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