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