lib/hash.c

   1 /* $Header$
   2  *
   3  * Generic hash table routines.  Uses integer keys to store char * values.
   4  *
   5  *  (c) Copyright 1988 by the Massachusetts Institute of Technology.
   6  *  For copying and distribution information, please see the file
   7  *  <mit-copyright.h>.
   8  */
   9
  10 #include <mit-copyright.h>
  11 #include <ctype.h>
  12 #include <moira.h>
  13 #include <string.h>
  14 #include <stdlib.h>
  15
  16 #ifndef NULL
  17 #define NULL 0
  18 #endif
  19 #define hash_func(h, key) (key >= 0 ? (key % h->size) : (-key % h->size))
  20
  21 /* Create a hash table.  The size is just a hint, not a maximum. */
  22
  23 struct hash *create_hash(int size)
  24 {
  25   struct hash *h;
  26
  27   h = malloc(sizeof(struct hash));
  28   if (!h)
  29     return NULL;
  30   h->size = size;
  31   h->data = malloc(size * sizeof(char *));
  32   if (!h->data)
  33     {
  34       free(h);
  35       return NULL;
  36     }
  37   memset(h->data, 0, size * sizeof(char *));
  38   return h;
  39 }
  40
  41 /* Lookup an object in the hash table.  Returns the value associated with
  42  * the key, or NULL (thus NULL is not a very good value to store...)
  43  */
  44
  45 char *hash_lookup(struct hash *h, register int key)
  46 {
  47   register struct bucket *b;
  48
  49   b = h->data[hash_func(h, key)];
  50   while (b && b->key != key)
  51     b = b->next;
  52   if (b && b->key == key)
  53     return b->data;
  54   else
  55     return NULL;
  56 }
  57
  58
  59 /* Update an existing object in the hash table.  Returns 1 if the object
  60  * existed, or 0 if not.
  61  */
  62
  63 int hash_update(struct hash *h, register int key, char *value)
  64 {
  65   register struct bucket *b;
  66
  67   b = h->data[hash_func(h, key)];
  68   while (b && b->key != key)
  69     b = b->next;
  70   if (b && b->key == key)
  71     {
  72       b->data = value;
  73       return 1;
  74     }
  75   else
  76     return 0;
  77 }
  78
  79
  80 /* Store an item in the hash table.  Returns 0 if the key was not previously
  81  * there, 1 if it was, or -1 if we ran out of memory.
  82  */
  83
  84 int hash_store(struct hash *h, register int key, char *value)
  85 {
  86   register struct bucket *b, **p;
  87
  88   p = &(h->data[hash_func(h, key)]);
  89   if (!*p)
  90     {
  91       b = *p = malloc(sizeof(struct bucket));
  92       if (!b)
  93         return -1;
  94       b->next = NULL;
  95       b->key = key;
  96       b->data = value;
  97       return 0;
  98     }
  99
 100   for (b = *p; b && b->key != key; b = *p)
 101     p = (struct bucket **) *p;
 102   if (b && b->key == key)
 103     {
 104       b->data = value;
 105       return 1;
 106     }
 107   b = *p = malloc(sizeof(struct bucket));
 108   if (!b)
 109     return -1;
 110   b->next = NULL;
 111   b->key = key;
 112   b->data = value;
 113   return 0;
 114 }
 115
 116
 117 /* Search through the hash table for a given value.  For each piece of
 118  * data with that value, call the callback proc with the corresponding key.
 119  */
 120
 121 hash_search(struct hash *h, register char *value, void (*callback)())
 122 {
 123   register struct bucket *b, **p;
 124
 125   for (p = &(h->data[h->size - 1]); p >= h->data; p--)
 126     {
 127       for (b = *p; b; b = b->next)
 128         {
 129           if (b->data == value)
 130             (*callback)(b->key);
 131         }
 132     }
 133 }
 134
 135
 136 /* Step through the hash table, calling the callback proc with each key.
 137  */
 138
 139 hash_step(struct hash *h, void (*callback)(), char *hint)
 140 {
 141   register struct bucket *b, **p;
 142
 143   for (p = &(h->data[h->size - 1]); p >= h->data; p--)
 144     {
 145       for (b = *p; b; b = b->next)
 146         (*callback)(b->key, b->data, hint);
 147     }
 148 }
 149
 150
 151 /* Deallocate all of the memory associated with a table */
 152
 153 hash_destroy(struct hash *h)
 154 {
 155   register struct bucket *b, **p, *b1;
 156
 157   for (p = &(h->data[h->size - 1]); p >= h->data; p--)
 158     {
 159       for (b = *p; b; b = b1)
 160         {
 161           b1 = b->next;
 162           free(b);
 163         }
 164     }
 165 }