NAME

SYNOPSIS

#include "htable.h"

HTABLE_HEAD(NAME, SIZE, TYPE);

HTABLE_ENTRY(TYPE);

size_t


HTABLE_SIZE(HTABLE_HEAD *head);

uint32_t


HTABLE_COUNT(HTABLE_HEAD *head);

int


HTABLE_EMPTY(HTABLE_HEAD *head);

float


HTABLE_COLLS(HTABLE_HEAD *head);

float


HTABLE_LOAD(HTABLE_HEAD *head);

HTABLE_INITIALIZER(HTABLE_HEAD *head);

HTABLE_INIT(HTABLE_HEAD *head);

HTABLE_PROTOTYPE(NAME, TYPE);

HTABLE_GENERATE(NAME, TYPE, KEY, CMP);

HTABLE_ENTRY *


HTABLE_INSERT(NAME, HTABLE_HEAD *head, HTABLE_ENTRY *elm);

HTABLE_ENTRY *


HTABLE_REMOVE(NAME, HTABLE_HEAD *head, HTABLE_ENTRY *elm); 

HTABLE_ENTRY *


HTABLE_LOOKUP(NAME, HTABLE_HEAD *head, HTABLE_ENTRY *elm);

HTABLE_ENTRY *


HTABLE_FIRST(NAME, HTABLE_HEAD *head);

HTABLE_ENTRY *


HTABLE_NEXT(NAME, HTABLE_HEAD *head, HTABLE_ENTRY *elm);

HTABLE_FOREACH(HTABLE_ENTRY *elm, NAME, HTABLE_HEAD *head);

DESCRIPTION

Hash tables are ideal for applications with datasets needing a lot of adding, searching or removal, as those are normally constant-time operations. The primary operation it supports efficiently is a lookup: given a key (e.g. a person's name), find the corresponding value (e.g. that person's telephone number). It works by transforming the key using a hash function into a hash, a number that is used as an index in an array to locate the desired location ("bucket") where the values should be.

Hash tables support the efficient insertion of new entries, in expected O(1) time. The time spent in searching depends on the hash function and the load of the hash table; both insertion and search approach O(1) time with well chosen values and hashes.

HASH TABLES

      struct phonebook_s {
        char *name, *phone;
        HTABLE_ENTRY (phonebook_s);
      };

The argument NAME in the macro definitions is the name tag of a user defined structure that must be declared using the macro HTABLE_HEAD() as follows:

HTABLE_HEAD (NAME, SIZE, TYPE) hash_table;

The argument NAME has to be a unique name prefix for every hash table that is defined. SIZE is the number of buckets the hash table will hold. A pointer to such a hash table structure could then later be defined as:

struct NAME *tableptr;

Once a hash table was defined, it must be initialized using the HTABLE_INIT() macro, head being a reference to this hash table. It is also possible to initialize it statically by using the HTABLE_INITIALIZER() macro like this:

      HTABLE_HEAD (NAME, SIZE, TYPE) htable = 
        HTABLE_INITIALIZER (&htable);

In order to use the functions that manipulate the hash table structure, their prototypes need to be declared with the HTABLE_PROTOTYPE() macro, where NAME is a unique identifier for this particular hash_table. The TYPE argument is the type of the structure that is being managed by the hash table.

The function bodies are generated with the HTABLE_GENERATE() macro, which must be used only once. It takes the same two first arguments as the HTABLE_PROTOTYPE() macro, and the two last arguments are the names of user-defined functions used to extract key information from a hash table entry and to compare two entries.

The function used to retrieve information related to the key given a hash table entry must have the following prototype:

 void (*key) (HTABLE_ENTRY *elm, char **key, int *len);

where elm is the given pointer to the hash table entry, key and len must be filled in with respectively the pointer to the corresponding key and with this key's length.

The function used to compare two hash tables entries must follow this prototype:

 int (*cmp) (HTABLE_ENTRY *elm1, HTABLE_ENTRY *elm2);

where elm1 and elm2 are the entries to compare. This function must return an integer value, being 0 in case the keys are equal, and a value different from 0 otherwise.

See section EXAMPLE for possible implementations of such functions.

The HTABLE_INSERT() macro inserts the element elm in the hash table pointed at by head. A pointer to the element is returned in case it was successfully inserted. Otherwise, NULL is returned, meaning the insertion did not occur (e.g. the element was already stored in the hash table).

