git
/
string-list.c
336 строк · 8.0 Кб
1#include "git-compat-util.h"
2#include "string-list.h"
3
4void string_list_init_nodup(struct string_list *list)
5{
6struct string_list blank = STRING_LIST_INIT_NODUP;
7memcpy(list, &blank, sizeof(*list));
8}
9
10void string_list_init_dup(struct string_list *list)
11{
12struct string_list blank = STRING_LIST_INIT_DUP;
13memcpy(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 int get_entry_index(const struct string_list *list, const char *string,
19int *exact_match)
20{
21int left = -1, right = list->nr;
22compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
23
24while (left + 1 < right) {
25int middle = left + (right - left) / 2;
26int compare = cmp(string, list->items[middle].string);
27if (compare < 0)
28right = middle;
29else if (compare > 0)
30left = middle;
31else {
32*exact_match = 1;
33return middle;
34}
35}
36
37*exact_match = 0;
38return right;
39}
40
41/* returns -1-index if already exists */
42static int add_entry(int insert_at, struct string_list *list, const char *string)
43{
44int exact_match = 0;
45int index = insert_at != -1 ? insert_at : get_entry_index(list, string, &exact_match);
46
47if (exact_match)
48return -1 - index;
49
50ALLOC_GROW(list->items, list->nr+1, list->alloc);
51if (index < list->nr)
52MOVE_ARRAY(list->items + index + 1, list->items + index,
53list->nr - index);
54list->items[index].string = list->strdup_strings ?
55xstrdup(string) : (char *)string;
56list->items[index].util = NULL;
57list->nr++;
58
59return index;
60}
61
62struct string_list_item *string_list_insert(struct string_list *list, const char *string)
63{
64int index = add_entry(-1, list, string);
65
66if (index < 0)
67index = -1 - index;
68
69return list->items + index;
70}
71
72void string_list_remove(struct string_list *list, const char *string,
73int free_util)
74{
75int exact_match;
76int i = get_entry_index(list, string, &exact_match);
77
78if (exact_match) {
79if (list->strdup_strings)
80free(list->items[i].string);
81if (free_util)
82free(list->items[i].util);
83
84list->nr--;
85MOVE_ARRAY(list->items + i, list->items + i + 1, list->nr - i);
86}
87}
88
89int string_list_has_string(const struct string_list *list, const char *string)
90{
91int exact_match;
92get_entry_index(list, string, &exact_match);
93return exact_match;
94}
95
96int string_list_find_insert_index(const struct string_list *list, const char *string,
97int negative_existing_index)
98{
99int exact_match;
100int index = get_entry_index(list, string, &exact_match);
101if (exact_match)
102index = -1 - (negative_existing_index ? index : 0);
103return index;
104}
105
106struct string_list_item *string_list_lookup(struct string_list *list, const char *string)
107{
108int exact_match, i = get_entry_index(list, string, &exact_match);
109if (!exact_match)
110return NULL;
111return list->items + i;
112}
113
114void string_list_remove_duplicates(struct string_list *list, int free_util)
115{
116if (list->nr > 1) {
117int src, dst;
118compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
119for (src = dst = 1; src < list->nr; src++) {
120if (!cmp(list->items[dst - 1].string, list->items[src].string)) {
121if (list->strdup_strings)
122free(list->items[src].string);
123if (free_util)
124free(list->items[src].util);
125} else
126list->items[dst++] = list->items[src];
127}
128list->nr = dst;
129}
130}
131
132int for_each_string_list(struct string_list *list,
133string_list_each_func_t fn, void *cb_data)
134{
135int i, ret = 0;
136for (i = 0; i < list->nr; i++)
137if ((ret = fn(&list->items[i], cb_data)))
138break;
139return ret;
140}
141
142void filter_string_list(struct string_list *list, int free_util,
143string_list_each_func_t want, void *cb_data)
144{
145int src, dst = 0;
146for (src = 0; src < list->nr; src++) {
147if (want(&list->items[src], cb_data)) {
148list->items[dst++] = list->items[src];
149} else {
150if (list->strdup_strings)
151free(list->items[src].string);
152if (free_util)
153free(list->items[src].util);
154}
155}
156list->nr = dst;
157}
158
159static int item_is_not_empty(struct string_list_item *item, void *data UNUSED)
160{
161return *item->string != '\0';
162}
163
164void string_list_remove_empty_items(struct string_list *list, int free_util)
165{
166filter_string_list(list, free_util, item_is_not_empty, NULL);
167}
168
169void string_list_clear(struct string_list *list, int free_util)
170{
171if (list->items) {
172int i;
173if (list->strdup_strings) {
174for (i = 0; i < list->nr; i++)
175free(list->items[i].string);
176}
177if (free_util) {
178for (i = 0; i < list->nr; i++)
179free(list->items[i].util);
180}
181free(list->items);
182}
183list->items = NULL;
184list->nr = list->alloc = 0;
185}
186
187void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc)
188{
189if (list->items) {
190int i;
191if (clearfunc) {
192for (i = 0; i < list->nr; i++)
193clearfunc(list->items[i].util, list->items[i].string);
194}
195if (list->strdup_strings) {
196for (i = 0; i < list->nr; i++)
197free(list->items[i].string);
198}
199free(list->items);
200}
201list->items = NULL;
202list->nr = list->alloc = 0;
203}
204
205void string_list_setlen(struct string_list *list, size_t nr)
206{
207if (list->strdup_strings)
208BUG("cannot setlen a string_list which owns its entries");
209if (nr > list->nr)
210BUG("cannot grow a string_list with setlen");
211list->nr = nr;
212}
213
214struct string_list_item *string_list_append_nodup(struct string_list *list,
215char *string)
216{
217struct string_list_item *retval;
218ALLOC_GROW(list->items, list->nr + 1, list->alloc);
219retval = &list->items[list->nr++];
220retval->string = string;
221retval->util = NULL;
222return retval;
223}
224
225struct string_list_item *string_list_append(struct string_list *list,
226const char *string)
227{
228return string_list_append_nodup(
229list,
230list->strdup_strings ? xstrdup(string) : (char *)string);
231}
232
233/*
234* Encapsulate the compare function pointer because ISO C99 forbids
235* casting from void * to a function pointer and vice versa.
236*/
237struct string_list_sort_ctx
238{
239compare_strings_fn cmp;
240};
241
242static int cmp_items(const void *a, const void *b, void *ctx)
243{
244struct string_list_sort_ctx *sort_ctx = ctx;
245const struct string_list_item *one = a;
246const struct string_list_item *two = b;
247return sort_ctx->cmp(one->string, two->string);
248}
249
250void string_list_sort(struct string_list *list)
251{
252struct string_list_sort_ctx sort_ctx = {list->cmp ? list->cmp : strcmp};
253
254QSORT_S(list->items, list->nr, cmp_items, &sort_ctx);
255}
256
257struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
258const char *string)
259{
260struct string_list_item *item;
261compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
262
263for_each_string_list_item(item, list)
264if (!cmp(string, item->string))
265return item;
266return NULL;
267}
268
269int unsorted_string_list_has_string(struct string_list *list,
270const char *string)
271{
272return unsorted_string_list_lookup(list, string) != NULL;
273}
274
275void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util)
276{
277if (list->strdup_strings)
278free(list->items[i].string);
279if (free_util)
280free(list->items[i].util);
281list->items[i] = list->items[list->nr-1];
282list->nr--;
283}
284
285int string_list_split(struct string_list *list, const char *string,
286int delim, int maxsplit)
287{
288int count = 0;
289const char *p = string, *end;
290
291if (!list->strdup_strings)
292die("internal error in string_list_split(): "
293"list->strdup_strings must be set");
294for (;;) {
295count++;
296if (maxsplit >= 0 && count > maxsplit) {
297string_list_append(list, p);
298return count;
299}
300end = strchr(p, delim);
301if (end) {
302string_list_append_nodup(list, xmemdupz(p, end - p));
303p = end + 1;
304} else {
305string_list_append(list, p);
306return count;
307}
308}
309}
310
311int string_list_split_in_place(struct string_list *list, char *string,
312const char *delim, int maxsplit)
313{
314int count = 0;
315char *p = string, *end;
316
317if (list->strdup_strings)
318die("internal error in string_list_split_in_place(): "
319"list->strdup_strings must not be set");
320for (;;) {
321count++;
322if (maxsplit >= 0 && count > maxsplit) {
323string_list_append(list, p);
324return count;
325}
326end = strpbrk(p, delim);
327if (end) {
328*end = '\0';
329string_list_append(list, p);
330p = end + 1;
331} else {
332string_list_append(list, p);
333return count;
334}
335}
336}
337