4 /* Modified and bugfixed for nitfol by Evin Robertson Sept 10, 1999 */
8 ** public domain code by Jerry Coffin, with improvements by HenkJan Wolthuis.
10 ** Tested with Visual C 1.0 and Borland C 3.1.
11 ** Compiles without warnings, and seems like it should be pretty
18 ** A hash table consists of an array of these buckets. Each bucket
19 ** holds a copy of the key, a pointer to the data associated with the
20 ** key, and a pointer to the next bucket that collided with this one,
24 typedef struct bucket {
31 ** This is what you actually declare an instance of to create a table.
32 ** You then call 'construct_table' with the address of this structure,
33 ** and a guess at the size of the table. Note that more nodes than this
34 ** can be inserted in the table, but performance degrades as this
35 ** happens. Performance should still be quite adequate until 2 or 3
36 ** times as many nodes have been inserted as the table was created with.
39 typedef struct hash_table {
47 ** These are used in freeing a table. Perhaps I should code up
48 ** something a little less grungy, but it works, so what the heck.
50 typedef void (*my_function)(void *);
51 static my_function function = NULL;
52 static hash_table *the_table = NULL;
54 /* Initialize the hash_table to the size asked for. Allocates space
55 ** for the correct number of pointers and sets them to NULL. If it
56 ** can't allocate sufficient memory, signals error by setting the size
60 hash_table *n_hash_construct_table(hash_table *table, size_t size)
66 table -> table = (bucket * *)n_malloc(sizeof(bucket *) * size);
67 temp = table -> table;
82 ** Hashes a string to produce an unsigned short, which should be
83 ** sufficient for most purposes.
86 static unsigned hash(const char *string)
93 /* Modified by ecr to fix bug and improve method slightly */
95 i = string[0] + (string[1] << 8);
103 ** Insert 'key' into hash table.
104 ** Returns pointer to old data associated with the key, if any, or
105 ** NULL if the key wasn't in the table previously.
108 void *n_hash_insert(const char *key, void *data, hash_table *table)
110 unsigned val = hash(key) % table->size;
114 ** NULL means this bucket hasn't been used yet. We'll simply
115 ** allocate space for our new bucket and put our data there, with
116 ** the table pointing at it.
119 if (NULL == (table->table)[val])
121 (table->table)[val] = (bucket *)n_malloc(sizeof(bucket));
122 if (NULL==(table->table)[val])
125 (table->table)[val] -> key = n_strdup(key);
126 (table->table)[val] -> next = NULL;
127 (table->table)[val] -> data = data;
128 return (table->table)[val] -> data;
132 ** This spot in the table is already in use. See if the current string
133 ** has already been inserted, and if so, increment its count.
136 for (ptr = (table->table)[val];NULL != ptr; ptr = ptr -> next)
137 if (0 == n_strcmp(key, ptr->key))
141 old_data = ptr->data;
147 ** This key must not be in the table yet. We'll add it to the head of
148 ** the list at this spot in the hash table. Speed would be
149 ** slightly improved if the list was kept sorted instead. In this case,
150 ** this code would be moved into the loop above, and the insertion would
151 ** take place as soon as it was determined that the present key in the
152 ** list was larger than this one.
155 ptr = (bucket *)n_malloc(sizeof(bucket));
158 ptr -> key = n_strdup(key);
160 ptr -> next = (table->table)[val];
161 (table->table)[val] = ptr;
167 ** Look up a key and return the associated data. Returns NULL if
168 ** the key is not in the table.
171 void *n_hash_lookup(const char *key, hash_table *table)
173 unsigned val = hash(key) % table->size;
176 if (NULL == (table->table)[val])
179 for ( ptr = (table->table)[val];NULL != ptr; ptr = ptr->next )
181 if (0 == n_strcmp(key, ptr -> key ) )
188 ** Delete a key from the hash table and return associated
189 ** data, or NULL if not present.
192 void *n_hash_del(const char *key, hash_table *table)
194 unsigned val = hash(key) % table->size;
196 bucket *ptr, *last = NULL;
198 if (NULL == (table->table)[val])
202 ** Traverse the list, keeping track of the previous node in the list.
203 ** When we find the node to delete, we set the previous node's next
204 ** pointer to point to the node after ourself instead. We then delete
205 ** the key from the present node, and return a pointer to the data it
209 for (last = NULL, ptr = (table->table)[val];
211 last = ptr, ptr = ptr->next)
213 if (0 == n_strcmp(key, ptr -> key))
218 last -> next = ptr -> next;
225 ** If 'last' still equals NULL, it means that we need to
226 ** delete the first node in the list. This simply consists
227 ** of putting our own 'next' pointer in the array holding
228 ** the head of the list. We then dispose of the current
235 (table->table)[val] = ptr->next;
244 ** If we get here, it means we didn't find the item in the table.
245 ** Signal this by returning NULL.
252 ** free_table iterates the table, calling this repeatedly to free
253 ** each individual node. This, in turn, calls one or two other
254 ** functions - one to free the storage used for the key, the other
255 ** passes a pointer to the data back to a function defined by the user,
256 ** process the data as needed.
259 static void free_node(const char *key, void *data)
264 function(n_hash_del(key,the_table));
265 else n_hash_del(key,the_table);
269 ** Frees a complete table by iterating over it and freeing each node.
270 ** the second parameter is the address of a function it will call with a
271 ** pointer to the data associated with each node. This function is
272 ** responsible for freeing the data, or doing whatever is needed with
276 void n_hash_free_table(hash_table *table, void (*func)(void *))
281 n_hash_enumerate( table, free_node);
282 n_free(table->table);
287 function = (void (*)(void *))NULL;
291 ** Simply invokes the function given as the second parameter for each
292 ** node in the table, passing it the key and the associated data.
295 void n_hash_enumerate( hash_table *table, void (*func)(const char *, void *))
300 for (i=0; i < table->size; i++)
302 for (temp = (table->table)[i]; temp; temp=next)
304 next = temp->next; /* ecr - temp may be deleted by func */
305 func(temp->key, temp->data);