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