The string_list API offers a data structure and functions to handle sorted and unsorted string lists.

The string_list struct used to be called path_list, but was renamed because it is not specific to paths.

The caller:

  1. Allocates and clears a struct string_list variable.

  2. Initializes the members. You might want to set the flag strdup_strings if the strings should be strdup()ed. For example, this is necessary when you add something like git_path("…"), since that function returns a static buffer that will change with the next call to git_path().

    If you need something advanced, you can manually malloc() the items member (you need this if you add things later) and you should set the nr and alloc members in that case, too.

  3. Adds new items to the list, using string_list_append or string_list_insert.

  4. Can check if a string is in the list using string_list_has_string or unsorted_string_list_has_string and get it from the list using string_list_lookup for sorted lists.

  5. Can sort an unsorted list using sort_string_list.

  6. Can remove individual items of an unsorted list using unsorted_string_list_delete_item.

  7. Finally it should free the list using string_list_clear.

Example:

struct string_list list;
int i;

memset(&list, 0, sizeof(struct string_list));
string_list_append(&list, "foo");
string_list_append(&list, "bar");
for (i = 0; i < list.nr; i++)
        printf("%s\n", list.items[i].string)
Note
 It is more efficient to build an unsorted list and sort it afterwards, instead of building a sorted list (O(n log n) instead of O(n^2)).

+ However, if you use the list to check if a certain string was added already, you should not do that (using unsorted_string_list_has_string()), because the complexity would be quadratic again (but with a worse factor).

Functions

  • General ones (works with sorted and unsorted lists as well)

    print_string_list

    Dump a string_list to stdout, useful mainly for debugging purposes. It can take an optional header argument and it writes out the string-pointer pairs of the string_list, each one in its own line.

    string_list_clear

    Free a string_list. The string pointer of the items will be freed in case the strdup_strings member of the string_list is set. The second parameter controls if the util pointer of the items should be freed or not.

  • Functions for sorted lists only

    string_list_has_string

    Determine if the string_list has a given string or not.

    string_list_insert

    Insert a new element to the string_list. The returned pointer can be handy if you want to write something to the util pointer of the string_list_item containing the just added string. If the given string already exists the insertion will be skipped and the pointer to the existing item returned.

    Since this function uses xrealloc() (which die()s if it fails) if the list needs to grow, it is safe not to check the pointer. I.e. you may write string_list_insert(...)->util = ...;.

    string_list_lookup

    Look up a given string in the string_list, returning the containing string_list_item. If the string is not found, NULL is returned.

  • Functions for unsorted lists only

    string_list_append

    Append a new string to the end of the string_list.

    sort_string_list

    Make an unsorted list sorted.

    unsorted_string_list_has_string

    It’s like string_list_has_string() but for unsorted lists.

    unsorted_string_list_lookup

    It’s like string_list_lookup() but for unsorted lists.

    The above two functions need to look through all items, as opposed to their counterpart for sorted lists, which performs a binary search.

    unsorted_string_list_delete_item

    Remove an item from a string_list. The string pointer of the items will be freed in case the strdup_strings member of the string_list is set. The third parameter controls if the util pointer of the items should be freed or not.

Data structures

  • struct string_list_item

Represents an item of the list. The string member is a pointer to the string, and you may use the util member for any purpose, if you want.

  • struct string_list

Represents the list itself.

  1. The array of items are available via the items member.

  2. The nr member contains the number of items stored in the list.

  3. The alloc member is used to avoid reallocating at every insertion. You should not tamper with it.

  4. Setting the strdup_strings member to 1 will strdup() the strings before adding them, see above.