/src/git/string-list.c

Source (jump to first uncovered line)
#include "git-compat-util.h"
#include "string-list.h"

void string_list_init_nodup(struct string_list *list)
{
  struct string_list blank = STRING_LIST_INIT_NODUP;
  memcpy(list, &blank, sizeof(*list));
}

void string_list_init_dup(struct string_list *list)
{
  struct string_list blank = STRING_LIST_INIT_DUP;
  memcpy(list, &blank, sizeof(*list));
}

/* if there is no exact match, point to the index where the entry could be
 * inserted */
static int get_entry_index(const struct string_list *list, const char *string,
    int *exact_match)
{
  int left = -1, right = list->nr;
  compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;

  while (left + 1 < right) {
    int middle = left + (right - left) / 2;
    int compare = cmp(string, list->items[middle].string);
    if (compare < 0)
      right = middle;
    else if (compare > 0)
      left = middle;
    else {
      *exact_match = 1;
      return middle;
    }
  }

  *exact_match = 0;
  return right;
}

/* returns -1-index if already exists */
static int add_entry(int insert_at, struct string_list *list, const char *string)
{
  int exact_match = 0;
  int index = insert_at != -1 ? insert_at : get_entry_index(list, string, &exact_match);

  if (exact_match)
    return -1 - index;

  ALLOC_GROW(list->items, list->nr+1, list->alloc);
  if (index < list->nr)
    MOVE_ARRAY(list->items + index + 1, list->items + index,
         list->nr - index);
  list->items[index].string = list->strdup_strings ?
    xstrdup(string) : (char *)string;
  list->items[index].util = NULL;
  list->nr++;

  return index;
}

struct string_list_item *string_list_insert(struct string_list *list, const char *string)
{
  int index = add_entry(-1, list, string);

  if (index < 0)
    index = -1 - index;

  return list->items + index;
}

void string_list_remove(struct string_list *list, const char *string,
      int free_util)
{
  int exact_match;
  int i = get_entry_index(list, string, &exact_match);

  if (exact_match) {
    if (list->strdup_strings)
      free(list->items[i].string);
    if (free_util)
      free(list->items[i].util);

    list->nr--;
    MOVE_ARRAY(list->items + i, list->items + i + 1, list->nr - i);
  }
}

int string_list_has_string(const struct string_list *list, const char *string)
{
  int exact_match;
  get_entry_index(list, string, &exact_match);
  return exact_match;
}

int string_list_find_insert_index(const struct string_list *list, const char *string,
          int negative_existing_index)
{
  int exact_match;
  int index = get_entry_index(list, string, &exact_match);
  if (exact_match)
    index = -1 - (negative_existing_index ? index : 0);
  return index;
}

struct string_list_item *string_list_lookup(struct string_list *list, const char *string)
{
  int exact_match, i = get_entry_index(list, string, &exact_match);
  if (!exact_match)
    return NULL;
  return list->items + i;
}

void string_list_remove_duplicates(struct string_list *list, int free_util)
{
  if (list->nr > 1) {
    int src, dst;
    compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
    for (src = dst = 1; src < list->nr; src++) {
      if (!cmp(list->items[dst - 1].string, list->items[src].string)) {
        if (list->strdup_strings)
          free(list->items[src].string);
        if (free_util)
          free(list->items[src].util);
      } else
        list->items[dst++] = list->items[src];
    }
    list->nr = dst;
  }
}

int for_each_string_list(struct string_list *list,
       string_list_each_func_t fn, void *cb_data)
{
  int i, ret = 0;
  for (i = 0; i < list->nr; i++)
    if ((ret = fn(&list->items[i], cb_data)))
      break;
  return ret;
}

void filter_string_list(struct string_list *list, int free_util,
      string_list_each_func_t want, void *cb_data)
{
  int src, dst = 0;
  for (src = 0; src < list->nr; src++) {
    if (want(&list->items[src], cb_data)) {
      list->items[dst++] = list->items[src];
    } else {
      if (list->strdup_strings)
        free(list->items[src].string);
      if (free_util)
        free(list->items[src].util);
    }
  }
  list->nr = dst;
}

static int item_is_not_empty(struct string_list_item *item, void *data UNUSED)
{
  return *item->string != '\0';
}

