lib/hash.c

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