dbck/nhash.c

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