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