]>
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 | 88 | struct string_list_item *items; |
99d60545 ÆAB |
89 | size_t nr; |
90 | size_t alloc; | |
c455c87c | 91 | unsigned int strdup_strings:1; |
8dd5afc9 | 92 | compare_strings_fn cmp; /* NULL uses strcmp() */ |
c455c87c JS |
93 | }; |
94 | ||
3d97ea47 ÆAB |
95 | #define STRING_LIST_INIT_NODUP { 0 } |
96 | #define STRING_LIST_INIT_DUP { .strdup_strings = 1 } | |
183113a5 | 97 | |
4f665f2c HWN |
98 | /* General functions which work with both sorted and unsorted lists. */ |
99 | ||
100 | /** | |
770fedaf ÆAB |
101 | * Initialize the members of a string_list pointer in the same way as |
102 | * the corresponding `STRING_LIST_INIT_NODUP` and | |
103 | * `STRING_LIST_INIT_DUP` macros. | |
104 | */ | |
105 | void string_list_init_nodup(struct string_list *list); | |
106 | void string_list_init_dup(struct string_list *list); | |
107 | ||
4f665f2c HWN |
108 | /** Callback function type for for_each_string_list */ |
109 | typedef int (*string_list_each_func_t)(struct string_list_item *, void *); | |
110 | ||
111 | /** | |
112 | * Apply `want` to each item in `list`, retaining only the ones for which | |
113 | * the function returns true. If `free_util` is true, call free() on | |
114 | * the util members of any items that have to be deleted. Preserve | |
115 | * the order of the items that are retained. | |
116 | */ | |
117 | void filter_string_list(struct string_list *list, int free_util, | |
118 | string_list_each_func_t want, void *cb_data); | |
119 | ||
4f665f2c HWN |
120 | /** |
121 | * Free a string_list. The `string` pointer of the items will be freed | |
122 | * in case the `strdup_strings` member of the string_list is set. The | |
123 | * second parameter controls if the `util` pointer of the items should | |
124 | * be freed or not. | |
125 | */ | |
c455c87c JS |
126 | void string_list_clear(struct string_list *list, int free_util); |
127 | ||
4f665f2c HWN |
128 | /** |
129 | * Callback type for `string_list_clear_func`. The string associated | |
130 | * with the util pointer is passed as the second argument | |
131 | */ | |
cfa1ee6b | 132 | typedef void (*string_list_clear_func_t)(void *p, const char *str); |
4f665f2c HWN |
133 | |
134 | /** Call a custom clear function on each util pointer */ | |
cfa1ee6b MSO |
135 | void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc); |
136 | ||
492ba813 TB |
137 | /* |
138 | * Set the length of a string_list to `nr`, provided that (a) `list` | |
139 | * does not own its own storage, and (b) that `nr` is no larger than | |
140 | * `list->nr`. | |
141 | * | |
142 | * Useful when "shrinking" `list` to write over existing entries that | |
143 | * are no longer used without reallocating. | |
144 | */ | |
145 | void string_list_setlen(struct string_list *list, size_t nr); | |
146 | ||
4f665f2c HWN |
147 | /** |
148 | * Apply `func` to each item. If `func` returns nonzero, the | |
149 | * iteration aborts and the return value is propagated. | |
150 | */ | |
b684e977 | 151 | int for_each_string_list(struct string_list *list, |
4f665f2c HWN |
152 | string_list_each_func_t func, void *cb_data); |
153 | ||
d151f0cc DS |
154 | /** |
155 | * Iterate over each item, as a macro. | |
156 | * | |
157 | * Be sure that 'list' is non-NULL. The macro cannot perform NULL | |
158 | * checks due to -Werror=address errors. | |
159 | */ | |
ac7da78e MH |
160 | #define for_each_string_list_item(item,list) \ |
161 | for (item = (list)->items; \ | |
162 | item && item < (list)->items + (list)->nr; \ | |
163 | ++item) | |
c6f5a7a9 | 164 | |
4f665f2c | 165 | /** |
6bb2a137 MH |
166 | * Remove any empty strings from the list. If free_util is true, call |
167 | * free() on the util members of any items that have to be deleted. | |
168 | * Preserve the order of the items that are retained. | |
169 | */ | |
170 | void string_list_remove_empty_items(struct string_list *list, int free_util); | |
171 | ||
c455c87c | 172 | /* Use these functions only on sorted lists: */ |
4f665f2c HWN |
173 | |
174 | /** Determine if the string_list has a given string or not. */ | |
c455c87c | 175 | int string_list_has_string(const struct string_list *list, const char *string); |
cfa1ee6b MSO |
176 | int string_list_find_insert_index(const struct string_list *list, const char *string, |
177 | int negative_existing_index); | |
4f665f2c HWN |
178 | |
179 | /** | |
180 | * Insert a new element to the string_list. The returned pointer can | |
181 | * be handy if you want to write something to the `util` pointer of | |
182 | * the string_list_item containing the just added string. If the given | |
183 | * string already exists the insertion will be skipped and the pointer | |
184 | * to the existing item returned. | |
185 | * | |
186 | * Since this function uses xrealloc() (which die()s if it fails) if the | |
187 | * list needs to grow, it is safe not to check the pointer. I.e. you may | |
188 | * write `string_list_insert(...)->util = ...;`. | |
fc66505c | 189 | */ |
78a395d3 | 190 | struct string_list_item *string_list_insert(struct string_list *list, const char *string); |
fc66505c | 191 | |
4f665f2c HWN |
192 | /** |
193 | * Remove the given string from the sorted list. If the string | |
194 | * doesn't exist, the list is not altered. | |
3a300333 | 195 | */ |
55454427 | 196 | void string_list_remove(struct string_list *list, const char *string, |
ad6dad09 | 197 | int free_util); |
3a300333 | 198 | |
4f665f2c HWN |
199 | /** |
200 | * Check if the given string is part of a sorted list. If it is part of the list, | |
15beaaa3 | 201 | * return the corresponding string_list_item, NULL otherwise. |
fc66505c | 202 | */ |
e8c8b713 | 203 | struct string_list_item *string_list_lookup(struct string_list *list, const char *string); |
c455c87c | 204 | |
31d5451e MH |
205 | /* |
206 | * Remove all but the first of consecutive entries with the same | |
207 | * string value. If free_util is true, call free() on the util | |
208 | * members of any items that have to be deleted. | |
209 | */ | |
210 | void string_list_remove_duplicates(struct string_list *sorted_list, int free_util); | |
211 | ||
e448fed8 | 212 | |
c455c87c | 213 | /* Use these functions only on unsorted lists: */ |
e448fed8 | 214 | |
4f665f2c | 215 | /** |
e448fed8 MH |
216 | * Add string to the end of list. If list->strdup_string is set, then |
217 | * string is copied; otherwise the new string_list_entry refers to the | |
218 | * input string. | |
219 | */ | |
1d2f80fa | 220 | struct string_list_item *string_list_append(struct string_list *list, const char *string); |
e448fed8 | 221 | |
4f665f2c | 222 | /** |
e448fed8 MH |
223 | * Like string_list_append(), except string is never copied. When |
224 | * list->strdup_strings is set, this function can be used to hand | |
225 | * ownership of a malloc()ed string to list without making an extra | |
226 | * copy. | |
227 | */ | |
228 | struct string_list_item *string_list_append_nodup(struct string_list *list, char *string); | |
229 | ||
4f665f2c | 230 | /** |
065027ee EN |
231 | * Sort the list's entries by string value in order specified by list->cmp |
232 | * (strcmp() if list->cmp is NULL). | |
4f665f2c | 233 | */ |
3383e199 | 234 | void string_list_sort(struct string_list *list); |
4f665f2c HWN |
235 | |
236 | /** | |
237 | * Like `string_list_has_string()` but for unsorted lists. Linear in | |
238 | * size of the list. | |
239 | */ | |
c455c87c | 240 | int unsorted_string_list_has_string(struct string_list *list, const char *string); |
4f665f2c HWN |
241 | |
242 | /** | |
243 | * Like `string_list_lookup()` but for unsorted lists. Linear in size | |
244 | * of the list. | |
245 | */ | |
e2421480 SB |
246 | struct string_list_item *unsorted_string_list_lookup(struct string_list *list, |
247 | const char *string); | |
4f665f2c HWN |
248 | /** |
249 | * Remove an item from a string_list. The `string` pointer of the | |
250 | * items will be freed in case the `strdup_strings` member of the | |
251 | * string_list is set. The third parameter controls if the `util` | |
252 | * pointer of the items should be freed or not. | |
253 | */ | |
86d4b528 | 254 | void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util); |
ff919f96 | 255 | |
4f665f2c HWN |
256 | /** |
257 | * Split string into substrings on character `delim` and append the | |
258 | * substrings to `list`. The input string is not modified. | |
ff919f96 MH |
259 | * list->strdup_strings must be set, as new memory needs to be |
260 | * allocated to hold the substrings. If maxsplit is non-negative, | |
261 | * then split at most maxsplit times. Return the number of substrings | |
262 | * appended to list. | |
263 | * | |
264 | * Examples: | |
265 | * string_list_split(l, "foo:bar:baz", ':', -1) -> ["foo", "bar", "baz"] | |
266 | * string_list_split(l, "foo:bar:baz", ':', 0) -> ["foo:bar:baz"] | |
267 | * string_list_split(l, "foo:bar:baz", ':', 1) -> ["foo", "bar:baz"] | |
268 | * string_list_split(l, "foo:bar:", ':', -1) -> ["foo", "bar", ""] | |
269 | * string_list_split(l, "", ':', -1) -> [""] | |
270 | * string_list_split(l, ":", ':', -1) -> ["", ""] | |
271 | */ | |
272 | int string_list_split(struct string_list *list, const char *string, | |
273 | int delim, int maxsplit); | |
274 | ||
275 | /* | |
276 | * Like string_list_split(), except that string is split in-place: the | |
277 | * delimiter characters in string are overwritten with NULs, and the | |
278 | * new string_list_items point into string (which therefore must not | |
279 | * be modified or freed while the string_list is in use). | |
280 | * list->strdup_strings must *not* be set. | |
281 | */ | |
282 | int string_list_split_in_place(struct string_list *list, char *string, | |
52acddf3 | 283 | const char *delim, int maxsplit); |
0afcb5f7 | 284 | #endif /* STRING_LIST_H */ |