1#include "cache.h"
2#include "string-list.h"
3void string_list_init(struct string_list *list, int strdup_strings)
5{
6 memset(list, 0, sizeof(*list));
7 list->strdup_strings = strdup_strings;
8}
9/* if there is no exact match, point to the index where the entry could be
11 * inserted */
12static int get_entry_index(const struct string_list *list, const char *string,
13 int *exact_match)
14{
15 int left = -1, right = list->nr;
16 compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
17 while (left + 1 < right) {
19 int middle = (left + right) / 2;
20 int compare = cmp(string, list->items[middle].string);
21 if (compare < 0)
22 right = middle;
23 else if (compare > 0)
24 left = middle;
25 else {
26 *exact_match = 1;
27 return middle;
28 }
29 }
30 *exact_match = 0;
32 return right;
33}
34/* returns -1-index if already exists */
36static int add_entry(int insert_at, struct string_list *list, const char *string)
37{
38 int exact_match = 0;
39 int index = insert_at != -1 ? insert_at : get_entry_index(list, string, &exact_match);
40 if (exact_match)
42 return -1 - index;
43 ALLOC_GROW(list->items, list->nr+1, list->alloc);
45 if (index < list->nr)
46 memmove(list->items + index + 1, list->items + index,
47 (list->nr - index)
48 * sizeof(struct string_list_item));
49 list->items[index].string = list->strdup_strings ?
50 xstrdup(string) : (char *)string;
51 list->items[index].util = NULL;
52 list->nr++;
53 return index;
55}
56struct string_list_item *string_list_insert(struct string_list *list, const char *string)
58{
59 int index = add_entry(-1, list, string);
60 if (index < 0)
62 index = -1 - index;
63 return list->items + index;
65}
66int string_list_has_string(const struct string_list *list, const char *string)
68{
69 int exact_match;
70 get_entry_index(list, string, &exact_match);
71 return exact_match;
72}
73int string_list_find_insert_index(const struct string_list *list, const char *string,
75 int negative_existing_index)
76{
77 int exact_match;
78 int index = get_entry_index(list, string, &exact_match);
79 if (exact_match)
80 index = -1 - (negative_existing_index ? index : 0);
81 return index;
82}
83struct string_list_item *string_list_lookup(struct string_list *list, const char *string)
85{
86 int exact_match, i = get_entry_index(list, string, &exact_match);
87 if (!exact_match)
88 return NULL;
89 return list->items + i;
90}
91void string_list_remove_duplicates(struct string_list *list, int free_util)
93{
94 if (list->nr > 1) {
95 int src, dst;
96 compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
97 for (src = dst = 1; src < list->nr; src++) {
98 if (!cmp(list->items[dst - 1].string, list->items[src].string)) {
99 if (list->strdup_strings)
100 free(list->items[src].string);
101 if (free_util)
102 free(list->items[src].util);
103 } else
104 list->items[dst++] = list->items[src];
105 }
106 list->nr = dst;
107 }
108}
109int for_each_string_list(struct string_list *list,
111 string_list_each_func_t fn, void *cb_data)
112{
113 int i, ret = 0;
114 for (i = 0; i < list->nr; i++)
115 if ((ret = fn(&list->items[i], cb_data)))
116 break;
117 return ret;
118}
119void filter_string_list(struct string_list *list, int free_util,
121 string_list_each_func_t want, void *cb_data)
122{
123 int src, dst = 0;
124 for (src = 0; src < list->nr; src++) {
125 if (want(&list->items[src], cb_data)) {
126 list->items[dst++] = list->items[src];
127 } else {
128 if (list->strdup_strings)
129 free(list->items[src].string);
130 if (free_util)
131 free(list->items[src].util);
132 }
133 }
134 list->nr = dst;
135}
136static int item_is_not_empty(struct string_list_item *item, void *unused)
138{
139 return *item->string != '\0';
140}
141void string_list_remove_empty_items(struct string_list *list, int free_util) {
143 filter_string_list(list, free_util, item_is_not_empty, NULL);
144}
145void string_list_clear(struct string_list *list, int free_util)
147{
148 if (list->items) {
149 int i;
150 if (list->strdup_strings) {
151 for (i = 0; i < list->nr; i++)
152 free(list->items[i].string);
153 }
154 if (free_util) {
155 for (i = 0; i < list->nr; i++)
156 free(list->items[i].util);
157 }
158 free(list->items);
159 }
160 list->items = NULL;
161 list->nr = list->alloc = 0;
162}
163void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc)
165{
166 if (list->items) {
167 int i;
168 if (clearfunc) {
169 for (i = 0; i < list->nr; i++)
170 clearfunc(list->items[i].util, list->items[i].string);
171 }
172 if (list->strdup_strings) {
173 for (i = 0; i < list->nr; i++)
174 free(list->items[i].string);
175 }
176 free(list->items);
177 }
178 list->items = NULL;
179 list->nr = list->alloc = 0;
180}
181void print_string_list(const struct string_list *p, const char *text)
184{
185 int i;
186 if ( text )
187 printf("%s\n", text);
188 for (i = 0; i < p->nr; i++)
189 printf("%s:%p\n", p->items[i].string, p->items[i].util);
190}
191struct string_list_item *string_list_append_nodup(struct string_list *list,
193 char *string)
194{
195 struct string_list_item *retval;
196 ALLOC_GROW(list->items, list->nr + 1, list->alloc);
197 retval = &list->items[list->nr++];
198 retval->string = string;
199 retval->util = NULL;
200 return retval;
201}
202struct string_list_item *string_list_append(struct string_list *list,
204 const char *string)
205{
206 return string_list_append_nodup(
207 list,
208 list->strdup_strings ? xstrdup(string) : (char *)string);
209}
210static int cmp_items(const void *a, const void *b, void *ctx)
212{
213 compare_strings_fn cmp = ctx;
214 const struct string_list_item *one = a;
215 const struct string_list_item *two = b;
216 return cmp(one->string, two->string);
217}
218void string_list_sort(struct string_list *list)
220{
221 QSORT_S(list->items, list->nr, cmp_items,
222 list->cmp ? list->cmp : strcmp);
223}
224struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
226 const char *string)
227{
228 struct string_list_item *item;
229 compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
230 for_each_string_list_item(item, list)
232 if (!cmp(string, item->string))
233 return item;
234 return NULL;
235}
236int unsorted_string_list_has_string(struct string_list *list,
238 const char *string)
239{
240 return unsorted_string_list_lookup(list, string) != NULL;
241}
242void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util)
244{
245 if (list->strdup_strings)
246 free(list->items[i].string);
247 if (free_util)
248 free(list->items[i].util);
249 list->items[i] = list->items[list->nr-1];
250 list->nr--;
251}
252int string_list_split(struct string_list *list, const char *string,
254 int delim, int maxsplit)
255{
256 int count = 0;
257 const char *p = string, *end;
258 if (!list->strdup_strings)
260 die("internal error in string_list_split(): "
261 "list->strdup_strings must be set");
262 for (;;) {
263 count++;
264 if (maxsplit >= 0 && count > maxsplit) {
265 string_list_append(list, p);
266 return count;
267 }
268 end = strchr(p, delim);
269 if (end) {
270 string_list_append_nodup(list, xmemdupz(p, end - p));
271 p = end + 1;
272 } else {
273 string_list_append(list, p);
274 return count;
275 }
276 }
277}
278int string_list_split_in_place(struct string_list *list, char *string,
280 int delim, int maxsplit)
281{
282 int count = 0;
283 char *p = string, *end;
284 if (list->strdup_strings)
286 die("internal error in string_list_split_in_place(): "
287 "list->strdup_strings must not be set");
288 for (;;) {
289 count++;
290 if (maxsplit >= 0 && count > maxsplit) {
291 string_list_append(list, p);
292 return count;
293 }
294 end = strchr(p, delim);
295 if (end) {
296 *end = '\0';
297 string_list_append(list, p);
298 p = end + 1;
299 } else {
300 string_list_append(list, p);
301 return count;
302 }
303 }
304}