HASHTABLE(3)                                                      HASHTABLE(3)

       hashtable - keyed sets and maps

       #include "hashtable.h"
       #include "hashtable.c"

       struct hashtable *hashtable_new(unsigned size);
       void hashtable_delete(struct hashtable *table);

       struct hashtable *hashtable_initialise(struct hashtable *table);
       struct hashtable *hashtable_release(struct hashtable *table);

       struct hashtable_entry *hashtable_insert(struct hashtable *table,
           char *key, unsigned length);

       struct hashtable_entry *hashtable_find(struct hashtable *table,
           char *key);

       These  functions  provide hash tables that use the method of coalescing
       lists [1].  They are particularly suitable for building symbol tables.

       The hashtable_new() function allocates and  returns  a  pointer  to  an
       empty  hash  table  structure  that can contain size entries.  When the
       structure is no longer needed, the hashtable_delete() function  can  be
       used to destroy it.  Programs that want to allocate a hash table struc-
       ture in automatic or static storage can use  hashtable_initialise()  to
       prepare  it for use and subsequently hashtable_release() to reclaim any
       resources  it   has   used.    (The   functions   hashtable_new()   and
       hashtable_delete()  perform this initialisation and reclamation implic-

       The hashtable_insert() function creates a new entry in table  with  the
       given  key,  growing  the table to make room if necessary.  It does not
       check if an entry with the  key  already  exists  in  the  table.   The
       hashtable_find()  function  searches  table for an entry with the given
       key and returns a pointer to it, or null if no such entry exists.   The
       length  argument specifies the number of bytes in the key.  The default
       type of key is char * and the length should not include any  terminaing
       nul character.

       Two  data  structures are declared by the header file.  Several members
       of these structures are potentially useful to the client, as follows.

          struct hashtable_entry
            char     *hashtable_entry_key;
            unsigned  hashtable_entry_length;

          struct hashtable
            unsigned int             hashtable_capacity;
            struct hashtable_entry **hashtable_entries;

       The hashtable_entry_key and hashtable_entry_length are copies of  those
       provided  to  the  hashtable_insert function at the time when the entry
       was created.  The hashtable_capacity gives the size of (one  more  than
       the  maximum  valid  index  into)  hashtable_entries.   Each element of
       hashtable_entries is either null or  a  pointer  to  a  hashtable_entry

       The client must never modify the contents of these structures directly,
       with the exception of any additional members that were  added  to  them
       explicitly (see the next section).

       Programs  that  wish  only  to  manage a set of unique strings can just
       include hashtable.h to declare the API, and add hashtable.c to the list
       of source files.  The types and functions described in this manual will
       then be available.

       Simple customisation is possible by  defining  preprocessor  macros  to
       change default types and names.

              The  tag  given  to  the  hashtable  structure,  and  the prefix
              prepended to the hash table functions.  The  default  is  'hash-

              The  tag given to the hashtable entry structure.  The default is

              Additional members to be added to the hashtable structure.  They
              are  placed at the beginning of the structure and initialised to

              Additional members to be added to the hashtable entry structure.
              They  are  placed  at the beginning of the structure and will be
              initialised to zero.

       These symbols affect the  declarations  made  in  hashtable.h  and  the
       implementations  of  associated functions in hashtable.c.  The same set
       of definitions must be in effect when including  the  header  file  and
       compiling  the  source  file.   The  easiest  way  to ensure this is to
       include hashtable.c in the program after the necessary definitions.

       For example, the following  complete  program  tallies  the  number  of
       occurences of each unique word passed on the command line.

          #define HASHTABLE_NAME          SymbolTable
          #define HASHTABLE_ENTRY_NAME    Symbol
          #define HASHTABLE_ENTRY_MEMBERS int tally;

          #include "hashtable.c"
          #include <stdio.h>

          struct Symbol *lookup(struct SymbolTable *t, char *key)
            unsigned int len= strlen(key);
            struct Symbol *found= SymbolTable_find(t, key, len);
            if (!found) found= SymbolTable_insert(t, key, len);
            return found;

          int main(int argc, char **argv)
            unsigned int i;
            struct SymbolTable *symbols= SymbolTable_new(argc * 2);
            while (--argc) {
              struct Symbol *symbol= lookup(symbols, *argv);
            for (i= 0;  i < symbols->hashtable_capacity;  ++i) {
              struct Symbol *s;
              if ((s= symbols->hashtable_entries[i]))
                printf("%7i %s\n", s->tally, s->hashtable_entry_key);
            return 0;

       The  following  preprocessor  symbols affect only the implementation in
       hashtable.c, unless otherwise noted.

              The type of a key.  The default type is 'char *'.   If  the  key
              type  is not 'pointer to integer' then appropriate copy, compare
              and hash functions should also be specified (see  below).   Note
              that this symbol affects both hashtable.c and hashtable.h.

              The  function  used  to  copy  a  key.   The default is value is
              'strdup'.  Note that the implemenation will reclaim the  storage
              for  copied  keys by calling free(), so the copy function should
              use malloc() (or one of its  cousins)  to  allocate  memory  for
              copied keys.

              The  function  used  to  compare two keys.  This function should
              return non-zero if the two keys are equal.  The default value is

              Controls  when  a  table grows to make room for new keys.  It is
              specified as a fraction of the  total  capacity  of  the  table.
              When this fractional capacity is exceeded, the table is grown by
              HASHTABLE_FACTOR (see below).  The default value is '1/2'.  Note
              that  the  fractional value must not be enclosed in parentheses,
              otherwise the compiler will round down to  zero  and  the  table
              will grow every time a key is inserted.

              The factor by which the capacity of the table is increased every
              time it is grown.  The default value is '3'.

              The name of the function that generates a  numeric  hash  for  a
              key.  The signature of this function must be

                 unsigned int
                                           unsigned int length )

              and  it  must always return the same value when given equivalent

       The symbols that affect hashtable.h are undefined automatically at  the
       end  of  that  file.  In the unlikely event they are useful beyond that
       file, defining HASHTABLE_KEEP_DEFINITIONS will preserve them.  All sym-
       bols  affecting  either  hashtable.h or hashtable.c are unconditionally
       undefined at the end of hashtable.c.  This permits the  C  file  to  be
       included  more than once in a parent source file, to create implementa-
       tions for multiple table types.

       The hashtable_new() function returns a pointer to  the  newly-allocated
       hash table, or null if memory could not be allocated.

       The  hashtable_initiliase(),  and  hashtable_release() functions return

       The hashtable_insert() function returns a pointer to the  newly-created
       table entry, or null if required memory cannot be allocated.

       The  hashtable_find()  function returns a pointer to the existing table
       entry corresponding to key, or null if the key does not  exist  in  the

       There  is  no  way  to  remove a key from a table.  You should not feel
       upset about this.

       The implementation trusts the client not to free any  of  the  pointers
       returned by hashable_insert() and hashable_find().

       The contents of the table may be rearranged during insertion.  Pointers
       returned  from  hashable_insert()  and  hashable_find()  are  therefore
       invalid after (and iteration is unstable over) insertions.


       [1] Donald Knuth, The Art of Computer Programming, Algorithm 6.4C.

       The latest version of this software and documentation:


       The software and this manual page were written by Ian Piumarta (first-
       name at last-name dot com).

       Please send bug reports and suggestions for improvements to the author
       at the above address.