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