dict.c

   #include <stdlib.h>
   #include <assert.h>
   #include <string.h>
   #include "dict.h"

    struct elt {
         struct elt *next;
         char *key;
         char *value;
   };

   struct dict {
       int size;           /* size of the pointer table */
       int n;              /* number of elements stored */
       struct elt **table;
   };

   #define INITIAL_SIZE (1024)
   #define GROWTH_FACTOR (2)
   #define MAX_LOAD_FACTOR (1)

   /* dictionary initialization code used in both DictCreate and grow */
   Dict
   internalDictCreate(int size)
   {
       Dict d;
       int i;

       d = malloc(sizeof(*d));

       assert(d != 0);

       d->size = size;
       d->n = 0;
       d->table = malloc(sizeof(struct elt *) * d->size);

       assert(d->table != 0);

       for(i = 0; i < d->size; i++) d->table[i] = 0;

       return d;
   }

   Dict
   DictCreate(void)
   {
       return internalDictCreate(INITIAL_SIZE);
   }

   void
   DictDestroy(Dict d)
   {
       int i;
       struct elt *e;
       struct elt *next;

       for(i = 0; i < d->size; i++) {
           for(e = d->table[i]; e != 0; e = next) {
               next = e->next;

               free(e->key);
               free(e->value);
               free(e);
           }
       }

       free(d->table);
       free(d);
   }

   #define MULTIPLIER (97)

   static unsigned long
   hash_function(const char *s)
   {
       unsigned const char *us;
       unsigned long h;

       h = 0;

       for(us = (unsigned const char *) s; *us; us++) {
           h = h * MULTIPLIER + *us;
       }

       return h;
   }

   static void
   grow(Dict d)
   {
       Dict d2;            /* new dictionary we'll create */
       struct dict swap;   /* temporary structure for brain transplant */
       int i;
       struct elt *e;

       d2 = internalDictCreate(d->size * GROWTH_FACTOR);

       for(i = 0; i < d->size; i++) {
          for(e = d->table[i]; e != 0; e = e->next) {
              /* note: this recopies everything */
              /* a more efficient implementation would
               * patch out the strdups inside DictInsert
               * to avoid this problem */
              DictInsert(d2, e->key, e->value);
          }
      }

      /* the hideous part */
      /* We'll swap the guts of d and d2 */
      /* then call DictDestroy on d2 */
      swap = *d;
      *d = *d2;
      *d2 = swap;

      DictDestroy(d2);
  }

  /* insert a new key-value pair into an existing dictionary */
  void
  DictInsert(Dict d, const char *key, const char *value)
  {
      struct elt *e;
      unsigned long h;

      assert(key);
      assert(value);

      e = malloc(sizeof(*e));

      assert(e);

      e->key = strdup(key);
      e->value = strdup(value);

      h = hash_function(key) % d->size;

      e->next = d->table[h];
      d->table[h] = e;

      d->n++;

      /* grow table if there is not enough room */
      if(d->n >= d->size * MAX_LOAD_FACTOR) {
          grow(d);
      }
  }

  /* return the most recently inserted value associated with a key */
  /* or 0 if no matching key is present */
  const char *
  DictSearch(Dict d, const char *key)
  {
      struct elt *e;

      for(e = d->table[hash_function(key) % d->size]; e != 0; e = e->next) {
          if(!strcmp(e->key, key)) {
              /* got it */
              return e->value;
          }
      }

      return 0;
  }

  /* delete the most recently inserted record with the given key */
  /* if there is no such record, has no effect */
  void
  DictDelete(Dict d, const char *key)
  {
      struct elt **prev;          /* what to change when elt is deleted */
      struct elt *e;              /* what to delete */

      for(prev = &(d->table[hash_function(key) % d->size]);
          *prev != 0;
          prev = &((*prev)->next)) {
          if(!strcmp((*prev)->key, key)) {
              /* got it */
              e = *prev;
              *prev = e->next;

              free(e->key);
              free(e->value);
              free(e);

              return;
          }
      }
  }