]>
Commit | Line | Data |
---|---|---|
c455c87c JS |
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` or | |
24 | `string_list_insert`. | |
25 | ||
26 | . Can check if a string is in the list using `string_list_has_string` or | |
27 | `unsorted_string_list_has_string` and get it from the list using | |
28 | `string_list_lookup` for sorted lists. | |
29 | ||
30 | . Can sort an unsorted list using `sort_string_list`. | |
31 | ||
86d4b528 JS |
32 | . Can remove individual items of an unsorted list using |
33 | `unsorted_string_list_delete_item`. | |
34 | ||
c455c87c JS |
35 | . Finally it should free the list using `string_list_clear`. |
36 | ||
37 | Example: | |
38 | ||
39 | ---- | |
40 | struct string_list list; | |
41 | int i; | |
42 | ||
43 | memset(&list, 0, sizeof(struct string_list)); | |
1d2f80fa JP |
44 | string_list_append(&list, "foo"); |
45 | string_list_append(&list, "bar"); | |
c455c87c | 46 | for (i = 0; i < list.nr; i++) |
0dda1d1e | 47 | printf("%s\n", list.items[i].string) |
c455c87c JS |
48 | ---- |
49 | ||
50 | NOTE: It is more efficient to build an unsorted list and sort it | |
51 | afterwards, instead of building a sorted list (`O(n log n)` instead of | |
52 | `O(n^2)`). | |
53 | + | |
54 | However, if you use the list to check if a certain string was added | |
55 | already, you should not do that (using unsorted_string_list_has_string()), | |
56 | because the complexity would be quadratic again (but with a worse factor). | |
57 | ||
58 | Functions | |
59 | --------- | |
60 | ||
61 | * General ones (works with sorted and unsorted lists as well) | |
62 | ||
63 | `print_string_list`:: | |
64 | ||
65 | Dump a string_list to stdout, useful mainly for debugging purposes. It | |
66 | can take an optional header argument and it writes out the | |
67 | string-pointer pairs of the string_list, each one in its own line. | |
68 | ||
69 | `string_list_clear`:: | |
70 | ||
71 | Free a string_list. The `string` pointer of the items will be freed in | |
72 | case the `strdup_strings` member of the string_list is set. The second | |
73 | parameter controls if the `util` pointer of the items should be freed | |
74 | or not. | |
75 | ||
76 | * Functions for sorted lists only | |
77 | ||
78 | `string_list_has_string`:: | |
79 | ||
80 | Determine if the string_list has a given string or not. | |
81 | ||
82 | `string_list_insert`:: | |
83 | ||
84 | Insert a new element to the string_list. The returned pointer can be | |
85 | handy if you want to write something to the `util` pointer of the | |
86 | string_list_item containing the just added string. | |
87 | + | |
88 | Since this function uses xrealloc() (which die()s if it fails) if the | |
89 | list needs to grow, it is safe not to check the pointer. I.e. you may | |
90 | write `string_list_insert(...)->util = ...;`. | |
91 | ||
92 | `string_list_lookup`:: | |
93 | ||
94 | Look up a given string in the string_list, returning the containing | |
95 | string_list_item. If the string is not found, NULL is returned. | |
96 | ||
97 | * Functions for unsorted lists only | |
98 | ||
99 | `string_list_append`:: | |
100 | ||
101 | Append a new string to the end of the string_list. | |
102 | ||
103 | `sort_string_list`:: | |
104 | ||
105 | Make an unsorted list sorted. | |
106 | ||
107 | `unsorted_string_list_has_string`:: | |
108 | ||
109 | It's like `string_list_has_string()` but for unsorted lists. | |
e2421480 SB |
110 | |
111 | `unsorted_string_list_lookup`:: | |
112 | ||
113 | It's like `string_list_lookup()` but for unsorted lists. | |
c455c87c | 114 | + |
e2421480 | 115 | The above two functions need to look through all items, as opposed to their |
c455c87c JS |
116 | counterpart for sorted lists, which performs a binary search. |
117 | ||
86d4b528 JS |
118 | `unsorted_string_list_delete_item`:: |
119 | ||
120 | Remove an item from a string_list. The `string` pointer of the items | |
121 | will be freed in case the `strdup_strings` member of the string_list | |
122 | is set. The third parameter controls if the `util` pointer of the | |
123 | items should be freed or not. | |
124 | ||
c455c87c JS |
125 | Data structures |
126 | --------------- | |
127 | ||
128 | * `struct string_list_item` | |
129 | ||
0dda1d1e | 130 | Represents an item of the list. The `string` member is a pointer to the |
c455c87c JS |
131 | string, and you may use the `util` member for any purpose, if you want. |
132 | ||
133 | * `struct string_list` | |
134 | ||
135 | Represents the list itself. | |
136 | ||
137 | . The array of items are available via the `items` member. | |
138 | . The `nr` member contains the number of items stored in the list. | |
139 | . The `alloc` member is used to avoid reallocating at every insertion. | |
140 | You should not tamper with it. | |
141 | . Setting the `strdup_strings` member to 1 will strdup() the strings | |
142 | before adding them, see above. |