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