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