Prefix tables

Submitted by raevnos on Thu, 2007-05-24 17:03

Prefix tables, aka ptabs, are a (string key,value) lookup structure used to find the entry for a name that is the unique prefix of a key in the table. For example, they're used by @set for flag names so that you don't have to get the full name of the flag.

API

To use a ptab, #include "ptab.h" if it isn't already in the source file. Prefix tables then can be declare using the PTAB type.

For example:
PTAB ptab_sample;

Before using any other functions on a new ptab, it must be initialized, with ptab_init(), which takes a pointer to a PTAB as its argument. Unless otherwise mentioned, all ptab functions take a pointer to a PTAB as their first argument.

Example:
ptab_init(&ptab_sample);

When done with the table, call ptab_free() to release allocated memory:

ptab_free(&ptab_sample);

Before looking up anything, you have to add (key,value) tuples to the table. There are three steps involved in this. First, you have to call ptab_start_inserts(), then add new entries with ptab_insert(ptab, key, data). Once done inserting items, call ptab_end_inserts(). You can only insert items between a start/end; lookups are disallowed.

Example:


ptab_start_inserts(&ptab_sample);
for (n = 0; n < initarray_size; n++) {
ptab_insert(&ptab_sample, initarray[n].key,
initarray[n].value);
}
ptab_end_inserts(&ptab_sample);

With version 1.8.3p3 and later, you can use ptab_insert_one() to insert a single new item. It's better to use ptab_insert() when inserting multiple entries at one time.

Example:
ptab_insert_one(&ptab_sample, "I AM A UNIQUE PREFIX", &stdin);

You can look up an entry with ptab_find(). If an entry matching the given key is found, that element's data pointer is returned. If it's not found or there are more than one keys with the given lookup key as a prefix, NULL is returned. Note that this means that if you use a NULL data pointer, there is no way to tell it apart from a failed lookup.

Example:
data = ptab_find(&ptab_sample, "I AM A");

You can also do a lookup testing for an exact match only with ptab_find_exact():

data = ptab_find_exact(&ptab_sample, "I AM A UNIQUE PREFIX");

Delete entries from a table with ptab_delete(). The key must be an exact match, and no cleanup is done of the data pointer. If it needs to be freed, that has to be done first.

Example:
ptab_delete(&ptab_sample, "I AM A UNIQUE PREFIX");

Finally, you can iterate through all entries in a table with the ptab_firstentry_new() and ptab_nextentry_new() functions. The former returns the data of the first element, and the latter subsequent data. It returns NULL once all elements have been returned. The second argument to each, if non-NULL, must be large enough to hold the longest key in the table. If you don't care about the key, use ptab_firstentry() and ptab_nextentry().

Internals
Internally, ptabs are implemented as a sorted array. Exact lookups are done with a binary search and thus have a O(log N) performance. Prefix lookups use a modified binary search that finds the first entry with a prefix of the lookup key and checks the elements before and after. to see if it's unique.

When new entries are added, the key (A string) is copied. The calling function can safely free the memory used as the key argument if needed. The data pointer is merely stored.

ptab_start_inserts() marks the table as being unsorted. ptab_insert() adds new elements to the end of the array, and ptab_end_inserts() sorts it again. ptab_insert_one() does a single insertion into the proper place in the table.

See the documentation of ptab.c for more information.