word diff: handle zero length matches
[git] / string-list.h
1 #ifndef STRING_LIST_H
2 #define STRING_LIST_H
3
4 /**
5  * The string_list API offers a data structure and functions to handle
6  * sorted and unsorted arrays of strings.  A "sorted" list is one whose
7  * entries are sorted by string value in the order specified by the `cmp`
8  * member (`strcmp()` by default).
9  *
10  * The caller:
11  *
12  * . Allocates and clears a `struct string_list` variable.
13  *
14  * . Initializes the members. You might want to set the flag `strdup_strings`
15  *   if the strings should be strdup()ed. For example, this is necessary
16  *   when you add something like git_path("..."), since that function returns
17  *   a static buffer that will change with the next call to git_path().
18  *
19  * If you need something advanced, you can manually malloc() the `items`
20  * member (you need this if you add things later) and you should set the
21  * `nr` and `alloc` members in that case, too.
22  *
23  * . Adds new items to the list, using `string_list_append`,
24  *   `string_list_append_nodup`, `string_list_insert`,
25  *   `string_list_split`, and/or `string_list_split_in_place`.
26  *
27  * . Can check if a string is in the list using `string_list_has_string` or
28  *   `unsorted_string_list_has_string` and get it from the list using
29  *   `string_list_lookup` for sorted lists.
30  *
31  * . Can sort an unsorted list using `string_list_sort`.
32  *
33  * . Can remove duplicate items from a sorted list using
34  *   `string_list_remove_duplicates`.
35  *
36  * . Can remove individual items of an unsorted list using
37  *   `unsorted_string_list_delete_item`.
38  *
39  * . Can remove items not matching a criterion from a sorted or unsorted
40  *   list using `filter_string_list`, or remove empty strings using
41  *   `string_list_remove_empty_items`.
42  *
43  * . Finally it should free the list using `string_list_clear`.
44  *
45  * Example:
46  *
47  *     struct string_list list = STRING_LIST_INIT_NODUP;
48  *     int i;
49  *
50  *     string_list_append(&list, "foo");
51  *     string_list_append(&list, "bar");
52  *     for (i = 0; i < list.nr; i++)
53  *             printf("%s\n", list.items[i].string)
54  *
55  * NOTE: It is more efficient to build an unsorted list and sort it
56  * afterwards, instead of building a sorted list (`O(n log n)` instead of
57  * `O(n^2)`).
58  *
59  * However, if you use the list to check if a certain string was added
60  * already, you should not do that (using unsorted_string_list_has_string()),
61  * because the complexity would be quadratic again (but with a worse factor).
62  */
63
64 /**
65  * Represents an item of the list. The `string` member is a pointer to the
66  * string, and you may use the `util` member for any purpose, if you want.
67  */
68 struct string_list_item {
69         char *string;
70         void *util;
71 };
72
73 typedef int (*compare_strings_fn)(const char *, const char *);
74
75 /**
76  * Represents the list itself.
77  *
78  * . The array of items are available via the `items` member.
79  * . The `nr` member contains the number of items stored in the list.
80  * . The `alloc` member is used to avoid reallocating at every insertion.
81  *   You should not tamper with it.
82  * . Setting the `strdup_strings` member to 1 will strdup() the strings
83  *   before adding them, see above.
84  * . The `compare_strings_fn` member is used to specify a custom compare
85  *   function, otherwise `strcmp()` is used as the default function.
86  */
87 struct string_list {
88         struct string_list_item *items;
89         unsigned int nr, alloc;
90         unsigned int strdup_strings:1;
91         compare_strings_fn cmp; /* NULL uses strcmp() */
92 };
93
94 #define STRING_LIST_INIT_NODUP { NULL, 0, 0, 0, NULL }
95 #define STRING_LIST_INIT_DUP   { NULL, 0, 0, 1, NULL }
96
97 /* General functions which work with both sorted and unsorted lists. */
98
99 /**
100  * Initialize the members of the string_list, set `strdup_strings`
101  * member according to the value of the second parameter.
102  */
103 void string_list_init(struct string_list *list, int strdup_strings);
104
105 /** Callback function type for for_each_string_list */
106 typedef int (*string_list_each_func_t)(struct string_list_item *, void *);
107
108 /**
109  * Apply `want` to each item in `list`, retaining only the ones for which
110  * the function returns true.  If `free_util` is true, call free() on
111  * the util members of any items that have to be deleted.  Preserve
112  * the order of the items that are retained.
113  */
114 void filter_string_list(struct string_list *list, int free_util,
115                         string_list_each_func_t want, void *cb_data);
116
117 /**
118  * Free a string_list. The `string` pointer of the items will be freed
119  * in case the `strdup_strings` member of the string_list is set. The
120  * second parameter controls if the `util` pointer of the items should
121  * be freed or not.
122  */
123 void string_list_clear(struct string_list *list, int free_util);
124
125 /**
126  * Callback type for `string_list_clear_func`.  The string associated
127  * with the util pointer is passed as the second argument
128  */
129 typedef void (*string_list_clear_func_t)(void *p, const char *str);
130
131 /** Call a custom clear function on each util pointer */
132 void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc);
133
134 /**
135  * Apply `func` to each item. If `func` returns nonzero, the
136  * iteration aborts and the return value is propagated.
137  */
138 int for_each_string_list(struct string_list *list,
139                          string_list_each_func_t func, void *cb_data);
140
141 /** Iterate over each item, as a macro. */
142 #define for_each_string_list_item(item,list)            \
143         for (item = (list)->items;                      \
144              item && item < (list)->items + (list)->nr; \
145              ++item)
146
147 /**
148  * Remove any empty strings from the list.  If free_util is true, call
149  * free() on the util members of any items that have to be deleted.
150  * Preserve the order of the items that are retained.
151  */
152 void string_list_remove_empty_items(struct string_list *list, int free_util);
153
154 /* Use these functions only on sorted lists: */
155
156 /** Determine if the string_list has a given string or not. */
157 int string_list_has_string(const struct string_list *list, const char *string);
158 int string_list_find_insert_index(const struct string_list *list, const char *string,
159                                   int negative_existing_index);
160
161 /**
162  * Insert a new element to the string_list. The returned pointer can
163  * be handy if you want to write something to the `util` pointer of
164  * the string_list_item containing the just added string. If the given
165  * string already exists the insertion will be skipped and the pointer
166  * to the existing item returned.
167  *
168  * Since this function uses xrealloc() (which die()s if it fails) if the
169  * list needs to grow, it is safe not to check the pointer. I.e. you may
170  * write `string_list_insert(...)->util = ...;`.
171  */
172 struct string_list_item *string_list_insert(struct string_list *list, const char *string);
173
174 /**
175  * Remove the given string from the sorted list.  If the string
176  * doesn't exist, the list is not altered.
177  */
178 void string_list_remove(struct string_list *list, const char *string,
179                         int free_util);
180
181 /**
182  * Check if the given string is part of a sorted list. If it is part of the list,
183  * return the corresponding string_list_item, NULL otherwise.
184  */
185 struct string_list_item *string_list_lookup(struct string_list *list, const char *string);
186
187 /*
188  * Remove all but the first of consecutive entries with the same
189  * string value.  If free_util is true, call free() on the util
190  * members of any items that have to be deleted.
191  */
192 void string_list_remove_duplicates(struct string_list *sorted_list, int free_util);
193
194
195 /* Use these functions only on unsorted lists: */
196
197 /**
198  * Add string to the end of list.  If list->strdup_string is set, then
199  * string is copied; otherwise the new string_list_entry refers to the
200  * input string.
201  */
202 struct string_list_item *string_list_append(struct string_list *list, const char *string);
203
204 /**
205  * Like string_list_append(), except string is never copied.  When
206  * list->strdup_strings is set, this function can be used to hand
207  * ownership of a malloc()ed string to list without making an extra
208  * copy.
209  */
210 struct string_list_item *string_list_append_nodup(struct string_list *list, char *string);
211
212 /**
213  * Sort the list's entries by string value in order specified by list->cmp
214  * (strcmp() if list->cmp is NULL).
215  */
216 void string_list_sort(struct string_list *list);
217
218 /**
219  * Like `string_list_has_string()` but for unsorted lists. Linear in
220  * size of the list.
221  */
222 int unsorted_string_list_has_string(struct string_list *list, const char *string);
223
224 /**
225  * Like `string_list_lookup()` but for unsorted lists. Linear in size
226  * of the list.
227  */
228 struct string_list_item *unsorted_string_list_lookup(struct string_list *list,
229                                                      const char *string);
230 /**
231  * Remove an item from a string_list. The `string` pointer of the
232  * items will be freed in case the `strdup_strings` member of the
233  * string_list is set. The third parameter controls if the `util`
234  * pointer of the items should be freed or not.
235  */
236 void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util);
237
238 /**
239  * Split string into substrings on character `delim` and append the
240  * substrings to `list`.  The input string is not modified.
241  * list->strdup_strings must be set, as new memory needs to be
242  * allocated to hold the substrings.  If maxsplit is non-negative,
243  * then split at most maxsplit times.  Return the number of substrings
244  * appended to list.
245  *
246  * Examples:
247  *   string_list_split(l, "foo:bar:baz", ':', -1) -> ["foo", "bar", "baz"]
248  *   string_list_split(l, "foo:bar:baz", ':', 0) -> ["foo:bar:baz"]
249  *   string_list_split(l, "foo:bar:baz", ':', 1) -> ["foo", "bar:baz"]
250  *   string_list_split(l, "foo:bar:", ':', -1) -> ["foo", "bar", ""]
251  *   string_list_split(l, "", ':', -1) -> [""]
252  *   string_list_split(l, ":", ':', -1) -> ["", ""]
253  */
254 int string_list_split(struct string_list *list, const char *string,
255                       int delim, int maxsplit);
256
257 /*
258  * Like string_list_split(), except that string is split in-place: the
259  * delimiter characters in string are overwritten with NULs, and the
260  * new string_list_items point into string (which therefore must not
261  * be modified or freed while the string_list is in use).
262  * list->strdup_strings must *not* be set.
263  */
264 int string_list_split_in_place(struct string_list *list, char *string,
265                                int delim, int maxsplit);
266 #endif /* STRING_LIST_H */