Documentation / technical / api-string-list.txton commit rev-list: disable object/refname ambiguity check with --stdin (4c30d50)
   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`print_string_list`::
  86
  87        Dump a string_list to stdout, useful mainly for debugging purposes. It
  88        can take an optional header argument and it writes out the
  89        string-pointer pairs of the string_list, each one in its own line.
  90
  91`string_list_clear`::
  92
  93        Free a string_list. The `string` pointer of the items will be freed in
  94        case the `strdup_strings` member of the string_list is set. The second
  95        parameter controls if the `util` pointer of the items should be freed
  96        or not.
  97
  98* Functions for sorted lists only
  99
 100`string_list_has_string`::
 101
 102        Determine if the string_list has a given string or not.
 103
 104`string_list_insert`::
 105
 106        Insert a new element to the string_list. The returned pointer can be
 107        handy if you want to write something to the `util` pointer of the
 108        string_list_item containing the just added string. If the given
 109        string already exists the insertion will be skipped and the
 110        pointer to the existing item returned.
 111+
 112Since this function uses xrealloc() (which die()s if it fails) if the
 113list needs to grow, it is safe not to check the pointer. I.e. you may
 114write `string_list_insert(...)->util = ...;`.
 115
 116`string_list_lookup`::
 117
 118        Look up a given string in the string_list, returning the containing
 119        string_list_item. If the string is not found, NULL is returned.
 120
 121`string_list_remove_duplicates`::
 122
 123        Remove all but the first of consecutive entries that have the
 124        same string value.  If free_util is true, call free() on the
 125        util members of any items that have to be deleted.
 126
 127* Functions for unsorted lists only
 128
 129`string_list_append`::
 130
 131        Append a new string to the end of the string_list.  If
 132        `strdup_string` is set, then the string argument is copied;
 133        otherwise the new `string_list_entry` refers to the input
 134        string.
 135
 136`string_list_append_nodup`::
 137
 138        Append a new string to the end of the string_list.  The new
 139        `string_list_entry` always refers to the input string, even if
 140        `strdup_string` is set.  This function can be used to hand
 141        ownership of a malloc()ed string to a `string_list` that has
 142        `strdup_string` set.
 143
 144`sort_string_list`::
 145
 146        Sort the list's entries by string value in `strcmp()` order.
 147
 148`unsorted_string_list_has_string`::
 149
 150        It's like `string_list_has_string()` but for unsorted lists.
 151
 152`unsorted_string_list_lookup`::
 153
 154        It's like `string_list_lookup()` but for unsorted lists.
 155+
 156The above two functions need to look through all items, as opposed to their
 157counterpart for sorted lists, which performs a binary search.
 158
 159`unsorted_string_list_delete_item`::
 160
 161        Remove an item from a string_list. The `string` pointer of the items
 162        will be freed in case the `strdup_strings` member of the string_list
 163        is set. The third parameter controls if the `util` pointer of the
 164        items should be freed or not.
 165
 166`string_list_split`::
 167`string_list_split_in_place`::
 168
 169        Split a string into substrings on a delimiter character and
 170        append the substrings to a `string_list`.  If `maxsplit` is
 171        non-negative, then split at most `maxsplit` times.  Return the
 172        number of substrings appended to the list.
 173+
 174`string_list_split` requires a `string_list` that has `strdup_strings`
 175set to true; it leaves the input string untouched and makes copies of
 176the substrings in newly-allocated memory.
 177`string_list_split_in_place` requires a `string_list` that has
 178`strdup_strings` set to false; it splits the input string in place,
 179overwriting the delimiter characters with NULs and creating new
 180string_list_items that point into the original string (the original
 181string must therefore not be modified or freed while the `string_list`
 182is in use).
 183
 184
 185Data structures
 186---------------
 187
 188* `struct string_list_item`
 189
 190Represents an item of the list. The `string` member is a pointer to the
 191string, and you may use the `util` member for any purpose, if you want.
 192
 193* `struct string_list`
 194
 195Represents the list itself.
 196
 197. The array of items are available via the `items` member.
 198. The `nr` member contains the number of items stored in the list.
 199. The `alloc` member is used to avoid reallocating at every insertion.
 200  You should not tamper with it.
 201. Setting the `strdup_strings` member to 1 will strdup() the strings
 202  before adding them, see above.