test-string-list.c: Fix some sparse warnings
[git/git.git] / Documentation / technical / api-string-list.txt
CommitLineData
c455c87c
JS
1string-list API
2===============
3
4The string_list API offers a data structure and functions to handle sorted
5and unsorted string lists.
6
7The 'string_list' struct used to be called 'path_list', but was renamed
8because it is not specific to paths.
9
10The 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+
19If you need something advanced, you can manually malloc() the `items`
20member (you need this if you add things later) and you should set the
21`nr` and `alloc` members in that case, too.
22
e448fed8 23. Adds new items to the list, using `string_list_append`,
ff919f96
MH
24 `string_list_append_nodup`, `string_list_insert`,
25 `string_list_split`, and/or `string_list_split_in_place`.
c455c87c
JS
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
31d5451e
MH
33. Can remove duplicate items from a sorted list using
34 `string_list_remove_duplicates`.
35
86d4b528
JS
36. Can remove individual items of an unsorted list using
37 `unsorted_string_list_delete_item`.
38
eb5f0c7a
MH
39. Can remove items not matching a criterion from a sorted or unsorted
40 list using `filter_string_list`.
41
c455c87c
JS
42. Finally it should free the list using `string_list_clear`.
43
44Example:
45
46----
51f3145c 47struct string_list list = STRING_LIST_INIT_NODUP;
c455c87c
JS
48int i;
49
1d2f80fa
JP
50string_list_append(&list, "foo");
51string_list_append(&list, "bar");
c455c87c 52for (i = 0; i < list.nr; i++)
0dda1d1e 53 printf("%s\n", list.items[i].string)
c455c87c
JS
54----
55
56NOTE: It is more efficient to build an unsorted list and sort it
57afterwards, instead of building a sorted list (`O(n log n)` instead of
58`O(n^2)`).
59+
60However, if you use the list to check if a certain string was added
61already, you should not do that (using unsorted_string_list_has_string()),
62because the complexity would be quadratic again (but with a worse factor).
63
64Functions
65---------
66
67* General ones (works with sorted and unsorted lists as well)
68
eb5f0c7a
MH
69`filter_string_list`::
70
71 Apply a function to each item in a list, retaining only the
72 items for which the function returns true. If free_util is
73 true, call free() on the util members of any items that have
74 to be deleted. Preserve the order of the items that are
75 retained.
76
f103f95b
MH
77`string_list_longest_prefix`::
78
79 Return the longest string within a string_list that is a
80 prefix (in the sense of prefixcmp()) of the specified string,
81 or NULL if no such prefix exists. This function does not
82 require the string_list to be sorted (it does a linear
83 search).
84
c455c87c
JS
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
b8939b2b
HV
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.
c455c87c
JS
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
31d5451e
MH
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
c455c87c
JS
127* Functions for unsorted lists only
128
129`string_list_append`::
130
e448fed8
MH
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.
c455c87c
JS
143
144`sort_string_list`::
145
146 Make an unsorted list sorted.
147
148`unsorted_string_list_has_string`::
149
150 It's like `string_list_has_string()` but for unsorted lists.
e2421480
SB
151
152`unsorted_string_list_lookup`::
153
154 It's like `string_list_lookup()` but for unsorted lists.
c455c87c 155+
e2421480 156The above two functions need to look through all items, as opposed to their
c455c87c
JS
157counterpart for sorted lists, which performs a binary search.
158
86d4b528
JS
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
ff919f96
MH
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
c455c87c
JS
185Data structures
186---------------
187
188* `struct string_list_item`
189
0dda1d1e 190Represents an item of the list. The `string` member is a pointer to the
c455c87c
JS
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.