+++ /dev/null
-.\" -*-nroff-*-
-.de VS
-.sp 1
-.RS
-.nf
-.ft B
-..
-.de VE
-.ft R
-.fi
-.RE
-.sp 1
-..
-.de hP
-.IP
-.ft B
-\h'-\w'\\$1\ 'u'\\$1\ \c
-.ft P
-..
-.ie t .ds o \(bu
-.el .ds o o
-.TH hash 3 "2 August 1999" "Straylight/Edgeware" "mLib utilities library"
-.SH "NAME"
-hash \- low-level hashtable implementation
-.\" @hash_create
-.\" @hash_destroy
-.\" @hash_bin
-.\" @hash_extend
-.\" @hash_remove
-.\" @hash_mkiter
-.\" @hash_next
-.\"
-.\" @HASH_BIN
-.\" @HASH_MKITER
-.\" @HASH_NEXT
-.\"
-.SH "SYNOPSIS"
-.nf
-.B "#include <mLib/hash.h>"
-
-.BI "void hash_create(hash_table *" t ", size_t " n );
-.BI "void hash_destroy(hash_table *" t );
-.BI "hash_base **hash_bin(hash_table *" t ", uint32 " hash );
-.BI "int hash_extend(hash_table *" t );
-.BI "void hash_remove(hash_table *" t ", hash_base * " b );
-.BI "void hash_mkiter(hash_iter *" i ", hash_table *" t );
-.BI "hash_base *hash_next(hash_iter *" i );
-
-.BI "hash_base **HASH_BIN(hash_table *" t ", uint32 " hash );
-.BI "void HASH_MKITER(hash_iter *" i ", hash_table *" t );
-.BI "void HASH_NEXT(hash_iter *" i ", " b );
-.fi
-.SH "OVERVIEW"
-The
-.B hash
-functions provide the basis for an extensible hashtable implementation.
-The implementation is not complete. Many decisions have been left to
-the user, including:
-.hP \*o
-how keys should be represented, hashed and compared;
-.hP \*o
-how objects contained within the table should be allocated; and
-.hP \*o
-when the hashtable should be extended.
-.PP
-A complete hashtable implementation will need to take the above
-decisions. If you just want a prepackaged solution, see
-.BR sym (3)
-which provides one.
-.SH "IMPLEMENTATION DETAILS"
-Each item in the hashtable is assigned a 32-bit integer
-.IR hash :
-a number computed somehow from the item's data such that two items which
-are considered equal will yield the same hash. Ideally, different items
-will yield different hashes. It is important for this implementation
-that all bits of the hash are similarly good.
-.PP
-In order to look up an item, the high bits of the hash are masked off
-and the remainder used as an index into a vector of
-.IR "bin lists" .
-Each bin contains a list of items with identical low-order bits of their
-hashes.
-.PP
-A table expansion involves doubling the size of the bin vector. Each
-bin list is then split into two, items being placed into a new bin
-depending on the setting of the next lowest hash bit. By expanding the
-hashtable as needed, lookups remain constant-time.
-.PP
-A low-level hashtable is represented by a
-.B hash_table
-structure. It contains two members:
-.TP
-.B "uint32 mask"
-The current bitmask to be applied to hashes. This is one less than the
-current number of bins in the hashtable, and is applied to hash values
-in order to decide which bin an item should be in.
-.TP
-.B "hash_base **v"
-The bin vector. It is an array of pointers to hashtable items.
-.PP
-A hashtable item consists of a
-.B hash_base
-structure. A full hashtable implementation will need to extend this
-structure by adding keying information and other data; the
-.B hash_base
-only contains the bare minimum of information needed to maintain the
-hashtable at a low level. It contains the following members:
-.TP
-.B "hash_base *next"
-Pointer to the next item in the bin list. The final item has a null
-.B next
-pointer. The entry in the bin vector is null if the bin list is empty.
-It is up to the high-level implementation to insert items into the list.
-.TP
-.B "uint32 hash"
-The hash for this item. This must be the full 32-bit hash for the
-current item. It is used during hashtable expansion to determine which
-bin an item should be moved to.
-.SH "FUNCTIONALITY PROVIDED"
-This section describes the functions and macros provided for building
-hashtables. Code examples are given throughout. They assume the
-following definitions:
-.VS
-/* --- A table of items --- */
-
-typedef struct item_table {
- hash_table t;
- size_t load;
-};
-
-/* --- An item --- */
-
-typedef struct item {
- hash_base b;
- const char *k;
- /* ... */
-} item;
-.VE
-The implementation presented here is simple but relatively bad. The
-source file
-.B sym.c
-presents a more realistic example, but is rather more complex.
-.SS "Initialization and finalization"
-An empty hashtable is initialized by calling
-.B hash_create
-with the address of a
-.B hash_table
-structure to be filled in and the initial number of hash bins to create.
-.PP
-For example, an item table might be initialized like this:
-.VS
-void item_createtab(item_table *t)
-{
- hash_create(&t->t, ITEM_INITSZ);
- t->load = ITEM_INITLOAD;
-}
-.VE
-A hashtable can be destroyed by calling
-.B hash_destroy
-with the address of the
-.B hash_table
-structure. This does not attempt to deallocate the individual items;
-that must be done beforehand.
-.PP
-The usual way to deallocate the individual hashtable items is using the
-iteration constructs described below.
-.VS
-void item_destroytab(item_table *t)
-{
- hash_iter i;
- hash_base *b;
- for (hash_mkiter(&i, &t->t); (b = hash_next(&i)) != 0; ) {
- item *ii = (item *)b;
- free(ii->k);
- /* ... */
- DESTROY(ii);
- }
- hash_destroy(&t->t);
-}
-.VE
-.sp -1
-.SS "Searching, adding and removing"
-Items must be searched for and added by hand.
-.PP
-The macro
-.B HASH_BIN
-returns the address of the bin list haed for a particular hashtable and
-hash value. The function
-.B hash_bin
-works the same way and provides the same result, but since the macro is
-very simple its use is preferred. However, it will evaluate its
-arguments multiple times.
-.PP
-Once the bin list has been found, it's fairly easy to search for an
-exact match. A simple search might look something like this:
-.VS
-item *lookup(item_table *t, const char *k)
-{
- uint32 h = hash(k); /* Hash @k@ somehow */
- hash_base **bin = HASH_BIN(&t->t, h);
- hash_base *b;
- for (b = *bin; b; b = b->next) {
- item *i = (item *)b;
- if (h == i->b.hash && strcmp(k, i->k) == 0)
- return (i);
- }
- return (0);
-}
-.VE
-Insertion is also relatively trivial given the bin list head. Insertion
-may make the hashtable too large, so it might be necessary to extend
-it. Extension is performed by
-.BR hash_extend ,
-which is passed only the address of the hashtable. It returns nonzero
-if extension was successful.
-.VS
-item *add(item_table *t, const char *k, /* ... */)
-{
- item *i;
- uint32 h;
- hash_base **bin;
-
- /* --- See if the item is already there --- */
-
- if ((i = = lookup(t, k)) != 0)
- return (i);
-
- /* --- Make a new hashtable item --- */
-
- i = CREATE(item);
- i->k = xstrdup(k);
- /* ... */
-
- /* --- Link it into the bin list --- */
-
- h = i->b.hash = hash(k);
- bin = HASH_BIN(&t->t, h);
- i->b.next = *bin;
- *bin = &i->b.next;
-
- /* --- Maybe extend the hashtable --- */
-
- if (t->load)
- t->load--;
- else if (hash_extend(&t->t))
- t->load = recalc_load(t);
-
- /* --- Done --- */
-
- return (i);
-}
-.VE
-The
-.B sym
-implementation is rather more sophisticated in its approach but the idea
-is the same. In particular,
-.B sym
-provides a single interface for lookup and insertion which prevents the
-unnecessary rehashing performed by the above code.
-.PP
-Removal of items is more straightforward. The function
-.B hash_remove
-will unlink a given item from its bin list, after which point it is safe
-to remove.
-.SS "Iteration"
-Iteration allows code to be performed on all the items in a hashtable.
-This is done using an
-.I iterator
-object, represented by a
-.B hash_iter
-structure. An iterator is initialized by calling
-.BR hash_mkiter .
-Each call to
-.B hash_next
-yields a different item from the hashtable until there are none left, a
-condition signified by a null return value.
-.PP
-The macros
-.B HASH_MKITER
-and
-.B HASH_NEXT
-do the same jobs as the above functions. However,
-.B HASH_NEXT
-has a slightly bizarre argument passing convention: its second argument
-is an
-.I lvalue
-which is updated to contain the address of the next item.
-.PP
-The finalization code above contained an example of iteration.
-.SH "SEE ALSO"
-.BR sym (3),
-.BR mLib (3).
-.SH "AUTHOR"
-Mark Wooding, <mdw@distorted.org.uk>
~mdw / mLib / blobdiff