1 /*
2 * Part of Very Secure FTPd
3 * Licence: GPL v2
4 * Author: Chris Evans
5 * strlist.c
6 */
7
8 /* Anti-lamer measures deployed, sir! */
9 #define PRIVATE_HANDS_OFF_alloc_len alloc_len
10 #define PRIVATE_HANDS_OFF_list_len list_len
11 #define PRIVATE_HANDS_OFF_p_nodes p_nodes
12 #include "strlist.h"
13
14 #include "str.h"
15 #include "utility.h"
16 #include "sysutil.h"
17
18 struct mystr_list_node
19 {
20 struct mystr str;
21 struct mystr sort_key_str;
22 };
23
24 /* File locals */
25 static const unsigned int kMaxStrlist = 10 * 1000 * 1000;
26
27 static struct mystr s_null_str;
28
29 static int sort_compare_func(const void* p1, const void* p2);
30 static int sort_compare_func_reverse(const void* p1, const void* p2);
31 static int sort_compare_common(const void* p1, const void* p2, int reverse);
32
33 void
str_list_free(struct mystr_list * p_list)34 str_list_free(struct mystr_list* p_list)
35 {
36 unsigned int i;
37 for (i=0; i < p_list->list_len; ++i)
38 {
39 str_free(&p_list->p_nodes[i].str);
40 str_free(&p_list->p_nodes[i].sort_key_str);
41 }
42 p_list->list_len = 0;
43 p_list->alloc_len = 0;
44 if (p_list->p_nodes)
45 {
46 vsf_sysutil_free(p_list->p_nodes);
47 p_list->p_nodes = 0;
48 }
49 }
50
51 unsigned int
str_list_get_length(const struct mystr_list * p_list)52 str_list_get_length(const struct mystr_list* p_list)
53 {
54 return p_list->list_len;
55 }
56
57 int
str_list_contains_str(const struct mystr_list * p_list,const struct mystr * p_str)58 str_list_contains_str(const struct mystr_list* p_list,
59 const struct mystr* p_str)
60 {
61 unsigned int i;
62 for (i=0; i < p_list->list_len; ++i)
63 {
64 if (str_equal(p_str, &p_list->p_nodes[i].str))
65 {
66 return 1;
67 }
68 }
69 return 0;
70 }
71
72 void
str_list_add(struct mystr_list * p_list,const struct mystr * p_str,const struct mystr * p_sort_key_str)73 str_list_add(struct mystr_list* p_list, const struct mystr* p_str,
74 const struct mystr* p_sort_key_str)
75 {
76 struct mystr_list_node* p_node;
77 /* Expand the node allocation if we have to */
78 if (p_list->list_len == p_list->alloc_len)
79 {
80 if (p_list->alloc_len == 0)
81 {
82 p_list->alloc_len = 32;
83 p_list->p_nodes = vsf_sysutil_malloc(
84 p_list->alloc_len * (unsigned int) sizeof(struct mystr_list_node));
85 }
86 else
87 {
88 p_list->alloc_len *= 2;
89 if (p_list->alloc_len > kMaxStrlist)
90 {
91 die("excessive strlist");
92 }
93 p_list->p_nodes = vsf_sysutil_realloc(
94 p_list->p_nodes,
95 p_list->alloc_len * (unsigned int) sizeof(struct mystr_list_node));
96 }
97 }
98 p_node = &p_list->p_nodes[p_list->list_len];
99 p_node->str = s_null_str;
100 p_node->sort_key_str = s_null_str;
101 str_copy(&p_node->str, p_str);
102 if (p_sort_key_str)
103 {
104 str_copy(&p_node->sort_key_str, p_sort_key_str);
105 }
106 p_list->list_len++;
107 }
108
109 void
str_list_sort(struct mystr_list * p_list,int reverse)110 str_list_sort(struct mystr_list* p_list, int reverse)
111 {
112 if (!reverse)
113 {
114 vsf_sysutil_qsort(p_list->p_nodes, p_list->list_len,
115 sizeof(struct mystr_list_node), sort_compare_func);
116 }
117 else
118 {
119 vsf_sysutil_qsort(p_list->p_nodes, p_list->list_len,
120 sizeof(struct mystr_list_node),
121 sort_compare_func_reverse);
122 }
123 }
124
125 static int
sort_compare_func(const void * p1,const void * p2)126 sort_compare_func(const void* p1, const void* p2)
127 {
128 return sort_compare_common(p1, p2, 0);
129 }
130
131 static int
sort_compare_func_reverse(const void * p1,const void * p2)132 sort_compare_func_reverse(const void* p1, const void* p2)
133 {
134 return sort_compare_common(p1, p2, 1);
135 }
136
137 static int
sort_compare_common(const void * p1,const void * p2,int reverse)138 sort_compare_common(const void* p1, const void* p2, int reverse)
139 {
140 const struct mystr* p_cmp1;
141 const struct mystr* p_cmp2;
142 const struct mystr_list_node* p_node1 = (const struct mystr_list_node*) p1;
143 const struct mystr_list_node* p_node2 = (const struct mystr_list_node*) p2;
144 if (!str_isempty(&p_node1->sort_key_str))
145 {
146 p_cmp1 = &p_node1->sort_key_str;
147 }
148 else
149 {
150 p_cmp1 = &p_node1->str;
151 }
152 if (!str_isempty(&p_node2->sort_key_str))
153 {
154 p_cmp2 = &p_node2->sort_key_str;
155 }
156 else
157 {
158 p_cmp2 = &p_node2->str;
159 }
160
161 if (reverse)
162 {
163 return str_strcmp(p_cmp2, p_cmp1);
164 }
165 else
166 {
167 return str_strcmp(p_cmp1, p_cmp2);
168 }
169 }
170
171 const struct mystr*
str_list_get_pstr(const struct mystr_list * p_list,unsigned int indexx)172 str_list_get_pstr(const struct mystr_list* p_list, unsigned int indexx)
173 {
174 if (indexx >= p_list->list_len)
175 {
176 bug("indexx out of range in str_list_get_str");
177 }
178 return &p_list->p_nodes[indexx].str;
179 }
180
181