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