Documentation/technical/api-path-list.txt

   1 path-list API
   2 =============
   3
   4 The path_list API offers a data structure and functions to handle sorted
   5 and unsorted string lists.
   6
   7 The name is a bit misleading, a path_list may store not only paths but
   8 strings in general.
   9
  10 The 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 +
  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 `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
  33 Example:
  34
  35 ----
  36 struct path_list list;
  37 int i;
  38
  39 memset(&list, 0, sizeof(struct path_list));
  40 path_list_append("foo", &list);
  41 path_list_append("bar", &list);
  42 for (i = 0; i < list.nr; i++)
  43         printf("%s\n", list.items[i].path)
  44 ----
  45
  46 NOTE: It is more efficient to build an unsorted list and sort it
  47 afterwards, instead of building a sorted list (`O(n log n)` instead of
  48 `O(n^2)`).
  49 +
  50 However, if you use the list to check if a certain string was added
  51 already, you should not do that (using unsorted_path_list_has_path()),
  52 because the complexity would be quadratic again (but with a worse factor).
  53
  54 Functions
  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 +
  83 Since this function uses xrealloc() (which die()s if it fails) if the
  84 list needs to grow, it is safe not to check the pointer. I.e. you may
  85 write `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 +
 106 This function needs to look through all items, as opposed to its
 107 counterpart for sorted lists, which performs a binary search.
 108
 109 Data structures
 110 ---------------
 111
 112 * `struct path_list_item`
 113
 114 Represents an item of the list. The `path` member is a pointer to the
 115 string, and you may use the `util` member for any purpose, if you want.
 116
 117 * `struct path_list`
 118
 119 Represents 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.