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