1string-list API 2=============== 3 4The string_list API offers a data structure and functions to handle 5sorted and unsorted string lists. A "sorted" list is one whose 6entries are sorted by string value in `strcmp()` order. 7 8The 'string_list' struct used to be called 'path_list', but was renamed 9because it is not specific to paths. 10 11The caller: 12 13. Allocates and clears a `struct string_list` variable. 14 15. Initializes the members. You might want to set the flag `strdup_strings` 16 if the strings should be strdup()ed. For example, this is necessary 17 when you add something like git_path("..."), since that function returns 18 a static buffer that will change with the next call to git_path(). 19+ 20If you need something advanced, you can manually malloc() the `items` 21member (you need this if you add things later) and you should set the 22`nr` and `alloc` members in that case, too. 23 24. Adds new items to the list, using `string_list_append`, 25 `string_list_append_nodup`, `string_list_insert`, 26 `string_list_split`, and/or `string_list_split_in_place`. 27 28. Can check if a string is in the list using `string_list_has_string` or 29 `unsorted_string_list_has_string` and get it from the list using 30 `string_list_lookup` for sorted lists. 31 32. Can sort an unsorted list using `sort_string_list`. 33 34. Can remove duplicate items from a sorted list using 35 `string_list_remove_duplicates`. 36 37. Can remove individual items of an unsorted list using 38 `unsorted_string_list_delete_item`. 39 40. Can remove items not matching a criterion from a sorted or unsorted 41 list using `filter_string_list`, or remove empty strings using 42 `string_list_remove_empty_items`. 43 44. Finally it should free the list using `string_list_clear`. 45 46Example: 47 48---- 49struct string_list list = STRING_LIST_INIT_NODUP; 50int i; 51 52string_list_append(&list, "foo"); 53string_list_append(&list, "bar"); 54for (i = 0; i < list.nr; i++) 55 printf("%s\n", list.items[i].string) 56---- 57 58NOTE: It is more efficient to build an unsorted list and sort it 59afterwards, instead of building a sorted list (`O(n log n)` instead of 60`O(n^2)`). 61+ 62However, if you use the list to check if a certain string was added 63already, you should not do that (using unsorted_string_list_has_string()), 64because the complexity would be quadratic again (but with a worse factor). 65 66Functions 67--------- 68 69* General ones (works with sorted and unsorted lists as well) 70 71`filter_string_list`:: 72 73 Apply a function to each item in a list, retaining only the 74 items for which the function returns true. If free_util is 75 true, call free() on the util members of any items that have 76 to be deleted. Preserve the order of the items that are 77 retained. 78 79`string_list_remove_empty_items`:: 80 81 Remove any empty strings from the list. If free_util is true, 82 call free() on the util members of any items that have to be 83 deleted. Preserve the order of the items that are retained. 84 85`string_list_longest_prefix`:: 86 87 Return the longest string within a string_list that is a 88 prefix (in the sense of prefixcmp()) of the specified string, 89 or NULL if no such prefix exists. This function does not 90 require the string_list to be sorted (it does a linear 91 search). 92 93`print_string_list`:: 94 95 Dump a string_list to stdout, useful mainly for debugging purposes. It 96 can take an optional header argument and it writes out the 97 string-pointer pairs of the string_list, each one in its own line. 98 99`string_list_clear`:: 100 101 Free a string_list. The `string` pointer of the items will be freed in 102 case the `strdup_strings` member of the string_list is set. The second 103 parameter controls if the `util` pointer of the items should be freed 104 or not. 105 106* Functions for sorted lists only 107 108`string_list_has_string`:: 109 110 Determine if the string_list has a given string or not. 111 112`string_list_insert`:: 113 114 Insert a new element to the string_list. The returned pointer can be 115 handy if you want to write something to the `util` pointer of the 116 string_list_item containing the just added string. If the given 117 string already exists the insertion will be skipped and the 118 pointer to the existing item returned. 119+ 120Since this function uses xrealloc() (which die()s if it fails) if the 121list needs to grow, it is safe not to check the pointer. I.e. you may 122write `string_list_insert(...)->util = ...;`. 123 124`string_list_lookup`:: 125 126 Look up a given string in the string_list, returning the containing 127 string_list_item. If the string is not found, NULL is returned. 128 129`string_list_remove_duplicates`:: 130 131 Remove all but the first of consecutive entries that have the 132 same string value. If free_util is true, call free() on the 133 util members of any items that have to be deleted. 134 135* Functions for unsorted lists only 136 137`string_list_append`:: 138 139 Append a new string to the end of the string_list. If 140 `strdup_string` is set, then the string argument is copied; 141 otherwise the new `string_list_entry` refers to the input 142 string. 143 144`string_list_append_nodup`:: 145 146 Append a new string to the end of the string_list. The new 147 `string_list_entry` always refers to the input string, even if 148 `strdup_string` is set. This function can be used to hand 149 ownership of a malloc()ed string to a `string_list` that has 150 `strdup_string` set. 151 152`sort_string_list`:: 153 154 Sort the list's entries by string value in `strcmp()` order. 155 156`unsorted_string_list_has_string`:: 157 158 It's like `string_list_has_string()` but for unsorted lists. 159 160`unsorted_string_list_lookup`:: 161 162 It's like `string_list_lookup()` but for unsorted lists. 163+ 164The above two functions need to look through all items, as opposed to their 165counterpart for sorted lists, which performs a binary search. 166 167`unsorted_string_list_delete_item`:: 168 169 Remove an item from a string_list. The `string` pointer of the items 170 will be freed in case the `strdup_strings` member of the string_list 171 is set. The third parameter controls if the `util` pointer of the 172 items should be freed or not. 173 174`string_list_split`:: 175`string_list_split_in_place`:: 176 177 Split a string into substrings on a delimiter character and 178 append the substrings to a `string_list`. If `maxsplit` is 179 non-negative, then split at most `maxsplit` times. Return the 180 number of substrings appended to the list. 181+ 182`string_list_split` requires a `string_list` that has `strdup_strings` 183set to true; it leaves the input string untouched and makes copies of 184the substrings in newly-allocated memory. 185`string_list_split_in_place` requires a `string_list` that has 186`strdup_strings` set to false; it splits the input string in place, 187overwriting the delimiter characters with NULs and creating new 188string_list_items that point into the original string (the original 189string must therefore not be modified or freed while the `string_list` 190is in use). 191 192 193Data structures 194--------------- 195 196* `struct string_list_item` 197 198Represents an item of the list. The `string` member is a pointer to the 199string, and you may use the `util` member for any purpose, if you want. 200 201* `struct string_list` 202 203Represents the list itself. 204 205. The array of items are available via the `items` member. 206. The `nr` member contains the number of items stored in the list. 207. The `alloc` member is used to avoid reallocating at every insertion. 208 You should not tamper with it. 209. Setting the `strdup_strings` member to 1 will strdup() the strings 210 before adding them, see above.