void string_list_remove_empty_items(struct string_list *list, int free_util)
{
  filter_string_list(list, free_util, item_is_not_empty, NULL);
}

void string_list_clear(struct string_list *list, int free_util)
{
  if (list->items) {
    int i;
    if (list->strdup_strings) {
      for (i = 0; i < list->nr; i++)
        free(list->items[i].string);
    }
    if (free_util) {
      for (i = 0; i < list->nr; i++)
        free(list->items[i].util);
    }
    free(list->items);
  }
  list->items = NULL;
  list->nr = list->alloc = 0;
}

void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc)
{
  if (list->items) {
    int i;
    if (clearfunc) {
      for (i = 0; i < list->nr; i++)
        clearfunc(list->items[i].util, list->items[i].string);
    }
    if (list->strdup_strings) {
      for (i = 0; i < list->nr; i++)
        free(list->items[i].string);
    }
    free(list->items);
  }
  list->items = NULL;
  list->nr = list->alloc = 0;
}

void string_list_setlen(struct string_list *list, size_t nr)
{
  if (list->strdup_strings)
    BUG("cannot setlen a string_list which owns its entries");
  if (nr > list->nr)
    BUG("cannot grow a string_list with setlen");
  list->nr = nr;
}

struct string_list_item *string_list_append_nodup(struct string_list *list,
              char *string)
{
  struct string_list_item *retval;
  ALLOC_GROW(list->items, list->nr + 1, list->alloc);
  retval = &list->items[list->nr++];
  retval->string = string;
  retval->util = NULL;
  return retval;
}

struct string_list_item *string_list_append(struct string_list *list,
              const char *string)
{
  return string_list_append_nodup(
      list,
      list->strdup_strings ? xstrdup(string) : (char *)string);
}

/*
 * Encapsulate the compare function pointer because ISO C99 forbids
 * casting from void * to a function pointer and vice versa.
 */
struct string_list_sort_ctx
{
  compare_strings_fn cmp;
};

static int cmp_items(const void *a, const void *b, void *ctx)
{
  struct string_list_sort_ctx *sort_ctx = ctx;
  const struct string_list_item *one = a;
  const struct string_list_item *two = b;
  return sort_ctx->cmp(one->string, two->string);
}

void string_list_sort(struct string_list *list)
{
  struct string_list_sort_ctx sort_ctx = {list->cmp ? list->cmp : strcmp};

  QSORT_S(list->items, list->nr, cmp_items, &sort_ctx);
}

struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
                 const char *string)
{
  struct string_list_item *item;
  compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;

  for_each_string_list_item(item, list)
    if (!cmp(string, item->string))
      return item;
  return NULL;
}

int unsorted_string_list_has_string(struct string_list *list,
            const char *string)
{
  return unsorted_string_list_lookup(list, string) != NULL;
}

void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util)
{
  if (list->strdup_strings)
    free(list->items[i].string);
  if (free_util)
    free(list->items[i].util);
  list->items[i] = list->items[list->nr-1];
  list->nr--;
}

int string_list_split(struct string_list *list, const char *string,
          int delim, int maxsplit)
{
  int count = 0;
  const char *p = string, *end;

  if (!list->strdup_strings)
    die("internal error in string_list_split(): "
        "list->strdup_strings must be set");
  for (;;) {
    count++;
    if (maxsplit >= 0 && count > maxsplit) {
      string_list_append(list, p);
      return count;
    }
    end = strchr(p, delim);
    if (end) {
      string_list_append_nodup(list, xmemdupz(p, end - p));
      p = end + 1;
    } else {
      string_list_append(list, p);
      return count;
    }
  }
}

int string_list_split_in_place(struct string_list *list, char *string,
             const char *delim, int maxsplit)
{
  int count = 0;
  char *p = string, *end;

  if (list->strdup_strings)
    die("internal error in string_list_split_in_place(): "
        "list->strdup_strings must not be set");
  for (;;) {
    count++;
    if (maxsplit >= 0 && count > maxsplit) {
      string_list_append(list, p);
      return count;
    }
    end = strpbrk(p, delim);
    if (end) {
      *end = '\0';
      string_list_append(list, p);
      p = end + 1;
    } else {
      string_list_append(list, p);
      return count;
    }
  }
}

Coverage Report

Created: 2024-09-16 06:10

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