1 /*-
2 * Copyright (c) 1988, 1989, 1990, 1993
3 * The Regents of the University of California. All rights reserved.
4 * Copyright (c) 1988, 1989 by Adam de Boor
5 * Copyright (c) 1989 by Berkeley Softworks
6 * All rights reserved.
7 *
8 * This code is derived from software contributed to Berkeley by
9 * Adam de Boor.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 * notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 * 3. All advertising materials mentioning features or use of this software
20 * must display the following acknowledgement:
21 * This product includes software developed by the University of
22 * California, Berkeley and its contributors.
23 * 4. Neither the name of the University nor the names of its contributors
24 * may be used to endorse or promote products derived from this software
25 * without specific prior written permission.
26 *
27 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
28 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
29 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
30 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
31 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
32 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
33 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
34 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
35 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
36 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
37 * SUCH DAMAGE.
38 *
39 * @(#)hash.c 8.1 (Berkeley) 6/6/93
40 */
41
42 #include <sys/cdefs.h>
43 __FBSDID("$FreeBSD$");
44
45 /* hash.c --
46 *
47 * This module contains routines to manipulate a hash table.
48 * See hash.h for a definition of the structure of the hash
49 * table. Hash tables grow automatically as the amount of
50 * information increases.
51 */
52
53 #include <stdlib.h>
54 #include <string.h>
55 #include <unistd.h>
56
57 #include "hash.h"
58 #include "util.h"
59
60 /*
61 * Forward references to local procedures that are used before they're
62 * defined:
63 */
64 static void RebuildTable(Hash_Table *);
65
66 /*
67 * The following defines the ratio of # entries to # buckets
68 * at which we rebuild the table to make it larger.
69 */
70
71 #define rebuildLimit 8
72
73 /*
74 *---------------------------------------------------------
75 *
76 * Hash_InitTable --
77 *
78 * Set up the hash table t with a given number of buckets, or a
79 * reasonable default if the number requested is less than or
80 * equal to zero. Hash tables will grow in size as needed.
81 *
82 *
83 * Results:
84 * None.
85 *
86 * Side Effects:
87 * Memory is allocated for the initial bucket area.
88 *
89 *---------------------------------------------------------
90 */
91 void
Hash_InitTable(Hash_Table * t,int numBuckets)92 Hash_InitTable(Hash_Table *t, int numBuckets)
93 {
94 int i;
95 struct Hash_Entry **hp;
96
97 /*
98 * Round up the size to a power of two.
99 */
100 if (numBuckets <= 0)
101 i = 16;
102 else {
103 for (i = 2; i < numBuckets; i <<= 1)
104 continue;
105 }
106 t->numEntries = 0;
107 t->size = i;
108 t->mask = i - 1;
109 t->bucketPtr = hp = emalloc(sizeof(*hp) * i);
110 while (--i >= 0)
111 *hp++ = NULL;
112 }
113
114 /*
115 *---------------------------------------------------------
116 *
117 * Hash_DeleteTable --
118 *
119 * This routine removes everything from a hash table
120 * and frees up the memory space it occupied (except for
121 * the space in the Hash_Table structure).
122 *
123 * Results:
124 * None.
125 *
126 * Side Effects:
127 * Lots of memory is freed up.
128 *
129 *---------------------------------------------------------
130 */
131 void
Hash_DeleteTable(Hash_Table * t)132 Hash_DeleteTable(Hash_Table *t)
133 {
134 struct Hash_Entry **hp, *h, *nexth = NULL;
135 int i;
136
137 for (hp = t->bucketPtr, i = t->size; --i >= 0;) {
138 for (h = *hp++; h != NULL; h = nexth) {
139 nexth = h->next;
140 free(h);
141 }
142 }
143 free(t->bucketPtr);
144
145 /*
146 * Set up the hash table to cause memory faults on any future access
147 * attempts until re-initialization.
148 */
149 t->bucketPtr = NULL;
150 }
151
152 /*
153 *---------------------------------------------------------
154 *
155 * Hash_FindEntry --
156 *
157 * Searches a hash table for an entry corresponding to key.
158 *
159 * Results:
160 * The return value is a pointer to the entry for key,
161 * if key was present in the table. If key was not
162 * present, NULL is returned.
163 *
164 * Side Effects:
165 * None.
166 *
167 *---------------------------------------------------------
168 */
169 Hash_Entry *
Hash_FindEntry(const Hash_Table * t,const char * key)170 Hash_FindEntry(const Hash_Table *t, const char *key)
171 {
172 Hash_Entry *e;
173 unsigned h;
174 const char *p;
175
176 for (h = 0, p = key; *p;)
177 h = (h << 5) - h + *p++;
178 p = key;
179 for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)
180 if (e->namehash == h && strcmp(e->name, p) == 0)
181 return (e);
182 return (NULL);
183 }
184
185 /*
186 *---------------------------------------------------------
187 *
188 * Hash_CreateEntry --
189 *
190 * Searches a hash table for an entry corresponding to
191 * key. If no entry is found, then one is created.
192 *
193 * Results:
194 * The return value is a pointer to the entry. If *newPtr
195 * isn't NULL, then *newPtr is filled in with TRUE if a
196 * new entry was created, and FALSE if an entry already existed
197 * with the given key.
198 *
199 * Side Effects:
200 * Memory may be allocated, and the hash buckets may be modified.
201 *---------------------------------------------------------
202 */
203 Hash_Entry *
Hash_CreateEntry(Hash_Table * t,const char * key,Boolean * newPtr)204 Hash_CreateEntry(Hash_Table *t, const char *key, Boolean *newPtr)
205 {
206 Hash_Entry *e;
207 unsigned int h;
208 const char *p;
209 int keylen;
210 struct Hash_Entry **hp;
211
212 /*
213 * Hash the key. As a side effect, save the length (strlen) of the
214 * key in case we need to create the entry.
215 */
216 for (h = 0, p = key; *p;)
217 h = (h << 5) - h + *p++;
218 keylen = p - key;
219 p = key;
220 for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
221 if (e->namehash == h && strcmp(e->name, p) == 0) {
222 if (newPtr != NULL)
223 *newPtr = FALSE;
224 return (e);
225 }
226 }
227
228 /*
229 * The desired entry isn't there. Before allocating a new entry,
230 * expand the table if necessary (and this changes the resulting
231 * bucket chain).
232 */
233 if (t->numEntries >= rebuildLimit * t->size)
234 RebuildTable(t);
235 e = emalloc(sizeof(*e) + keylen);
236 hp = &t->bucketPtr[h & t->mask];
237 e->next = *hp;
238 *hp = e;
239 e->clientData = NULL;
240 e->namehash = h;
241 strcpy(e->name, p);
242 t->numEntries++;
243
244 if (newPtr != NULL)
245 *newPtr = TRUE;
246 return (e);
247 }
248
249 /*
250 *---------------------------------------------------------
251 *
252 * Hash_DeleteEntry --
253 *
254 * Delete the given hash table entry and free memory associated with
255 * it.
256 *
257 * Results:
258 * None.
259 *
260 * Side Effects:
261 * Hash chain that entry lives in is modified and memory is freed.
262 *
263 *---------------------------------------------------------
264 */
265 void
Hash_DeleteEntry(Hash_Table * t,Hash_Entry * e)266 Hash_DeleteEntry(Hash_Table *t, Hash_Entry *e)
267 {
268 Hash_Entry **hp, *p;
269
270 if (e == NULL)
271 return;
272 for (hp = &t->bucketPtr[e->namehash & t->mask];
273 (p = *hp) != NULL; hp = &p->next) {
274 if (p == e) {
275 *hp = p->next;
276 free(p);
277 t->numEntries--;
278 return;
279 }
280 }
281 write(STDERR_FILENO, "bad call to Hash_DeleteEntry\n", 29);
282 abort();
283 }
284
285 /*
286 *---------------------------------------------------------
287 *
288 * Hash_EnumFirst --
289 * This procedure sets things up for a complete search
290 * of all entries recorded in the hash table.
291 *
292 * Results:
293 * The return value is the address of the first entry in
294 * the hash table, or NULL if the table is empty.
295 *
296 * Side Effects:
297 * The information in searchPtr is initialized so that successive
298 * calls to Hash_Next will return successive HashEntry's
299 * from the table.
300 *
301 *---------------------------------------------------------
302 */
303 Hash_Entry *
Hash_EnumFirst(const Hash_Table * t,Hash_Search * searchPtr)304 Hash_EnumFirst(const Hash_Table *t, Hash_Search *searchPtr)
305 {
306
307 searchPtr->tablePtr = t;
308 searchPtr->nextIndex = 0;
309 searchPtr->hashEntryPtr = NULL;
310 return (Hash_EnumNext(searchPtr));
311 }
312
313 /*
314 *---------------------------------------------------------
315 *
316 * Hash_EnumNext --
317 * This procedure returns successive entries in the hash table.
318 *
319 * Results:
320 * The return value is a pointer to the next HashEntry
321 * in the table, or NULL when the end of the table is
322 * reached.
323 *
324 * Side Effects:
325 * The information in searchPtr is modified to advance to the
326 * next entry.
327 *
328 *---------------------------------------------------------
329 */
330 Hash_Entry *
Hash_EnumNext(Hash_Search * searchPtr)331 Hash_EnumNext(Hash_Search *searchPtr)
332 {
333 Hash_Entry *e;
334 const Hash_Table *t = searchPtr->tablePtr;
335
336 /*
337 * The hashEntryPtr field points to the most recently returned
338 * entry, or is NULL if we are starting up. If not NULL, we have
339 * to start at the next one in the chain.
340 */
341 e = searchPtr->hashEntryPtr;
342 if (e != NULL)
343 e = e->next;
344 /*
345 * If the chain ran out, or if we are starting up, we need to
346 * find the next nonempty chain.
347 */
348 while (e == NULL) {
349 if (searchPtr->nextIndex >= t->size)
350 return (NULL);
351 e = t->bucketPtr[searchPtr->nextIndex++];
352 }
353 searchPtr->hashEntryPtr = e;
354 return (e);
355 }
356
357 /*
358 *---------------------------------------------------------
359 *
360 * RebuildTable --
361 * This local routine makes a new hash table that
362 * is larger than the old one.
363 *
364 * Results:
365 * None.
366 *
367 * Side Effects:
368 * The entire hash table is moved, so any bucket numbers
369 * from the old table are invalid.
370 *
371 *---------------------------------------------------------
372 */
373 static void
RebuildTable(Hash_Table * t)374 RebuildTable(Hash_Table *t)
375 {
376 Hash_Entry *e, *next = NULL, **hp, **xp;
377 int i, mask;
378 Hash_Entry **oldhp;
379 int oldsize;
380
381 oldhp = t->bucketPtr;
382 oldsize = i = t->size;
383 i <<= 1;
384 t->size = i;
385 t->mask = mask = i - 1;
386 t->bucketPtr = hp = emalloc(sizeof(*hp) * i);
387 while (--i >= 0)
388 *hp++ = NULL;
389 for (hp = oldhp, i = oldsize; --i >= 0;) {
390 for (e = *hp++; e != NULL; e = next) {
391 next = e->next;
392 xp = &t->bucketPtr[e->namehash & mask];
393 e->next = *xp;
394 *xp = e;
395 }
396 }
397 free(oldhp);
398 }
399