]>
Commit | Line | Data |
---|---|---|
0afcb5f7 TF |
1 | #ifndef STRING_LIST_H |
2 | #define STRING_LIST_H | |
c455c87c | 3 | |
4f665f2c HWN |
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 | |
065027ee EN |
7 | * entries are sorted by string value in the order specified by the `cmp` |
8 | * member (`strcmp()` by default). | |
4f665f2c HWN |
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 | */ | |
c455c87c JS |
68 | struct string_list_item { |
69 | char *string; | |
70 | void *util; | |
71 | }; | |
8dd5afc9 JH |
72 | |
73 | typedef int (*compare_strings_fn)(const char *, const char *); | |
74 | ||
4f665f2c HWN |
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 | */ | |
9cba13ca | 87 | struct string_list { |
c455c87c JS |
88 | struct string_list_item *items; |
89 | unsigned int nr, alloc; | |
90 | unsigned int strdup_strings:1; | |
8dd5afc9 | 91 | compare_strings_fn cmp; /* NULL uses strcmp() */ |
c455c87c JS |
92 | }; |
93 | ||
acb3d222 TA |
94 | #define STRING_LIST_INIT_NODUP { NULL, 0, 0, 0, NULL } |
95 | #define STRING_LIST_INIT_DUP { NULL, 0, 0, 1, NULL } | |
183113a5 | 96 | |
4f665f2c HWN |
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 | */ | |
3ed3f5fe TA |
103 | void string_list_init(struct string_list *list, int strdup_strings); |
104 | ||
4f665f2c HWN |
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 | ||
4f665f2c HWN |
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 | */ | |
c455c87c JS |
123 | void string_list_clear(struct string_list *list, int free_util); |
124 | ||
4f665f2c HWN |
125 | /** |
126 | * Callback type for `string_list_clear_func`. The string associated | |
127 | * with the util pointer is passed as the second argument | |
128 | */ | |
cfa1ee6b | 129 | typedef void (*string_list_clear_func_t)(void *p, const char *str); |
4f665f2c HWN |
130 | |
131 | /** Call a custom clear function on each util pointer */ | |
cfa1ee6b MSO |
132 | void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc); |
133 | ||
4f665f2c HWN |
134 | /** |
135 | * Apply `func` to each item. If `func` returns nonzero, the | |
136 | * iteration aborts and the return value is propagated. | |
137 | */ | |
b684e977 | 138 | int for_each_string_list(struct string_list *list, |
4f665f2c HWN |
139 | string_list_each_func_t func, void *cb_data); |
140 | ||
141 | /** Iterate over each item, as a macro. */ | |
ac7da78e MH |
142 | #define for_each_string_list_item(item,list) \ |
143 | for (item = (list)->items; \ | |
144 | item && item < (list)->items + (list)->nr; \ | |
145 | ++item) | |
c6f5a7a9 | 146 | |
4f665f2c | 147 | /** |
6bb2a137 MH |
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 | ||
c455c87c | 154 | /* Use these functions only on sorted lists: */ |
4f665f2c HWN |
155 | |
156 | /** Determine if the string_list has a given string or not. */ | |
c455c87c | 157 | int string_list_has_string(const struct string_list *list, const char *string); |
cfa1ee6b MSO |
158 | int string_list_find_insert_index(const struct string_list *list, const char *string, |
159 | int negative_existing_index); | |
4f665f2c HWN |
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 = ...;`. | |
fc66505c | 171 | */ |
78a395d3 | 172 | struct string_list_item *string_list_insert(struct string_list *list, const char *string); |
fc66505c | 173 | |
4f665f2c HWN |
174 | /** |
175 | * Remove the given string from the sorted list. If the string | |
176 | * doesn't exist, the list is not altered. | |
3a300333 | 177 | */ |
55454427 | 178 | void string_list_remove(struct string_list *list, const char *string, |
ad6dad09 | 179 | int free_util); |
3a300333 | 180 | |
4f665f2c HWN |
181 | /** |
182 | * Check if the given string is part of a sorted list. If it is part of the list, | |
15beaaa3 | 183 | * return the corresponding string_list_item, NULL otherwise. |
fc66505c | 184 | */ |
e8c8b713 | 185 | struct string_list_item *string_list_lookup(struct string_list *list, const char *string); |
c455c87c | 186 | |
31d5451e MH |
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 | ||
e448fed8 | 194 | |
c455c87c | 195 | /* Use these functions only on unsorted lists: */ |
e448fed8 | 196 | |
4f665f2c | 197 | /** |
e448fed8 MH |
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 | */ | |
1d2f80fa | 202 | struct string_list_item *string_list_append(struct string_list *list, const char *string); |
e448fed8 | 203 | |
4f665f2c | 204 | /** |
e448fed8 MH |
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 | ||
4f665f2c | 212 | /** |
065027ee EN |
213 | * Sort the list's entries by string value in order specified by list->cmp |
214 | * (strcmp() if list->cmp is NULL). | |
4f665f2c | 215 | */ |
3383e199 | 216 | void string_list_sort(struct string_list *list); |
4f665f2c HWN |
217 | |
218 | /** | |
219 | * Like `string_list_has_string()` but for unsorted lists. Linear in | |
220 | * size of the list. | |
221 | */ | |
c455c87c | 222 | int unsorted_string_list_has_string(struct string_list *list, const char *string); |
4f665f2c HWN |
223 | |
224 | /** | |
225 | * Like `string_list_lookup()` but for unsorted lists. Linear in size | |
226 | * of the list. | |
227 | */ | |
e2421480 SB |
228 | struct string_list_item *unsorted_string_list_lookup(struct string_list *list, |
229 | const char *string); | |
4f665f2c HWN |
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 | */ | |
86d4b528 | 236 | void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util); |
ff919f96 | 237 | |
4f665f2c HWN |
238 | /** |
239 | * Split string into substrings on character `delim` and append the | |
240 | * substrings to `list`. The input string is not modified. | |
ff919f96 MH |
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); | |
0afcb5f7 | 266 | #endif /* STRING_LIST_H */ |