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
  14 extern char *malloc();
  15
  16 #define NULL 0
  17 #define hash_func(h, key) (key >= 0 ? (key % h->size) : (-key % h->size))
  18
  19 /* Create a hash table.  The size is just a hint, not a maximum. */
  20
  21 struct hash *create_hash(size)
  22 int size;
  23 {
  24     struct hash *h;
  25
  26     h = (struct hash *) malloc(sizeof(struct hash));
  27     if (h == (struct hash *) NULL)
  28       return((struct hash *) NULL);
  29     h->size = size;
  30     h->data = (struct bucket **) malloc(size * sizeof(char *));
  31     if (h->data == (struct bucket **) NULL) {
  32         free(h);
  33         return((struct hash *) NULL);
  34     }
  35     bzero(h->data, size * sizeof(char *));
  36     return(h);
  37 }
  38
  39 /* Lookup an object in the hash table.  Returns the value associated with
  40  * the key, or NULL (thus NULL is not a very good value to store...)
  41  */
  42
  43 char *hash_lookup(h, key)
  44 struct hash *h;
  45 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(h, key, value)
  64 struct hash *h;
  65 register int key;
  66 char *value;
  67 {
  68     register struct bucket *b;
  69
  70     b = h->data[hash_func(h, key)];
  71     while (b && b->key != key)
  72       b = b->next;
  73     if (b && b->key == key) {
  74         b->data = value;
  75         return(1);
  76     } else
  77       return(0);
  78 }
  79
  80
  81 /* Store an item in the hash table.  Returns 0 if the key was not previously
  82  * there, 1 if it was, or -1 if we ran out of memory.
  83  */
  84
  85 int hash_store(h, key, value)
  86 struct hash *h;
  87 register int key;
  88 char *value;
  89 {
  90     register struct bucket *b, **p;
  91
  92     p = &(h->data[hash_func(h, key)]);
  93     if (*p == NULL) {
  94         b = *p = (struct bucket *) malloc(sizeof(struct bucket));
  95         if (b == (struct bucket *) NULL)
  96           return(-1);
  97         b->next = NULL;
  98         b->key = key;
  99         b->data = value;
 100         return(0);
 101     }
 102
 103     for (b = *p; b && b->key != key; b = *p)
 104       p = (struct bucket **) *p;
 105     if (b && b->key == key) {
 106         b->data = value;
 107         return(1);
 108     }
 109     b = *p = (struct bucket *) malloc(sizeof(struct bucket));
 110     if (b == (struct bucket *) NULL)
 111       return(-1);
 112     b->next = NULL;
 113     b->key = key;
 114     b->data = value;
 115     return(0);
 116 }
 117
 118
 119 /* Search through the hash table for a given value.  For each piece of
 120  * data with that value, call the callback proc with the corresponding key.
 121  */
 122
 123 hash_search(h, value, callback)
 124 struct hash *h;
 125 register char *value;
 126 void (*callback)();
 127 {
 128     register struct bucket *b, **p;
 129
 130     for (p = &(h->data[h->size - 1]); p >= h->data; p--) {
 131         for (b = *p; b; b = b->next) {
 132             if (b->data == value)
 133               (*callback)(b->key);
 134         }
 135     }
 136 }
 137
 138
 139 /* Step through the hash table, calling the callback proc with each key.
 140  */
 141
 142 hash_step(h, callback, hint)
 143 struct hash *h;
 144 void (*callback)();
 145 char *hint;
 146 {
 147     register struct bucket *b, **p;
 148
 149     for (p = &(h->data[h->size - 1]); p >= h->data; p--) {
 150         for (b = *p; b; b = b->next) {
 151             (*callback)(b->key, b->data, hint);
 152         }
 153     }
 154 }
 155
 156
 157 /* Deallocate all of the memory associated with a table */
 158
 159 hash_destroy(h)
 160 struct hash *h;
 161 {
 162     register struct bucket *b, **p, *b1;
 163
 164     for (p = &(h->data[h->size - 1]); p >= h->data; p--) {
 165         for (b = *p; b; b = b1) {
 166             b1 = b->next;
 167             free(b);
 168         }
 169     }
 170 }