Annotation of src/usr.bin/make/hash.c, Revision 1.2
1.2 ! deraadt 1: /* $OpenBSD: hash.c,v 1.5 1995/06/14 15:19:15 christos Exp $ */
1.1 deraadt 2: /* $NetBSD: hash.c,v 1.5 1995/06/14 15:19:15 christos Exp $ */
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: #ifndef lint
43: #if 0
44: static char sccsid[] = "@(#)hash.c 5.5 (Berkeley) 12/28/90";
45: #else
1.2 ! deraadt 46: static char rcsid[] = "$OpenBSD: hash.c,v 1.5 1995/06/14 15:19:15 christos Exp $";
1.1 deraadt 47: #endif
48: #endif /* not lint */
49:
50: /* hash.c --
51: *
52: * This module contains routines to manipulate a hash table.
53: * See hash.h for a definition of the structure of the hash
54: * table. Hash tables grow automatically as the amount of
55: * information increases.
56: */
57: #include "sprite.h"
58: #include "make.h"
59: #include "hash.h"
60:
61: /*
62: * Forward references to local procedures that are used before they're
63: * defined:
64: */
65:
66: static void RebuildTable __P((Hash_Table *));
67:
68: /*
69: * The following defines the ratio of # entries to # buckets
70: * at which we rebuild the table to make it larger.
71: */
72:
73: #define rebuildLimit 8
74:
75: /*
76: *---------------------------------------------------------
77: *
78: * Hash_InitTable --
79: *
80: * This routine just sets up the hash table.
81: *
82: * Results:
83: * None.
84: *
85: * Side Effects:
86: * Memory is allocated for the initial bucket area.
87: *
88: *---------------------------------------------------------
89: */
90:
91: void
92: Hash_InitTable(t, numBuckets)
93: register Hash_Table *t; /* Structure to use to hold table. */
94: int numBuckets; /* How many buckets to create for starters.
95: * This number is rounded up to a power of
96: * two. If <= 0, a reasonable default is
97: * chosen. The table will grow in size later
98: * as needed. */
99: {
100: register int i;
101: register struct Hash_Entry **hp;
102:
103: /*
104: * Round up the size to a power of two.
105: */
106: if (numBuckets <= 0)
107: i = 16;
108: else {
109: for (i = 2; i < numBuckets; i <<= 1)
110: continue;
111: }
112: t->numEntries = 0;
113: t->size = i;
114: t->mask = i - 1;
115: t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i);
116: while (--i >= 0)
117: *hp++ = NULL;
118: }
119:
120: /*
121: *---------------------------------------------------------
122: *
123: * Hash_DeleteTable --
124: *
125: * This routine removes everything from a hash table
126: * and frees up the memory space it occupied (except for
127: * the space in the Hash_Table structure).
128: *
129: * Results:
130: * None.
131: *
132: * Side Effects:
133: * Lots of memory is freed up.
134: *
135: *---------------------------------------------------------
136: */
137:
138: void
139: Hash_DeleteTable(t)
140: Hash_Table *t;
141: {
142: register struct Hash_Entry **hp, *h, *nexth = NULL;
143: register int i;
144:
145: for (hp = t->bucketPtr, i = t->size; --i >= 0;) {
146: for (h = *hp++; h != NULL; h = nexth) {
147: nexth = h->next;
148: free((char *)h);
149: }
150: }
151: free((char *)t->bucketPtr);
152:
153: /*
154: * Set up the hash table to cause memory faults on any future access
155: * attempts until re-initialization.
156: */
157: t->bucketPtr = NULL;
158: }
159:
160: /*
161: *---------------------------------------------------------
162: *
163: * Hash_FindEntry --
164: *
165: * Searches a hash table for an entry corresponding to key.
166: *
167: * Results:
168: * The return value is a pointer to the entry for key,
169: * if key was present in the table. If key was not
170: * present, NULL is returned.
171: *
172: * Side Effects:
173: * None.
174: *
175: *---------------------------------------------------------
176: */
177:
178: Hash_Entry *
179: Hash_FindEntry(t, key)
180: Hash_Table *t; /* Hash table to search. */
181: char *key; /* A hash key. */
182: {
183: register Hash_Entry *e;
184: register unsigned h;
185: register char *p;
186:
187: for (h = 0, p = key; *p;)
188: h = (h << 5) - h + *p++;
189: p = key;
190: for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)
191: if (e->namehash == h && strcmp(e->name, p) == 0)
192: return (e);
193: return (NULL);
194: }
195:
196: /*
197: *---------------------------------------------------------
198: *
199: * Hash_CreateEntry --
200: *
201: * Searches a hash table for an entry corresponding to
202: * key. If no entry is found, then one is created.
203: *
204: * Results:
205: * The return value is a pointer to the entry. If *newPtr
206: * isn't NULL, then *newPtr is filled in with TRUE if a
207: * new entry was created, and FALSE if an entry already existed
208: * with the given key.
209: *
210: * Side Effects:
211: * Memory may be allocated, and the hash buckets may be modified.
212: *---------------------------------------------------------
213: */
214:
215: Hash_Entry *
216: Hash_CreateEntry(t, key, newPtr)
217: register Hash_Table *t; /* Hash table to search. */
218: char *key; /* A hash key. */
219: Boolean *newPtr; /* Filled in with TRUE if new entry created,
220: * FALSE otherwise. */
221: {
222: register Hash_Entry *e;
223: register unsigned h;
224: register char *p;
225: int keylen;
226: struct Hash_Entry **hp;
227:
228: /*
229: * Hash the key. As a side effect, save the length (strlen) of the
230: * key in case we need to create the entry.
231: */
232: for (h = 0, p = key; *p;)
233: h = (h << 5) - h + *p++;
234: keylen = p - key;
235: p = key;
236: for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
237: if (e->namehash == h && strcmp(e->name, p) == 0) {
238: if (newPtr != NULL)
239: *newPtr = FALSE;
240: return (e);
241: }
242: }
243:
244: /*
245: * The desired entry isn't there. Before allocating a new entry,
246: * expand the table if necessary (and this changes the resulting
247: * bucket chain).
248: */
249: if (t->numEntries >= rebuildLimit * t->size)
250: RebuildTable(t);
251: e = (Hash_Entry *) emalloc(sizeof(*e) + keylen);
252: hp = &t->bucketPtr[h & t->mask];
253: e->next = *hp;
254: *hp = e;
255: e->clientData = NULL;
256: e->namehash = h;
257: (void) strcpy(e->name, p);
258: t->numEntries++;
259:
260: if (newPtr != NULL)
261: *newPtr = TRUE;
262: return (e);
263: }
264:
265: /*
266: *---------------------------------------------------------
267: *
268: * Hash_DeleteEntry --
269: *
270: * Delete the given hash table entry and free memory associated with
271: * it.
272: *
273: * Results:
274: * None.
275: *
276: * Side Effects:
277: * Hash chain that entry lives in is modified and memory is freed.
278: *
279: *---------------------------------------------------------
280: */
281:
282: void
283: Hash_DeleteEntry(t, e)
284: Hash_Table *t;
285: Hash_Entry *e;
286: {
287: register Hash_Entry **hp, *p;
288:
289: if (e == NULL)
290: return;
291: for (hp = &t->bucketPtr[e->namehash & t->mask];
292: (p = *hp) != NULL; hp = &p->next) {
293: if (p == e) {
294: *hp = p->next;
295: free((char *)p);
296: t->numEntries--;
297: return;
298: }
299: }
300: (void) write(2, "bad call to Hash_DeleteEntry\n", 29);
301: abort();
302: }
303:
304: /*
305: *---------------------------------------------------------
306: *
307: * Hash_EnumFirst --
308: * This procedure sets things up for a complete search
309: * of all entries recorded in the hash table.
310: *
311: * Results:
312: * The return value is the address of the first entry in
313: * the hash table, or NULL if the table is empty.
314: *
315: * Side Effects:
316: * The information in searchPtr is initialized so that successive
317: * calls to Hash_Next will return successive HashEntry's
318: * from the table.
319: *
320: *---------------------------------------------------------
321: */
322:
323: Hash_Entry *
324: Hash_EnumFirst(t, searchPtr)
325: Hash_Table *t; /* Table to be searched. */
326: register Hash_Search *searchPtr;/* Area in which to keep state
327: * about search.*/
328: {
329: searchPtr->tablePtr = t;
330: searchPtr->nextIndex = 0;
331: searchPtr->hashEntryPtr = NULL;
332: return Hash_EnumNext(searchPtr);
333: }
334:
335: /*
336: *---------------------------------------------------------
337: *
338: * Hash_EnumNext --
339: * This procedure returns successive entries in the hash table.
340: *
341: * Results:
342: * The return value is a pointer to the next HashEntry
343: * in the table, or NULL when the end of the table is
344: * reached.
345: *
346: * Side Effects:
347: * The information in searchPtr is modified to advance to the
348: * next entry.
349: *
350: *---------------------------------------------------------
351: */
352:
353: Hash_Entry *
354: Hash_EnumNext(searchPtr)
355: register Hash_Search *searchPtr; /* Area used to keep state about
356: search. */
357: {
358: register Hash_Entry *e;
359: Hash_Table *t = searchPtr->tablePtr;
360:
361: /*
362: * The hashEntryPtr field points to the most recently returned
363: * entry, or is nil if we are starting up. If not nil, we have
364: * to start at the next one in the chain.
365: */
366: e = searchPtr->hashEntryPtr;
367: if (e != NULL)
368: e = e->next;
369: /*
370: * If the chain ran out, or if we are starting up, we need to
371: * find the next nonempty chain.
372: */
373: while (e == NULL) {
374: if (searchPtr->nextIndex >= t->size)
375: return (NULL);
376: e = t->bucketPtr[searchPtr->nextIndex++];
377: }
378: searchPtr->hashEntryPtr = e;
379: return (e);
380: }
381:
382: /*
383: *---------------------------------------------------------
384: *
385: * RebuildTable --
386: * This local routine makes a new hash table that
387: * is larger than the old one.
388: *
389: * Results:
390: * None.
391: *
392: * Side Effects:
393: * The entire hash table is moved, so any bucket numbers
394: * from the old table are invalid.
395: *
396: *---------------------------------------------------------
397: */
398:
399: static void
400: RebuildTable(t)
401: register Hash_Table *t;
402: {
403: register Hash_Entry *e, *next = NULL, **hp, **xp;
404: register int i, mask;
405: register Hash_Entry **oldhp;
406: int oldsize;
407:
408: oldhp = t->bucketPtr;
409: oldsize = i = t->size;
410: i <<= 1;
411: t->size = i;
412: t->mask = mask = i - 1;
413: t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i);
414: while (--i >= 0)
415: *hp++ = NULL;
416: for (hp = oldhp, i = oldsize; --i >= 0;) {
417: for (e = *hp++; e != NULL; e = next) {
418: next = e->next;
419: xp = &t->bucketPtr[e->namehash & mask];
420: e->next = *xp;
421: *xp = e;
422: }
423: }
424: free((char *)oldhp);
425: }
![[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