lib/hash.c

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