lib/hash.c

   1 /* $Header$
   2  *
   3  * Generic hash table routines.  Uses integer keys to store char * values.
   4  */
   5
   6 #include <ctype.h>
   7 #include "sms_app.h"
   8 #define NULL 0
   9
  10
  11 /* Create a hash table.  The size is just a hint, not a maximum. */
  12
  13 struct hash *create_hash(size)
  14 int size;
  15 {
  16     struct hash *h;
  17
  18     h = (struct hash *) malloc(sizeof(struct hash));
  19     h->size = size;
  20     h->data = (struct bucket **) malloc(size * sizeof(char *));
  21     bzero(h->data, size * sizeof(char *));
  22     return(h);
  23 }
  24
  25 /* Lookup an object in the hash table.  Returns the value associated with
  26  * the key, or NULL (thus NULL is not a very good value to store...)
  27  */
  28
  29 char *hash_lookup(h, key)
  30 struct hash *h;
  31 register int key;
  32 {
  33     register struct bucket *b;
  34
  35     b = h->data[key % h->size];
  36     while (b && b->key != key)
  37       b = b->next;
  38     if (b && b->key == key)
  39       return(b->data);
  40     else
  41       return(NULL);
  42 }
  43
  44
  45 /* Update an existing object in the hash table.  Returns 1 if the object
  46  * existed, or 0 if not.
  47  */
  48
  49 int hash_update(h, key, value)
  50 struct hash *h;
  51 register int key;
  52 char *value;
  53 {
  54     register struct bucket *b;
  55
  56     b = h->data[key % h->size];
  57     while (b && b->key != key)
  58       b = b->next;
  59     if (b && b->key == key) {
  60         b->data = value;
  61         return(1);
  62     } else
  63       return(0);
  64 }
  65
  66
  67 /* Store an item in the hash table.  Returns 0 if the key was not previously
  68  * there, or 1 if it was.
  69  */
  70
  71 int hash_store(h, key, value)
  72 struct hash *h;
  73 register int key;
  74 char *value;
  75 {
  76     register struct bucket *b, **p;
  77
  78     p = &(h->data[key % h->size]);
  79     if (*p == NULL) {
  80         b = *p = (struct bucket *) malloc(sizeof(struct bucket));
  81         b->next = NULL;
  82         b->key = key;
  83         b->data = value;
  84         return(0);
  85     }
  86
  87     for (b = *p; b && b->key != key; b = *p)
  88       p = (struct bucket **) *p;
  89     if (b && b->key == key) {
  90         b->data = value;
  91         return(1);
  92     }
  93     b = *p = (struct bucket *) malloc(sizeof(struct bucket));
  94     b->next = NULL;
  95     b->key = key;
  96     b->data = value;
  97     return(0);
  98 }
  99
 100
 101 /* Search through the hash table for a given value.  For each piece of
 102  * data with that value, call the callback proc with the corresponding key.
 103  */
 104
 105 hash_search(h, value, callback)
 106 struct hash *h;
 107 register char *value;
 108 void (*callback)();
 109 {
 110     register struct bucket *b, **p;
 111
 112     for (p = &(h->data[h->size - 1]); p >= h->data; p--) {
 113         for (b = *p; b; b = b->next) {
 114             if (b->data == value)
 115               (*callback)(b->key);
 116         }
 117     }
 118 }
 119
 120
 121 /* Deallocate all of the memory associated with a table */
 122
 123 hash_destroy(h)
 124 struct hash *h;
 125 {
 126     register struct bucket *b, **p, *b1;
 127
 128     for (p = &(h->data[h->size - 1]); p >= h->data; p--) {
 129         for (b = *p; b; b = b1) {
 130             b1 = b->next;
 131             free(b);
 132         }
 133     }
 134 }