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