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