freshlybakedca.ke
Git fork
1#include "git-compat-util.h"
2#include "string-list.h"
3
4void string_list_init_nodup(struct string_list *list)
5{
6 struct string_list blank = STRING_LIST_INIT_NODUP;
7 memcpy(list, &blank, sizeof(*list));
8}
9
10void string_list_init_dup(struct string_list *list)
11{
12 struct string_list blank = STRING_LIST_INIT_DUP;
13 memcpy(list, &blank, sizeof(*list));
14}
15
16/* if there is no exact match, point to the index where the entry could be
17 * inserted */
18static size_t get_entry_index(const struct string_list *list, const char *string,
19 bool *exact_match)
20{
21 size_t left = 0, right = list->nr;
22 compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
23
24 while (left < right) {
25 size_t middle = left + (right - left) / 2;
26 int compare = cmp(string, list->items[middle].string);
27 if (compare < 0)
28 right = middle;
29 else if (compare > 0)
30 left = middle + 1;
31 else {
32 if (exact_match)
33 *exact_match = true;
34 return middle;
35 }
36 }
37
38 if (exact_match)
39 *exact_match = false;
40 return right;
41}
42
43static size_t add_entry(struct string_list *list, const char *string)
44{
45 bool exact_match;
46 size_t index = get_entry_index(list, string, &exact_match);
47
48 if (exact_match)
49 return index;
50
51 ALLOC_GROW(list->items, list->nr+1, list->alloc);
52 if (index < list->nr)
53 MOVE_ARRAY(list->items + index + 1, list->items + index,
54 list->nr - index);
55 list->items[index].string = list->strdup_strings ?
56 xstrdup(string) : (char *)string;
57 list->items[index].util = NULL;
58 list->nr++;
59
60 return index;
61}
62
63struct string_list_item *string_list_insert(struct string_list *list, const char *string)
64{
65 size_t index = add_entry(list, string);
66
67 return list->items + index;
68}
69
70void string_list_remove(struct string_list *list, const char *string,
71 int free_util)
72{
73 bool exact_match;
74 int i = get_entry_index(list, string, &exact_match);
75
76 if (exact_match) {
77 if (list->strdup_strings)
78 free(list->items[i].string);
79 if (free_util)
80 free(list->items[i].util);
81
82 list->nr--;
83 MOVE_ARRAY(list->items + i, list->items + i + 1, list->nr - i);
84 }
85}
86
87bool string_list_has_string(const struct string_list *list, const char *string)
88{
89 bool exact_match;
90 get_entry_index(list, string, &exact_match);
91 return exact_match;
92}
93
94size_t string_list_find_insert_index(const struct string_list *list, const char *string,
95 bool *exact_match)
96{
97 return get_entry_index(list, string, exact_match);
98}
99
100struct string_list_item *string_list_lookup(struct string_list *list, const char *string)
101{
102 bool exact_match;
103 size_t i = get_entry_index(list, string, &exact_match);
104 if (!exact_match)
105 return NULL;
106 return list->items + i;
107}
108
109void string_list_remove_duplicates(struct string_list *list, int free_util)
110{
111 if (list->nr > 1) {
112 size_t dst = 1;
113 compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
114 for (size_t src = 1; src < list->nr; src++) {
115 if (!cmp(list->items[dst - 1].string, list->items[src].string)) {
116 if (list->strdup_strings)
117 free(list->items[src].string);
118 if (free_util)
119 free(list->items[src].util);
120 } else
121 list->items[dst++] = list->items[src];
122 }
123 list->nr = dst;
124 }
125}
126
127int for_each_string_list(struct string_list *list,
128 string_list_each_func_t fn, void *cb_data)
129{
130 int ret = 0;
131 for (size_t i = 0; i < list->nr; i++)
132 if ((ret = fn(&list->items[i], cb_data)))
133 break;
134 return ret;
135}
136
137void filter_string_list(struct string_list *list, int free_util,
138 string_list_each_func_t want, void *cb_data)
139{
140 size_t dst = 0;
141 for (size_t src = 0; src < list->nr; src++) {
142 if (want(&list->items[src], cb_data)) {
143 list->items[dst++] = list->items[src];
144 } else {
145 if (list->strdup_strings)
146 free(list->items[src].string);
147 if (free_util)
148 free(list->items[src].util);
149 }
150 }
151 list->nr = dst;
152}
153
154static int item_is_not_empty(struct string_list_item *item, void *data UNUSED)
155{
156 return *item->string != '\0';
157}
158
159void string_list_remove_empty_items(struct string_list *list, int free_util)
160{
161 filter_string_list(list, free_util, item_is_not_empty, NULL);
162}
163
164void string_list_clear(struct string_list *list, int free_util)
165{
166 if (list->items) {
167 if (list->strdup_strings) {
168 for (size_t i = 0; i < list->nr; i++)
169 free(list->items[i].string);
170 }
171 if (free_util) {
172 for (size_t i = 0; i < list->nr; i++)
173 free(list->items[i].util);
174 }
175 free(list->items);
176 }
177 list->items = NULL;
178 list->nr = list->alloc = 0;
179}
180
181void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc)
182{
183 if (list->items) {
184 if (clearfunc) {
185 for (size_t i = 0; i < list->nr; i++)
186 clearfunc(list->items[i].util, list->items[i].string);
187 }
188 if (list->strdup_strings) {
189 for (size_t i = 0; i < list->nr; i++)
190 free(list->items[i].string);
191 }
192 free(list->items);
193 }
194 list->items = NULL;
195 list->nr = list->alloc = 0;
196}
197
198void string_list_setlen(struct string_list *list, size_t nr)
199{
200 if (list->strdup_strings)
201 BUG("cannot setlen a string_list which owns its entries");
202 if (nr > list->nr)
203 BUG("cannot grow a string_list with setlen");
204 list->nr = nr;
205}
206
207struct string_list_item *string_list_append_nodup(struct string_list *list,
208 char *string)
209{
210 struct string_list_item *retval;
211 ALLOC_GROW(list->items, list->nr + 1, list->alloc);
212 retval = &list->items[list->nr++];
213 retval->string = string;
214 retval->util = NULL;
215 return retval;
216}
217
218struct string_list_item *string_list_append(struct string_list *list,
219 const char *string)
220{
221 return string_list_append_nodup(
222 list,
223 list->strdup_strings ? xstrdup(string) : (char *)string);
224}
225
226/*
227 * Encapsulate the compare function pointer because ISO C99 forbids
228 * casting from void * to a function pointer and vice versa.
229 */
230struct string_list_sort_ctx
231{
232 compare_strings_fn cmp;
233};
234
235static int cmp_items(const void *a, const void *b, void *ctx)
236{
237 struct string_list_sort_ctx *sort_ctx = ctx;
238 const struct string_list_item *one = a;
239 const struct string_list_item *two = b;
240 return sort_ctx->cmp(one->string, two->string);
241}
242
243void string_list_sort(struct string_list *list)
244{
245 struct string_list_sort_ctx sort_ctx = {list->cmp ? list->cmp : strcmp};
246
247 QSORT_S(list->items, list->nr, cmp_items, &sort_ctx);
248}
249
250struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
251 const char *string)
252{
253 struct string_list_item *item;
254 compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
255
256 for_each_string_list_item(item, list)
257 if (!cmp(string, item->string))
258 return item;
259 return NULL;
260}
261
262int unsorted_string_list_has_string(struct string_list *list,
263 const char *string)
264{
265 return unsorted_string_list_lookup(list, string) != NULL;
266}
267
268void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util)
269{
270 if (list->strdup_strings)
271 free(list->items[i].string);
272 if (free_util)
273 free(list->items[i].util);
274 list->items[i] = list->items[list->nr-1];
275 list->nr--;
276}
277
278/*
279 * append a substring [p..end] to list; return number of things it
280 * appended to the list.
281 */
282static int append_one(struct string_list *list,
283 const char *p, const char *end,
284 int in_place, unsigned flags)
285{
286 if (!end)
287 end = p + strlen(p);
288
289 if ((flags & STRING_LIST_SPLIT_TRIM)) {
290 /* rtrim */
291 for (; p < end; end--)
292 if (!isspace(end[-1]))
293 break;
294 }
295
296 if ((flags & STRING_LIST_SPLIT_NONEMPTY) && (end <= p))
297 return 0;
298
299 if (in_place) {
300 *((char *)end) = '\0';
301 string_list_append(list, p);
302 } else {
303 string_list_append_nodup(list, xmemdupz(p, end - p));
304 }
305 return 1;
306}
307
308/*
309 * Unfortunately this cannot become a public interface, as _in_place()
310 * wants to have "const char *string" while the other variant wants to
311 * have "char *string" for type safety.
312 *
313 * This accepts "const char *string" to allow both wrappers to use it;
314 * it internally casts away the constness when in_place is true by
315 * taking advantage of strpbrk() that takes a "const char *" arg and
316 * returns "char *" pointer into that const string. Yucky but works ;-).
317 */
318static int split_string(struct string_list *list, const char *string, const char *delim,
319 int maxsplit, int in_place, unsigned flags)
320{
321 int count = 0;
322 const char *p = string;
323
324 if (in_place && list->strdup_strings)
325 BUG("string_list_split_in_place() called with strdup_strings");
326 else if (!in_place && !list->strdup_strings)
327 BUG("string_list_split() called without strdup_strings");
328
329 for (;;) {
330 char *end;
331
332 if (flags & STRING_LIST_SPLIT_TRIM) {
333 /* ltrim */
334 while (*p && isspace(*p))
335 p++;
336 }
337
338 if (0 <= maxsplit && maxsplit <= count)
339 end = NULL;
340 else
341 end = strpbrk(p, delim);
342
343 count += append_one(list, p, end, in_place, flags);
344
345 if (!end)
346 return count;
347 p = end + 1;
348 }
349}
350
351int string_list_split(struct string_list *list, const char *string,
352 const char *delim, int maxsplit)
353{
354 return split_string(list, string, delim, maxsplit, 0, 0);
355}
356
357int string_list_split_in_place(struct string_list *list, char *string,
358 const char *delim, int maxsplit)
359{
360 return split_string(list, string, delim, maxsplit, 1, 0);
361}
362
363int string_list_split_f(struct string_list *list, const char *string,
364 const char *delim, int maxsplit, unsigned flags)
365{
366 return split_string(list, string, delim, maxsplit, 0, flags);
367}
368
369int string_list_split_in_place_f(struct string_list *list, char *string,
370 const char *delim, int maxsplit, unsigned flags)
371{
372 return split_string(list, string, delim, maxsplit, 1, flags);
373}