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