| 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 | size_t nr; |
| 90 | size_t alloc; |
| 91 | unsigned int strdup_strings:1; |
| 92 | compare_strings_fn cmp; /* NULL uses strcmp() */ |
| 93 | }; |
| 94 | |
| 95 | #define STRING_LIST_INIT_NODUP { 0 } |
| 96 | #define STRING_LIST_INIT_DUP { .strdup_strings = 1 } |
| 97 | |
| 98 | /* General functions which work with both sorted and unsorted lists. */ |
| 99 | |
| 100 | /** |
| 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 | |
| 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 | |
| 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 | */ |
| 126 | void string_list_clear(struct string_list *list, int free_util); |
| 127 | |
| 128 | /** |
| 129 | * Callback type for `string_list_clear_func`. The string associated |
| 130 | * with the util pointer is passed as the second argument |
| 131 | */ |
| 132 | typedef void (*string_list_clear_func_t)(void *p, const char *str); |
| 133 | |
| 134 | /** Call a custom clear function on each util pointer */ |
| 135 | void string_list_clear_func(struct string_list *list, string_list_clear_func_t clearfunc); |
| 136 | |
| 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 | |
| 147 | /** |
| 148 | * Apply `func` to each item. If `func` returns nonzero, the |
| 149 | * iteration aborts and the return value is propagated. |
| 150 | */ |
| 151 | int for_each_string_list(struct string_list *list, |
| 152 | string_list_each_func_t func, void *cb_data); |
| 153 | |
| 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 | */ |
| 160 | #define for_each_string_list_item(item,list) \ |
| 161 | for (item = (list)->items; \ |
| 162 | item && item < (list)->items + (list)->nr; \ |
| 163 | ++item) |
| 164 | |
| 165 | /** |
| 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 | |
| 172 | /* Use these functions only on sorted lists: */ |
| 173 | |
| 174 | /** Determine if the string_list has a given string or not. */ |
| 175 | bool string_list_has_string(const struct string_list *list, const char *string); |
| 176 | |
| 177 | /** |
| 178 | * Find the index at which a new element should be inserted into the |
| 179 | * string_list to maintain sorted order. If exact_match is not NULL, |
| 180 | * it will be set to true if the string already exists in the list. |
| 181 | */ |
| 182 | size_t string_list_find_insert_index(const struct string_list *list, const char *string, |
| 183 | bool *exact_match); |
| 184 | |
| 185 | /** |
| 186 | * Insert a new element to the string_list. The returned pointer can |
| 187 | * be handy if you want to write something to the `util` pointer of |
| 188 | * the string_list_item containing the just added string. If the given |
| 189 | * string already exists the insertion will be skipped and the pointer |
| 190 | * to the existing item returned. |
| 191 | * |
| 192 | * Since this function uses xrealloc() (which die()s if it fails) if the |
| 193 | * list needs to grow, it is safe not to check the pointer. I.e. you may |
| 194 | * write `string_list_insert(...)->util = ...;`. |
| 195 | */ |
| 196 | struct string_list_item *string_list_insert(struct string_list *list, const char *string); |
| 197 | |
| 198 | /** |
| 199 | * Remove the given string from the sorted list. If the string |
| 200 | * doesn't exist, the list is not altered. |
| 201 | */ |
| 202 | void string_list_remove(struct string_list *list, const char *string, |
| 203 | int free_util); |
| 204 | |
| 205 | /** |
| 206 | * Check if the given string is part of a sorted list. If it is part of the list, |
| 207 | * return the corresponding string_list_item, NULL otherwise. |
| 208 | */ |
| 209 | struct string_list_item *string_list_lookup(struct string_list *list, const char *string); |
| 210 | |
| 211 | /* |
| 212 | * Remove all but the first of consecutive entries with the same |
| 213 | * string value. If free_util is true, call free() on the util |
| 214 | * members of any items that have to be deleted. |
| 215 | */ |
| 216 | void string_list_remove_duplicates(struct string_list *sorted_list, int free_util); |
| 217 | |
| 218 | |
| 219 | /* Use these functions only on unsorted lists: */ |
| 220 | |
| 221 | /** |
| 222 | * Add string to the end of list. If list->strdup_string is set, then |
| 223 | * string is copied; otherwise the new string_list_entry refers to the |
| 224 | * input string. |
| 225 | */ |
| 226 | struct string_list_item *string_list_append(struct string_list *list, const char *string); |
| 227 | |
| 228 | /** |
| 229 | * Like string_list_append(), except string is never copied. When |
| 230 | * list->strdup_strings is set, this function can be used to hand |
| 231 | * ownership of a malloc()ed string to list without making an extra |
| 232 | * copy. |
| 233 | */ |
| 234 | struct string_list_item *string_list_append_nodup(struct string_list *list, char *string); |
| 235 | |
| 236 | /** |
| 237 | * Sort the list's entries by string value in order specified by list->cmp |
| 238 | * (strcmp() if list->cmp is NULL). |
| 239 | */ |
| 240 | void string_list_sort(struct string_list *list); |
| 241 | |
| 242 | /** |
| 243 | * Sort the list and then remove duplicate entries. If free_util is true, |
| 244 | * call free() on the util members of any items that have to be deleted. |
| 245 | */ |
| 246 | void string_list_sort_u(struct string_list *list, int free_util); |
| 247 | |
| 248 | /** |
| 249 | * Like `string_list_has_string()` but for unsorted lists. Linear in |
| 250 | * size of the list. |
| 251 | */ |
| 252 | int unsorted_string_list_has_string(struct string_list *list, const char *string); |
| 253 | |
| 254 | /** |
| 255 | * Like `string_list_lookup()` but for unsorted lists. Linear in size |
| 256 | * of the list. |
| 257 | */ |
| 258 | struct string_list_item *unsorted_string_list_lookup(struct string_list *list, |
| 259 | const char *string); |
| 260 | /** |
| 261 | * Remove an item from a string_list. The `string` pointer of the |
| 262 | * items will be freed in case the `strdup_strings` member of the |
| 263 | * string_list is set. The third parameter controls if the `util` |
| 264 | * pointer of the items should be freed or not. |
| 265 | */ |
| 266 | void unsorted_string_list_delete_item(struct string_list *list, int i, int free_util); |
| 267 | |
| 268 | /** |
| 269 | * Remove the first item matching `str` from an unsorted string_list. |
| 270 | * No-op if `str` is not found. If `free_util` is non-zero, the `util` |
| 271 | * pointer of the removed item is freed before deletion. |
| 272 | */ |
| 273 | void unsorted_string_list_remove(struct string_list *list, const char *str, |
| 274 | int free_util); |
| 275 | |
| 276 | /** |
| 277 | * Split string into substrings on characters in `delim` and append the |
| 278 | * substrings to `list`. The input string is not modified. |
| 279 | * list->strdup_strings must be set, as new memory needs to be |
| 280 | * allocated to hold the substrings. If maxsplit is non-negative, |
| 281 | * then split at most maxsplit times. Return the number of substrings |
| 282 | * appended to list. |
| 283 | * |
| 284 | * Examples: |
| 285 | * string_list_split(l, "foo:bar:baz", ":", -1) -> ["foo", "bar", "baz"] |
| 286 | * string_list_split(l, "foo:bar:baz", ":", 0) -> ["foo:bar:baz"] |
| 287 | * string_list_split(l, "foo:bar:baz", ":", 1) -> ["foo", "bar:baz"] |
| 288 | * string_list_split(l, "foo:bar:", ":", -1) -> ["foo", "bar", ""] |
| 289 | * string_list_split(l, "", ":", -1) -> [""] |
| 290 | * string_list_split(l, ":", ":", -1) -> ["", ""] |
| 291 | */ |
| 292 | int string_list_split(struct string_list *list, const char *string, |
| 293 | const char *delim, int maxsplit); |
| 294 | |
| 295 | /* |
| 296 | * Like string_list_split(), except that string is split in-place: the |
| 297 | * delimiter characters in string are overwritten with NULs, and the |
| 298 | * new string_list_items point into string (which therefore must not |
| 299 | * be modified or freed while the string_list is in use). |
| 300 | * list->strdup_strings must *not* be set. |
| 301 | */ |
| 302 | int string_list_split_in_place(struct string_list *list, char *string, |
| 303 | const char *delim, int maxsplit); |
| 304 | |
| 305 | /* Flag bits for split_f and split_in_place_f functions */ |
| 306 | enum { |
| 307 | /* |
| 308 | * trim whitespaces around resulting string piece before adding |
| 309 | * it to the list |
| 310 | */ |
| 311 | STRING_LIST_SPLIT_TRIM = (1 << 0), |
| 312 | /* omit adding empty string piece to the resulting list */ |
| 313 | STRING_LIST_SPLIT_NONEMPTY = (1 << 1), |
| 314 | }; |
| 315 | |
| 316 | int string_list_split_f(struct string_list *, const char *string, |
| 317 | const char *delim, int maxsplit, unsigned flags); |
| 318 | |
| 319 | int string_list_split_in_place_f(struct string_list *, char *string, |
| 320 | const char *delim, int maxsplit, unsigned flags); |
| 321 | #endif /* STRING_LIST_H */ |