/src/git/string-list.c

Source
#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 size_t get_entry_index(const struct string_list *list, const char *string,
            bool *exact_match)
{
  size_t left = 0, right = list->nr;
  compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;

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

  if (exact_match)
    *exact_match = false;
  return right;
}

static size_t add_entry(struct string_list *list, const char *string)
{
  bool exact_match;
  size_t index = get_entry_index(list, string, &exact_match);

  if (exact_match)
    return 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)
{
  size_t index = add_entry(list, string);

  return list->items + index;
}

void string_list_remove(struct string_list *list, const char *string,
      int free_util)
{
  bool 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);
  }
}

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

size_t string_list_find_insert_index(const struct string_list *list, const char *string,
             bool *exact_match)
{
  return get_entry_index(list, string, exact_match);
}

struct string_list_item *string_list_lookup(struct string_list *list, const char *string)
{
  bool exact_match;
  size_t 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) {
    size_t dst = 1;
    compare_strings_fn cmp = list->cmp ? list->cmp : strcmp;
    for (size_t src = 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 ret = 0;
  for (size_t 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)
{
  size_t dst = 0;
  for (size_t 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) {
    if (list->strdup_strings) {
      for (size_t i = 0; i < list->nr; i++)
        free(list->items[i].string);
    }
    if (free_util) {
      for (size_t 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) {
    if (clearfunc) {
      for (size_t i = 0; i < list->nr; i++)
        clearfunc(list->items[i].util, list->items[i].string);
    }
    if (list->strdup_strings) {
      for (size_t 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--;
}

/*
 * append a substring [p..end] to list; return number of things it
 * appended to the list.
 */
static int append_one(struct string_list *list,
          const char *p, const char *end,
          int in_place, unsigned flags)
{
  if (!end)
    end = p + strlen(p);

  if ((flags & STRING_LIST_SPLIT_TRIM)) {
    /* rtrim */
    for (; p < end; end--)
      if (!isspace(end[-1]))
        break;
  }

  if ((flags & STRING_LIST_SPLIT_NONEMPTY) && (end <= p))
    return 0;

  if (in_place) {
    *((char *)end) = '\0';
    string_list_append(list, p);
  } else {
    string_list_append_nodup(list, xmemdupz(p, end - p));
  }
  return 1;
}

/*
 * Unfortunately this cannot become a public interface, as _in_place()
 * wants to have "const char *string" while the other variant wants to
 * have "char *string" for type safety.
 *
 * This accepts "const char *string" to allow both wrappers to use it;
 * it internally casts away the constness when in_place is true by
 * taking advantage of strpbrk() that takes a "const char *" arg and
 * returns "char *" pointer into that const string.  Yucky but works ;-).
 */
static int split_string(struct string_list *list, const char *string, const char *delim,
      int maxsplit, int in_place, unsigned flags)
{
  int count = 0;
  const char *p = string;

  if (in_place && list->strdup_strings)
    BUG("string_list_split_in_place() called with strdup_strings");
  else if (!in_place && !list->strdup_strings)
    BUG("string_list_split() called without strdup_strings");

  for (;;) {
    char *end;

    if (flags & STRING_LIST_SPLIT_TRIM) {
      /* ltrim */
      while (*p && isspace(*p))
        p++;
    }

    if (0 <= maxsplit && maxsplit <= count)
      end = NULL;
    else
      end = strpbrk(p, delim);

    count += append_one(list, p, end, in_place, flags);

    if (!end)
      return count;
    p = end + 1;
  }
}

int string_list_split(struct string_list *list, const char *string,
          const char *delim, int maxsplit)
{
  return split_string(list, string, delim, maxsplit, 0, 0);
}

int string_list_split_in_place(struct string_list *list, char *string,
             const char *delim, int maxsplit)
{
  return split_string(list, string, delim, maxsplit, 1, 0);
}

int string_list_split_f(struct string_list *list, const char *string,
      const char *delim, int maxsplit, unsigned flags)
{
  return split_string(list, string, delim, maxsplit, 0, flags);
}

int string_list_split_in_place_f(struct string_list *list, char *string,
             const char *delim, int maxsplit, unsigned flags)
{
  return split_string(list, string, delim, maxsplit, 1, flags);
}

Coverage Report

Created: 2025-12-31 07:01

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