The HTABLE_REMOVE() macro removes the element elm from the hash table pointed at by head. The removed element is returned to the user so it can be freed if necessary. If the element was not found, NULL is returned.

The HTABLE_LOOKUP() macro finds the element elm in the hash table pointed at by head. The data corresponding to the removed element is returned to the user (NULL is returned in case the element was not found).

The HTABLE_FIRST() and HTABLE_NEXT() macros can be used to traverse the hash table:

      for (elm = HTABLE_FIRST (NAME, &head); 
           elm != NULL; 
           elm = HTABLE_NEXT (NAME, &head, elm))

Or, for simplicity, one can use the HTABLE_FOREACH() macro:

HTABLE_FOREACH (elm, NAME, &head)

There are also some macros useful to get information about a given hash table:

The HTABLE_SIZE() macro returns the total number of buckets contained in the hash table pointed at by head.

The HTABLE_COUNT() returns the number of items contained in the hash table pointed at by head.

The HTABLE_COLLS() returns a percentage indicating the collisions (e.g. when two keys hash to the same bucket) there are in the hash table pointed at by head.

The HTABLE_LOAD() macro returns a percentage indicating the load factor (e.g. the number of filled buckets over the total number of buckets) of the hash table pointed at by head.

The HTABLE_EMPTY() macro should be used to check wether a hash table is empty.

EXAMPLES

   #include <stdlib.h>
   #include <stdio.h>
   #include <string.h>
   #include "htable.h"
   #define HSIZE  100
   struct book_s {
     char *name, *phone;
     HTABLE_ENTRY (book_s);
   };
   void
   extract_key (struct book_s *data, char **key, int *len)
   {
     *key = data->name;
     *len = strlen (data->name);
   }
   int
   compare (struct book_s *data1, struct book_s *data2)
   {
     const int KEYLEN = strlen (data1->name);
     if (strlen (data2->name) == KEYLEN
         && !memcmp (data1->name, data2->name, KEYLEN))
       return 0;
     else
       return 1;
   }
   int
   main ()
   {
     int i;
     struct book_s *elm;
     struct book_s entries[] = {
       {"friend1", "555-1111"},
       {"friend2", "555-2222"},
       {"person3", "555-3333"},
       {"person4", "555-4444"}
     };
     const int NOENTRIES = sizeof (entries) / sizeof (struct book_s);
     HTABLE_HEAD (pbook, HSIZE, book_s) htable = 
       HTABLE_INITIALIZER (&htable);
     HTABLE_GENERATE (pbook, book_s, extract_key, compare);  
     for (i = 0; i < NOENTRIES; i++)
       HTABLE_INSERT (pbook, &htable, &entries[i]);
     elm = HTABLE_LOOKUP (pbook, &htable, &entries[1]);
     printf ("friend2's Phone number is: %s\n", elm->phone);
     HTABLE_FOREACH (elm, pbook, &htable)
       {
         printf ("Entry:\n");
         printf (" name: %s\n", elm->name);
         printf ("phone: %s\n", elm->phone);
       }
     elm = HTABLE_REMOVE (pbook, &htable, &entries[2]);
     printf ("Number of items in hash table: %u\n",
             HTABLE_COUNT (&htable));
     return EXIT_SUCCESS;
   }

NOTES

   /*
    * Wrapper around the HTABLE_REMOVE macro.
    *
    * A hash table was previously defined using:
    *    HTABLE_HEAD (my_hash, HSIZE, my_entry) htable =
    *      HTABLE_INITIALIZER (&htable);
    */
   void
   htable_free (struct my_hash *ht, struct my_entry *elm)
   {
     struct my_entry *removed;
     removed = HTABLE_REMOVE (my_hash, ht, elm);
     if (removed != NULL)
       free (removed);
   }

HASH FUNCTIONS

The following functions are available:

HASH_JEN

The default hash function, Jenkins' Lookup hash.

HASH_OAT

Jenkins' "One at a time" hash function.

For example, to specify that Jenkins' "One at a time" hash function must be used for the "test" program, one must compile it using a command such as:

cc -I/path/to/htable.h -DHASH_FUNCTION=HASH_OAT -o test test.c

To determine the best hash function for your key domain, you can use the HTABLE_COLLS and HTABLE_LOAD macros to compare the collisions and load factors obtained with the different hash functions.

SEE ALSO

Those macros were greatly inspired by the implementations of spray and red-black trees found in the *BSD kernels (see file /usr/src/sys/sys/tree.h).

AUTHORS