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