git.oblomov.eu Git - git/blob - Documentation/technical/api-string-list.txt

   1 string-list API
   2 ===============
   3
   4 The string_list API offers a data structure and functions to handle sorted
   5 and unsorted string lists.
   6
   7 The 'string_list' struct used to be called 'path_list', but was renamed
   8 because it is not specific to paths.
   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 `sort_string_list`.
  32
  33 . Can remove individual items of an unsorted list using
  34   `unsorted_string_list_delete_item`.
  35
  36 . Can remove items not matching a criterion from a sorted or unsorted
  37   list using `filter_string_list`.
  38
  39 . Finally it should free the list using `string_list_clear`.
  40
  41 Example:
  42
  43 ----
  44 struct string_list list;
  45 int i;
  46
  47 memset(&list, 0, sizeof(struct string_list));
  48 string_list_append(&list, "foo");
  49 string_list_append(&list, "bar");
  50 for (i = 0; i < list.nr; i++)
  51         printf("%s\n", list.items[i].string)
  52 ----
  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 Functions
  63 ---------
  64
  65 * General ones (works with sorted and unsorted lists as well)
  66
  67 `filter_string_list`::
  68
  69         Apply a function to each item in a list, retaining only the
  70         items for which the function returns true.  If free_util is
  71         true, call free() on the util members of any items that have
  72         to be deleted.  Preserve the order of the items that are
  73         retained.
  74
  75 `print_string_list`::
  76
  77         Dump a string_list to stdout, useful mainly for debugging purposes. It
  78         can take an optional header argument and it writes out the
  79         string-pointer pairs of the string_list, each one in its own line.
  80
  81 `string_list_clear`::
  82
  83         Free a string_list. The `string` pointer of the items will be freed in
  84         case the `strdup_strings` member of the string_list is set. The second
  85         parameter controls if the `util` pointer of the items should be freed
  86         or not.
  87
  88 * Functions for sorted lists only
  89
  90 `string_list_has_string`::
  91
  92         Determine if the string_list has a given string or not.
  93
  94 `string_list_insert`::
  95
  96         Insert a new element to the string_list. The returned pointer can be
  97         handy if you want to write something to the `util` pointer of the
  98         string_list_item containing the just added string. If the given
  99         string already exists the insertion will be skipped and the
 100         pointer to the existing item returned.
 101 +
 102 Since this function uses xrealloc() (which die()s if it fails) if the
 103 list needs to grow, it is safe not to check the pointer. I.e. you may
 104 write `string_list_insert(...)->util = ...;`.
 105
 106 `string_list_lookup`::
 107
 108         Look up a given string in the string_list, returning the containing
 109         string_list_item. If the string is not found, NULL is returned.
 110
 111 * Functions for unsorted lists only
 112
 113 `string_list_append`::
 114
 115         Append a new string to the end of the string_list.  If
 116         `strdup_string` is set, then the string argument is copied;
 117         otherwise the new `string_list_entry` refers to the input
 118         string.
 119
 120 `string_list_append_nodup`::
 121
 122         Append a new string to the end of the string_list.  The new
 123         `string_list_entry` always refers to the input string, even if
 124         `strdup_string` is set.  This function can be used to hand
 125         ownership of a malloc()ed string to a `string_list` that has
 126         `strdup_string` set.
 127
 128 `sort_string_list`::
 129
 130         Make an unsorted list sorted.
 131
 132 `unsorted_string_list_has_string`::
 133
 134         It's like `string_list_has_string()` but for unsorted lists.
 135
 136 `unsorted_string_list_lookup`::
 137
 138         It's like `string_list_lookup()` but for unsorted lists.
 139 +
 140 The above two functions need to look through all items, as opposed to their
 141 counterpart for sorted lists, which performs a binary search.
 142
 143 `unsorted_string_list_delete_item`::
 144
 145         Remove an item from a string_list. The `string` pointer of the items
 146         will be freed in case the `strdup_strings` member of the string_list
 147         is set. The third parameter controls if the `util` pointer of the
 148         items should be freed or not.
 149
 150 `string_list_split`::
 151 `string_list_split_in_place`::
 152
 153         Split a string into substrings on a delimiter character and
 154         append the substrings to a `string_list`.  If `maxsplit` is
 155         non-negative, then split at most `maxsplit` times.  Return the
 156         number of substrings appended to the list.
 157 +
 158 `string_list_split` requires a `string_list` that has `strdup_strings`
 159 set to true; it leaves the input string untouched and makes copies of
 160 the substrings in newly-allocated memory.
 161 `string_list_split_in_place` requires a `string_list` that has
 162 `strdup_strings` set to false; it splits the input string in place,
 163 overwriting the delimiter characters with NULs and creating new
 164 string_list_items that point into the original string (the original
 165 string must therefore not be modified or freed while the `string_list`
 166 is in use).
 167
 168
 169 Data structures
 170 ---------------
 171
 172 * `struct string_list_item`
 173
 174 Represents an item of the list. The `string` member is a pointer to the
 175 string, and you may use the `util` member for any purpose, if you want.
 176
 177 * `struct string_list`
 178
 179 Represents the list itself.
 180
 181 . The array of items are available via the `items` member.
 182 . The `nr` member contains the number of items stored in the list.
 183 . The `alloc` member is used to avoid reallocating at every insertion.
 184   You should not tamper with it.
 185 . Setting the `strdup_strings` member to 1 will strdup() the strings
 186   before adding them, see above.