![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to hash.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / make|
Return to hash.c CVS log | Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / make |
1.1 root 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 are permitted
11: * provided that: (1) source distributions retain this entire copyright
12: * notice and comment, and (2) distributions including binaries display
13: * the following acknowledgement: ``This product includes software
14: * developed by the University of California, Berkeley and its contributors''
15: * in the documentation or other materials provided with the distribution
16: * and in all advertising materials mentioning features or use of this
17: * software. Neither the name of the University nor the names of its
18: * contributors may be used to endorse or promote products derived
19: * from this software without specific prior written permission.
20: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
21: * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
22: * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
23: */
24:
25: #ifndef lint
26: static char sccsid[] = "@(#)hash.c 5.4 (Berkeley) 6/1/90";
27: #endif /* not lint */
28:
29: /* hash.c --
30: *
31: * This module contains routines to manipulate a hash table.
32: * See hash.h for a definition of the structure of the hash
33: * table. Hash tables grow automatically as the amount of
34: * information increases.
35: */
36:
37: #include "sprite.h"
38: #include "hash.h"
39: #include "list.h"
40:
41: /*
42: * Forward references to local procedures that are used before they're
43: * defined:
44: */
45:
46: static Hash_Entry * ChainSearch();
47: static int Hash();
48: static void RebuildTable();
49:
50: /*
51: * The following defines the ratio of # entries to # buckets
52: * at which we rebuild the table to make it larger.
53: */
54:
55: static rebuildLimit = 3;
56:
57: /*
58: *---------------------------------------------------------
59: *
60: * Hash_InitTable --
61: *
62: * This routine just sets up the hash table.
63: *
64: * Results:
65: * None.
66: *
67: * Side Effects:
68: * Memory is allocated for the initial bucket area.
69: *
70: *---------------------------------------------------------
71: */
72:
73: void
74: Hash_InitTable(tablePtr, numBuckets, keyType)
75: register Hash_Table *tablePtr; /* Structure to use to hold table. */
76: int numBuckets; /* How many buckets to create for
77: * starters. This number is rounded
78: * up to a power of two. If <= 0,
79: * a reasonable default is chosen.
80: * The table will grow in size later
81: * as needed. */
82: int keyType; /* HASH_STRING_KEYS means that key
83: * values passed to HashFind will be
84: * strings, passed via a (char *)
85: * pointer. HASH_ONE_WORD_KEYS means
86: * that key values will be any
87: * one-word value passed as Address.
88: * > 1 means that key values will be
89: * multi-word values whose address is
90: * passed as Address. In this last
91: * case, keyType is the number of
92: * words in the key, not the number
93: * of bytes. */
94: {
95: register int i;
96: register List_Links *bucketPtr;
97:
98: /*
99: * Round up the size to a power of two.
100: */
101:
102: if (numBuckets <= 0) {
103: numBuckets = 16;
104: }
105: tablePtr->numEntries = 0;
106: tablePtr->keyType = keyType;
107: tablePtr->size = 2;
108: tablePtr->mask = 1;
109: tablePtr->downShift = 29;
110: while (tablePtr->size < numBuckets) {
111: tablePtr->size <<= 1;
112: tablePtr->mask = (tablePtr->mask << 1) + 1;
113: tablePtr->downShift--;
114: }
115:
116: tablePtr->bucketPtr = (List_Links *) emalloc(sizeof(List_Links)
117: * tablePtr->size);
118: for (i=0, bucketPtr = tablePtr->bucketPtr; i < tablePtr->size;
119: i++, bucketPtr++) {
120: List_Init(bucketPtr);
121: }
122: }
123:
124: /*
125: *---------------------------------------------------------
126: *
127: * Hash_DeleteTable --
128: *
129: * This routine removes everything from a hash table
130: * and frees up the memory space it occupied (except for
131: * the space in the Hash_Table structure).
132: *
133: * Results:
134: * None.
135: *
136: * Side Effects:
137: * Lots of memory is freed up.
138: *
139: *---------------------------------------------------------
140: */
141:
142: void
143: Hash_DeleteTable(tablePtr)
144: Hash_Table *tablePtr; /* Hash table whose entries are all to
145: * be freed. */
146: {
147: register List_Links *hashTableEnd;
148: register Hash_Entry *hashEntryPtr;
149: register List_Links *bucketPtr;
150:
151: bucketPtr = tablePtr->bucketPtr;
152: hashTableEnd = &(bucketPtr[tablePtr->size]);
153: for (; bucketPtr < hashTableEnd; bucketPtr++) {
154: while (!List_IsEmpty(bucketPtr)) {
155: hashEntryPtr = (Hash_Entry *) List_First(bucketPtr);
156: List_Remove((List_Links *) hashEntryPtr);
157: free((Address) hashEntryPtr);
158: }
159: }
160: free((Address) tablePtr->bucketPtr);
161:
162: /*
163: * Set up the hash table to cause memory faults on any future
164: * access attempts until re-initialization.
165: */
166:
167: tablePtr->bucketPtr = (List_Links *) NIL;
168: }
169:
170: /*
171: *---------------------------------------------------------
172: *
173: * Hash_FindEntry --
174: *
175: * Searches a hash table for an entry corresponding to key.
176: *
177: * Results:
178: * The return value is a pointer to the entry for key,
179: * if key was present in the table. If key was not
180: * present, NULL is returned.
181: *
182: * Side Effects:
183: * None.
184: *
185: *---------------------------------------------------------
186: */
187:
188: Hash_Entry *
189: Hash_FindEntry(tablePtr, key)
190: Hash_Table *tablePtr; /* Hash table to search. */
191: Address key; /* A hash key. */
192: {
193: return(ChainSearch(tablePtr, key,
194: &(tablePtr->bucketPtr[Hash(tablePtr, key)])));
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(tablePtr, key, newPtr)
218: register Hash_Table *tablePtr; /* Hash table to search. */
219: Address key; /* A hash key. */
220: Boolean *newPtr; /* Filled in with TRUE if new entry
221: * created, FALSE otherwise. */
222: {
223: register Hash_Entry *hashEntryPtr;
224: register int *hashKeyPtr;
225: register int *keyPtr;
226: List_Links *hashList;
227:
228: keyPtr = (int *) key;
229:
230: hashList = &(tablePtr->bucketPtr[Hash(tablePtr, (Address) keyPtr)]);
231: hashEntryPtr = ChainSearch(tablePtr, (Address) keyPtr, hashList);
232:
233: if (hashEntryPtr != (Hash_Entry *) NULL) {
234: if (newPtr != NULL) {
235: *newPtr = FALSE;
236: }
237: return hashEntryPtr;
238: }
239:
240: /*
241: * The desired entry isn't there. Before allocating a new entry,
242: * see if we're overloading the buckets. If so, then make a
243: * bigger table.
244: */
245:
246: if (tablePtr->numEntries >= rebuildLimit * tablePtr->size) {
247: RebuildTable(tablePtr);
248: hashList = &(tablePtr->bucketPtr[Hash(tablePtr, (Address) keyPtr)]);
249: }
250: tablePtr->numEntries += 1;
251:
252: /*
253: * Not there, we have to allocate. If the string is longer
254: * than 3 bytes, then we have to allocate extra space in the
255: * entry.
256: */
257:
258: switch (tablePtr->keyType) {
259: case HASH_STRING_KEYS:
260: hashEntryPtr = (Hash_Entry *) emalloc(sizeof(Hash_Entry) +
261: strlen((char *) keyPtr) - 3);
262: strcpy(hashEntryPtr->key.name, (char *) keyPtr);
263: break;
264: case HASH_ONE_WORD_KEYS:
265: hashEntryPtr = (Hash_Entry *) emalloc(sizeof(Hash_Entry));
266: hashEntryPtr->key.ptr = (Address) keyPtr;
267: break;
268: case 2:
269: hashEntryPtr =
270: (Hash_Entry *) emalloc(sizeof(Hash_Entry) + sizeof(int));
271: hashKeyPtr = hashEntryPtr->key.words;
272: *hashKeyPtr++ = *keyPtr++;
273: *hashKeyPtr = *keyPtr;
274: break;
275: default: {
276: register n;
277:
278: n = tablePtr->keyType;
279: hashEntryPtr = (Hash_Entry *)
280: emalloc(sizeof(Hash_Entry) + (n - 1) * sizeof(int));
281: hashKeyPtr = hashEntryPtr->key.words;
282: do {
283: *hashKeyPtr++ = *keyPtr++;
284: } while (--n);
285: break;
286: }
287: }
288:
289: hashEntryPtr->clientData = (ClientData) NULL;
290: List_Insert((List_Links *) hashEntryPtr, LIST_ATFRONT(hashList));
291:
292: if (newPtr != NULL) {
293: *newPtr = TRUE;
294: }
295: return hashEntryPtr;
296: }
297:
298: /*
299: *---------------------------------------------------------
300: *
301: * Hash_DeleteEntry --
302: *
303: * Delete the given hash table entry and free memory associated with
304: * it.
305: *
306: * Results:
307: * None.
308: *
309: * Side Effects:
310: * Hash chain that entry lives in is modified and memory is freed.
311: *
312: *---------------------------------------------------------
313: */
314:
315: void
316: Hash_DeleteEntry(tablePtr, hashEntryPtr)
317: Hash_Table *tablePtr;
318: register Hash_Entry *hashEntryPtr;
319: {
320: if (hashEntryPtr != (Hash_Entry *) NULL) {
321: List_Remove((List_Links *) hashEntryPtr);
322: free((Address) hashEntryPtr);
323: tablePtr->numEntries--;
324: }
325: }
326:
327: /*
328: *---------------------------------------------------------
329: *
330: * Hash_EnumFirst --
331: * This procedure sets things up for a complete search
332: * of all entries recorded in the hash table.
333: *
334: * Results:
335: * The return value is the address of the first entry in
336: * the hash table, or NULL if the table is empty.
337: *
338: * Side Effects:
339: * The information in hashSearchPtr is initialized so that successive
340: * calls to Hash_Next will return successive HashEntry's
341: * from the table.
342: *
343: *---------------------------------------------------------
344: */
345:
346: Hash_Entry *
347: Hash_EnumFirst(tablePtr, hashSearchPtr)
348: Hash_Table *tablePtr; /* Table to be searched. */
349: register Hash_Search *hashSearchPtr; /* Area in which to keep state
350: * about search.*/
351: {
352: hashSearchPtr->tablePtr = tablePtr;
353: hashSearchPtr->nextIndex = 0;
354: hashSearchPtr->hashEntryPtr = (Hash_Entry *) NULL;
355: return Hash_EnumNext(hashSearchPtr);
356: }
357:
358: /*
359: *---------------------------------------------------------
360: *
361: * Hash_EnumNext --
362: * This procedure returns successive entries in the hash table.
363: *
364: * Results:
365: * The return value is a pointer to the next HashEntry
366: * in the table, or NULL when the end of the table is
367: * reached.
368: *
369: * Side Effects:
370: * The information in hashSearchPtr is modified to advance to the
371: * next entry.
372: *
373: *---------------------------------------------------------
374: */
375:
376: Hash_Entry *
377: Hash_EnumNext(hashSearchPtr)
378: register Hash_Search *hashSearchPtr; /* Area used to keep state about
379: search. */
380: {
381: register List_Links *hashList;
382: register Hash_Entry *hashEntryPtr;
383:
384: hashEntryPtr = hashSearchPtr->hashEntryPtr;
385: while (hashEntryPtr == (Hash_Entry *) NULL ||
386: List_IsAtEnd(hashSearchPtr->hashList,
387: (List_Links *) hashEntryPtr)) {
388: if (hashSearchPtr->nextIndex >= hashSearchPtr->tablePtr->size) {
389: return((Hash_Entry *) NULL);
390: }
391: hashList = &(hashSearchPtr->tablePtr->bucketPtr[
392: hashSearchPtr->nextIndex]);
393: hashSearchPtr->nextIndex++;
394: if (!List_IsEmpty(hashList)) {
395: hashEntryPtr = (Hash_Entry *) List_First(hashList);
396: hashSearchPtr->hashList = hashList;
397: break;
398: }
399: }
400:
401: hashSearchPtr->hashEntryPtr =
402: (Hash_Entry *) List_Next((List_Links *) hashEntryPtr);
403:
404: return(hashEntryPtr);
405: }
406:
407: /*
408: *---------------------------------------------------------
409: *
410: * Hash_PrintStats --
411: *
412: * This routine calls a caller-supplied procedure to print
413: * statistics about the current bucket situation.
414: *
415: * Results:
416: * None.
417: *
418: * Side Effects:
419: * Proc gets called (potentially many times) to output information
420: * about the hash table. It must have the following calling sequence:
421: *
422: * void
423: * proc(clientData, string)
424: * ClientData clientData;
425: * char *string;
426: * {
427: * }
428: *
429: * In each call, clientData is the same as the clientData argument
430: * to this procedure, and string is a null-terminated string of
431: * characters to output.
432: *
433: *---------------------------------------------------------
434: */
435:
436: void
437: Hash_PrintStats(tablePtr, proc, clientData)
438: Hash_Table *tablePtr; /* Table for which to print info. */
439: void (*proc)(); /* Procedure to call to do actual
440: * I/O. */
441: {
442: int count[10], overflow, i, j;
443: char msg[100];
444: Hash_Entry *hashEntryPtr;
445: List_Links *hashList;
446:
447: for (i=0; i<10; i++) {
448: count[i] = 0;
449: }
450: overflow = 0;
451: for (i = 0; i < tablePtr->size; i++) {
452: j = 0;
453: hashList = &(tablePtr->bucketPtr[i]);
454: LIST_FORALL(hashList, (List_Links *) hashEntryPtr) {
455: j++;
456: }
457: if (j < 10) {
458: count[j]++;
459: } else {
460: overflow++;
461: }
462: }
463:
464: sprintf(msg, "Entries in table %d number of buckets %d\n",
465: tablePtr->numEntries, tablePtr->size);
466: (*proc)(clientData, msg);
467: for (i = 0; i < 10; i++) {
468: sprintf(msg, "Number of buckets with %d entries: %d.\n",
469: i, count[i]);
470: (*proc)(clientData, msg);
471: }
472: sprintf(msg, "Number of buckets with > 9 entries: %d.\n",
473: overflow);
474: (*proc)(clientData, msg);
475: }
476:
477: /*
478: *---------------------------------------------------------
479: *
480: * Hash --
481: * This is a local procedure to compute a hash table
482: * bucket address based on a string value.
483: *
484: * Results:
485: * The return value is an integer between 0 and size - 1.
486: *
487: * Side Effects:
488: * None.
489: *
490: * Design:
491: * It is expected that most keys are decimal numbers,
492: * so the algorithm behaves accordingly. The randomizing
493: * code is stolen straight from the rand library routine.
494: *
495: *---------------------------------------------------------
496: */
497:
498: static int
499: Hash(tablePtr, key)
500: register Hash_Table *tablePtr;
501: register char *key;
502: {
503: register int i = 0;
504: register int j;
505: register int *intPtr;
506:
507: switch (tablePtr->keyType) {
508: case HASH_STRING_KEYS:
509: while (*key != 0) {
510: i = (i * 10) + (*key++ - '0');
511: }
512: break;
513: case HASH_ONE_WORD_KEYS:
514: i = (int) key;
515: break;
516: case 2:
517: i = ((int *) key)[0] + ((int *) key)[1];
518: break;
519: default:
520: j = tablePtr->keyType;
521: intPtr = (int *) key;
522: do {
523: i += *intPtr++;
524: j--;
525: } while (j > 0);
526: break;
527: }
528:
529:
530: return(((i*1103515245 + 12345) >> tablePtr->downShift) & tablePtr->mask);
531: }
532:
533: /*
534: *---------------------------------------------------------
535: *
536: * ChainSearch --
537: *
538: * Search the hash table for the entry in the hash chain.
539: *
540: * Results:
541: * Pointer to entry in hash chain, NULL if none found.
542: *
543: * Side Effects:
544: * None.
545: *
546: *---------------------------------------------------------
547: */
548:
549: static Hash_Entry *
550: ChainSearch(tablePtr, key, hashList)
551: Hash_Table *tablePtr; /* Hash table to search. */
552: register Address key; /* A hash key. */
553: register List_Links *hashList;
554: {
555: register Hash_Entry *hashEntryPtr;
556: register int *hashKeyPtr;
557: int *keyPtr;
558: register int numKeys;
559:
560: numKeys = tablePtr->keyType;
561: LIST_FORALL(hashList, (List_Links *) hashEntryPtr) {
562: switch (numKeys) {
563: case 0:
564: if (strcmp(hashEntryPtr->key.name, key) == 0) {
565: return(hashEntryPtr);
566: }
567: break;
568: case 1:
569: if (hashEntryPtr->key.ptr == key) {
570: return(hashEntryPtr);
571: }
572: break;
573: case 2:
574: hashKeyPtr = hashEntryPtr->key.words;
575: keyPtr = (int *) key;
576: if (*hashKeyPtr++ == *keyPtr++ && *hashKeyPtr == *keyPtr) {
577: return(hashEntryPtr);
578: }
579: break;
580: default:
581: if (bcmp((Address) hashEntryPtr->key.words,
582: (Address) key, numKeys * sizeof(int))) {
583: return(hashEntryPtr);
584: }
585: break;
586: }
587: }
588:
589: /*
590: * The desired entry isn't there
591: */
592:
593: return ((Hash_Entry *) NULL);
594: }
595:
596: /*
597: *---------------------------------------------------------
598: *
599: * RebuildTable --
600: * This local routine makes a new hash table that
601: * is larger than the old one.
602: *
603: * Results:
604: * None.
605: *
606: * Side Effects:
607: * The entire hash table is moved, so any bucket numbers
608: * from the old table are invalid.
609: *
610: *---------------------------------------------------------
611: */
612:
613: static void
614: RebuildTable(tablePtr)
615: Hash_Table *tablePtr; /* Table to be enlarged. */
616: {
617: int oldSize;
618: int bucket;
619: List_Links *oldBucketPtr;
620: register Hash_Entry *hashEntryPtr;
621: register List_Links *oldHashList;
622:
623: oldBucketPtr = tablePtr->bucketPtr;
624: oldSize = tablePtr->size;
625:
626: /*
627: * Build a new table 4 times as large as the old one.
628: */
629:
630: Hash_InitTable(tablePtr, tablePtr->size * 4, tablePtr->keyType);
631:
632: for (oldHashList = oldBucketPtr; oldSize > 0; oldSize--, oldHashList++) {
633: while (!List_IsEmpty(oldHashList)) {
634: hashEntryPtr = (Hash_Entry *) List_First(oldHashList);
635: List_Remove((List_Links *) hashEntryPtr);
636: switch (tablePtr->keyType) {
637: case HASH_STRING_KEYS:
638: bucket = Hash(tablePtr, (Address) hashEntryPtr->key.name);
639: break;
640: case HASH_ONE_WORD_KEYS:
641: bucket = Hash(tablePtr, (Address) hashEntryPtr->key.ptr);
642: break;
643: default:
644: bucket = Hash(tablePtr, (Address) hashEntryPtr->key.words);
645: break;
646: }
647: List_Insert((List_Links *) hashEntryPtr,
648: LIST_ATFRONT(&(tablePtr->bucketPtr[bucket])));
649: tablePtr->numEntries++;
650: }
651: }
652:
653: free((Address) oldBucketPtr);
654: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.