3 * Generic hash table routines. Uses integer keys to store char * values.
5 * Copyright (C) 1988-1998 by the Massachusetts Institute of Technology.
6 * For copying and distribution information, please see the file
10 #include <mit-copyright.h>
18 #define hash_func(h, key) (key >= 0 ? (key % h->size) : (-key % h->size))
20 /* Create a hash table. The size is just a hint, not a maximum. */
22 struct hash *create_hash(int size)
26 h = malloc(sizeof(struct hash));
30 h->data = malloc(size * sizeof(void *));
36 memset(h->data, 0, size * sizeof(void *));
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...)
44 void *hash_lookup(struct hash *h, int key)
48 b = h->data[hash_func(h, key)];
49 while (b && b->key != key)
51 if (b && b->key == key)
58 /* Update an existing object in the hash table. Returns 1 if the object
59 * existed, or 0 if not.
62 int hash_update(struct hash *h, int key, void *value)
66 b = h->data[hash_func(h, key)];
67 while (b && b->key != key)
69 if (b && b->key == key)
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.
83 int hash_store(struct hash *h, int key, void *value)
85 struct bucket *b, **p;
87 p = &(h->data[hash_func(h, key)]);
90 b = *p = malloc(sizeof(struct bucket));
99 for (b = *p; b && b->key != key; b = *p)
100 p = (struct bucket **) *p;
101 if (b && b->key == key)
106 b = *p = malloc(sizeof(struct bucket));
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.
120 void hash_search(struct hash *h, void *value, void (*callback)(int))
122 struct bucket *b, **p;
124 for (p = &(h->data[h->size - 1]); p >= h->data; p--)
126 for (b = *p; b; b = b->next)
128 if (b->data == value)
135 /* Step through the hash table, calling the callback proc with each key.
138 void hash_step(struct hash *h, void (*callback)(int, void *, void *),
141 struct bucket *b, **p;
143 for (p = &(h->data[h->size - 1]); p >= h->data; p--)
145 for (b = *p; b; b = b->next)
146 (*callback)(b->key, b->data, hint);
151 /* Deallocate all of the memory associated with a table */
153 void hash_destroy(struct hash *h)
155 struct bucket *b, **p, *b1;
157 for (p = &(h->data[h->size - 1]); p >= h->data; p--)
159 for (b = *p; b; b = b1)