X-Git-Url: https://git.subgeniuskitty.com/unix-history/.git/blobdiff_plain/1c15e88899094343f75aeba04122cd96a96b428e..refs/tags/BSD-4_3_Net_2:/usr/src/usr.bin/make/hash.c diff --git a/usr/src/usr.bin/make/hash.c b/usr/src/usr.bin/make/hash.c index 7c24f7e86a..dd7a987431 100644 --- a/usr/src/usr.bin/make/hash.c +++ b/usr/src/usr.bin/make/hash.c @@ -7,23 +7,37 @@ * This code is derived from software contributed to Berkeley by * Adam de Boor. * - * Redistribution and use in source and binary forms are permitted - * provided that: (1) source distributions retain this entire copyright - * notice and comment, and (2) distributions including binaries display - * the following acknowledgement: ``This product includes software - * developed by the University of California, Berkeley and its contributors'' - * in the documentation or other materials provided with the distribution - * and in all advertising materials mentioning features or use of this - * software. Neither the name of the University nor the names of its - * contributors may be used to endorse or promote products derived - * from this software without specific prior written permission. - * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR - * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED - * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. */ #ifndef lint -static char sccsid[] = "@(#)hash.c 5.4 (Berkeley) 6/1/90"; +static char sccsid[] = "@(#)hash.c 5.5 (Berkeley) 12/28/90"; #endif /* not lint */ /* hash.c -- @@ -36,15 +50,12 @@ static char sccsid[] = "@(#)hash.c 5.4 (Berkeley) 6/1/90"; #include "sprite.h" #include "hash.h" -#include "list.h" /* * Forward references to local procedures that are used before they're * defined: */ -static Hash_Entry * ChainSearch(); -static int Hash(); static void RebuildTable(); /* @@ -52,8 +63,8 @@ static void RebuildTable(); * at which we rebuild the table to make it larger. */ -static rebuildLimit = 3; - +#define rebuildLimit 8 + /* *--------------------------------------------------------- * @@ -71,56 +82,34 @@ static rebuildLimit = 3; */ void -Hash_InitTable(tablePtr, numBuckets, keyType) - register Hash_Table *tablePtr; /* Structure to use to hold table. */ - int numBuckets; /* How many buckets to create for - * starters. This number is rounded - * up to a power of two. If <= 0, - * a reasonable default is chosen. - * The table will grow in size later - * as needed. */ - int keyType; /* HASH_STRING_KEYS means that key - * values passed to HashFind will be - * strings, passed via a (char *) - * pointer. HASH_ONE_WORD_KEYS means - * that key values will be any - * one-word value passed as Address. - * > 1 means that key values will be - * multi-word values whose address is - * passed as Address. In this last - * case, keyType is the number of - * words in the key, not the number - * of bytes. */ +Hash_InitTable(t, numBuckets) + register Hash_Table *t; /* Structure to use to hold table. */ + int numBuckets; /* How many buckets to create for starters. + * This number is rounded up to a power of + * two. If <= 0, a reasonable default is + * chosen. The table will grow in size later + * as needed. */ { - register int i; - register List_Links *bucketPtr; - - /* - * Round up the size to a power of two. - */ - - if (numBuckets <= 0) { - numBuckets = 16; - } - tablePtr->numEntries = 0; - tablePtr->keyType = keyType; - tablePtr->size = 2; - tablePtr->mask = 1; - tablePtr->downShift = 29; - while (tablePtr->size < numBuckets) { - tablePtr->size <<= 1; - tablePtr->mask = (tablePtr->mask << 1) + 1; - tablePtr->downShift--; - } - - tablePtr->bucketPtr = (List_Links *) emalloc(sizeof(List_Links) - * tablePtr->size); - for (i=0, bucketPtr = tablePtr->bucketPtr; i < tablePtr->size; - i++, bucketPtr++) { - List_Init(bucketPtr); - } + register int i; + register struct Hash_Entry **hp; + + /* + * Round up the size to a power of two. + */ + if (numBuckets <= 0) + i = 16; + else { + for (i = 2; i < numBuckets; i <<= 1) + /* void */ ; + } + t->numEntries = 0; + t->size = i; + t->mask = i - 1; + t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i); + while (--i >= 0) + *hp++ = NULL; } - + /* *--------------------------------------------------------- * @@ -140,33 +129,27 @@ Hash_InitTable(tablePtr, numBuckets, keyType) */ void -Hash_DeleteTable(tablePtr) - Hash_Table *tablePtr; /* Hash table whose entries are all to - * be freed. */ +Hash_DeleteTable(t) + Hash_Table *t; { - register List_Links *hashTableEnd; - register Hash_Entry *hashEntryPtr; - register List_Links *bucketPtr; - - bucketPtr = tablePtr->bucketPtr; - hashTableEnd = &(bucketPtr[tablePtr->size]); - for (; bucketPtr < hashTableEnd; bucketPtr++) { - while (!List_IsEmpty(bucketPtr)) { - hashEntryPtr = (Hash_Entry *) List_First(bucketPtr); - List_Remove((List_Links *) hashEntryPtr); - free((Address) hashEntryPtr); - } - } - free((Address) tablePtr->bucketPtr); + register struct Hash_Entry **hp, *h, *nexth; + register int i; - /* - * Set up the hash table to cause memory faults on any future - * access attempts until re-initialization. - */ + for (hp = t->bucketPtr, i = t->size; --i >= 0;) { + for (h = *hp++; h != NULL; h = nexth) { + nexth = h->next; + free((char *)h); + } + } + free((char *)t->bucketPtr); - tablePtr->bucketPtr = (List_Links *) NIL; + /* + * Set up the hash table to cause memory faults on any future access + * attempts until re-initialization. + */ + t->bucketPtr = NULL; } - + /* *--------------------------------------------------------- * @@ -186,14 +169,23 @@ Hash_DeleteTable(tablePtr) */ Hash_Entry * -Hash_FindEntry(tablePtr, key) - Hash_Table *tablePtr; /* Hash table to search. */ - Address key; /* A hash key. */ +Hash_FindEntry(t, key) + Hash_Table *t; /* Hash table to search. */ + char *key; /* A hash key. */ { - return(ChainSearch(tablePtr, key, - &(tablePtr->bucketPtr[Hash(tablePtr, key)]))); + register Hash_Entry *e; + register unsigned h; + register char *p; + + for (h = 0, p = key; *p;) + h = (h << 5) - h + *p++; + p = key; + for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) + if (e->namehash == h && strcmp(e->name, p) == 0) + return (e); + return (NULL); } - + /* *--------------------------------------------------------- * @@ -214,87 +206,55 @@ Hash_FindEntry(tablePtr, key) */ Hash_Entry * -Hash_CreateEntry(tablePtr, key, newPtr) - register Hash_Table *tablePtr; /* Hash table to search. */ - Address key; /* A hash key. */ - Boolean *newPtr; /* Filled in with TRUE if new entry - * created, FALSE otherwise. */ +Hash_CreateEntry(t, key, newPtr) + register Hash_Table *t; /* Hash table to search. */ + char *key; /* A hash key. */ + Boolean *newPtr; /* Filled in with TRUE if new entry created, + * FALSE otherwise. */ { - register Hash_Entry *hashEntryPtr; - register int *hashKeyPtr; - register int *keyPtr; - List_Links *hashList; - - keyPtr = (int *) key; - - hashList = &(tablePtr->bucketPtr[Hash(tablePtr, (Address) keyPtr)]); - hashEntryPtr = ChainSearch(tablePtr, (Address) keyPtr, hashList); - - if (hashEntryPtr != (Hash_Entry *) NULL) { - if (newPtr != NULL) { - *newPtr = FALSE; - } - return hashEntryPtr; - } - - /* - * The desired entry isn't there. Before allocating a new entry, - * see if we're overloading the buckets. If so, then make a - * bigger table. - */ - - if (tablePtr->numEntries >= rebuildLimit * tablePtr->size) { - RebuildTable(tablePtr); - hashList = &(tablePtr->bucketPtr[Hash(tablePtr, (Address) keyPtr)]); - } - tablePtr->numEntries += 1; - - /* - * Not there, we have to allocate. If the string is longer - * than 3 bytes, then we have to allocate extra space in the - * entry. - */ - - switch (tablePtr->keyType) { - case HASH_STRING_KEYS: - hashEntryPtr = (Hash_Entry *) emalloc(sizeof(Hash_Entry) + - strlen((char *) keyPtr) - 3); - strcpy(hashEntryPtr->key.name, (char *) keyPtr); - break; - case HASH_ONE_WORD_KEYS: - hashEntryPtr = (Hash_Entry *) emalloc(sizeof(Hash_Entry)); - hashEntryPtr->key.ptr = (Address) keyPtr; - break; - case 2: - hashEntryPtr = - (Hash_Entry *) emalloc(sizeof(Hash_Entry) + sizeof(int)); - hashKeyPtr = hashEntryPtr->key.words; - *hashKeyPtr++ = *keyPtr++; - *hashKeyPtr = *keyPtr; - break; - default: { - register n; - - n = tablePtr->keyType; - hashEntryPtr = (Hash_Entry *) - emalloc(sizeof(Hash_Entry) + (n - 1) * sizeof(int)); - hashKeyPtr = hashEntryPtr->key.words; - do { - *hashKeyPtr++ = *keyPtr++; - } while (--n); - break; + register Hash_Entry *e; + register unsigned h; + register char *p; + int keylen; + struct Hash_Entry **hp; + + /* + * Hash the key. As a side effect, save the length (strlen) of the + * key in case we need to create the entry. + */ + for (h = 0, p = key; *p;) + h = (h << 5) - h + *p++; + keylen = p - key; + p = key; + for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) { + if (e->namehash == h && strcmp(e->name, p) == 0) { + if (newPtr != NULL) + *newPtr = FALSE; + return (e); + } } - } - hashEntryPtr->clientData = (ClientData) NULL; - List_Insert((List_Links *) hashEntryPtr, LIST_ATFRONT(hashList)); - - if (newPtr != NULL) { - *newPtr = TRUE; - } - return hashEntryPtr; + /* + * The desired entry isn't there. Before allocating a new entry, + * expand the table if necessary (and this changes the resulting + * bucket chain). + */ + if (t->numEntries >= rebuildLimit * t->size) + RebuildTable(t); + e = (Hash_Entry *) emalloc(sizeof(*e) + keylen); + hp = &t->bucketPtr[h & t->mask]; + e->next = *hp; + *hp = e; + e->clientData = NULL; + e->namehash = h; + (void) strcpy(e->name, p); + t->numEntries++; + + if (newPtr != NULL) + *newPtr = TRUE; + return (e); } - + /* *--------------------------------------------------------- * @@ -313,17 +273,27 @@ Hash_CreateEntry(tablePtr, key, newPtr) */ void -Hash_DeleteEntry(tablePtr, hashEntryPtr) - Hash_Table *tablePtr; - register Hash_Entry *hashEntryPtr; +Hash_DeleteEntry(t, e) + Hash_Table *t; + Hash_Entry *e; { - if (hashEntryPtr != (Hash_Entry *) NULL) { - List_Remove((List_Links *) hashEntryPtr); - free((Address) hashEntryPtr); - tablePtr->numEntries--; - } + register Hash_Entry **hp, *p; + + if (e == NULL) + return; + for (hp = &t->bucketPtr[e->namehash & t->mask]; + (p = *hp) != NULL; hp = &p->next) { + if (p == e) { + *hp = p->next; + free((char *)p); + t->numEntries--; + return; + } + } + (void) write(2, "bad call to Hash_DeleteEntry\n", 29); + abort(); } - + /* *--------------------------------------------------------- * @@ -336,7 +306,7 @@ Hash_DeleteEntry(tablePtr, hashEntryPtr) * the hash table, or NULL if the table is empty. * * Side Effects: - * The information in hashSearchPtr is initialized so that successive + * The information in searchPtr is initialized so that successive * calls to Hash_Next will return successive HashEntry's * from the table. * @@ -344,15 +314,15 @@ Hash_DeleteEntry(tablePtr, hashEntryPtr) */ Hash_Entry * -Hash_EnumFirst(tablePtr, hashSearchPtr) - Hash_Table *tablePtr; /* Table to be searched. */ - register Hash_Search *hashSearchPtr; /* Area in which to keep state - * about search.*/ +Hash_EnumFirst(t, searchPtr) + Hash_Table *t; /* Table to be searched. */ + register Hash_Search *searchPtr;/* Area in which to keep state + * about search.*/ { - hashSearchPtr->tablePtr = tablePtr; - hashSearchPtr->nextIndex = 0; - hashSearchPtr->hashEntryPtr = (Hash_Entry *) NULL; - return Hash_EnumNext(hashSearchPtr); + searchPtr->tablePtr = t; + searchPtr->nextIndex = 0; + searchPtr->hashEntryPtr = NULL; + return Hash_EnumNext(searchPtr); } /* @@ -367,232 +337,41 @@ Hash_EnumFirst(tablePtr, hashSearchPtr) * reached. * * Side Effects: - * The information in hashSearchPtr is modified to advance to the + * The information in searchPtr is modified to advance to the * next entry. * *--------------------------------------------------------- */ Hash_Entry * -Hash_EnumNext(hashSearchPtr) - register Hash_Search *hashSearchPtr; /* Area used to keep state about +Hash_EnumNext(searchPtr) + register Hash_Search *searchPtr; /* Area used to keep state about search. */ { - register List_Links *hashList; - register Hash_Entry *hashEntryPtr; - - hashEntryPtr = hashSearchPtr->hashEntryPtr; - while (hashEntryPtr == (Hash_Entry *) NULL || - List_IsAtEnd(hashSearchPtr->hashList, - (List_Links *) hashEntryPtr)) { - if (hashSearchPtr->nextIndex >= hashSearchPtr->tablePtr->size) { - return((Hash_Entry *) NULL); + register Hash_Entry *e; + Hash_Table *t = searchPtr->tablePtr; + + /* + * The hashEntryPtr field points to the most recently returned + * entry, or is nil if we are starting up. If not nil, we have + * to start at the next one in the chain. + */ + e = searchPtr->hashEntryPtr; + if (e != NULL) + e = e->next; + /* + * If the chain ran out, or if we are starting up, we need to + * find the next nonempty chain. + */ + while (e == NULL) { + if (searchPtr->nextIndex >= t->size) + return (NULL); + e = t->bucketPtr[searchPtr->nextIndex++]; } - hashList = &(hashSearchPtr->tablePtr->bucketPtr[ - hashSearchPtr->nextIndex]); - hashSearchPtr->nextIndex++; - if (!List_IsEmpty(hashList)) { - hashEntryPtr = (Hash_Entry *) List_First(hashList); - hashSearchPtr->hashList = hashList; - break; - } - } - - hashSearchPtr->hashEntryPtr = - (Hash_Entry *) List_Next((List_Links *) hashEntryPtr); - - return(hashEntryPtr); + searchPtr->hashEntryPtr = e; + return (e); } - -/* - *--------------------------------------------------------- - * - * Hash_PrintStats -- - * - * This routine calls a caller-supplied procedure to print - * statistics about the current bucket situation. - * - * Results: - * None. - * - * Side Effects: - * Proc gets called (potentially many times) to output information - * about the hash table. It must have the following calling sequence: - * - * void - * proc(clientData, string) - * ClientData clientData; - * char *string; - * { - * } - * - * In each call, clientData is the same as the clientData argument - * to this procedure, and string is a null-terminated string of - * characters to output. - * - *--------------------------------------------------------- - */ -void -Hash_PrintStats(tablePtr, proc, clientData) - Hash_Table *tablePtr; /* Table for which to print info. */ - void (*proc)(); /* Procedure to call to do actual - * I/O. */ -{ - int count[10], overflow, i, j; - char msg[100]; - Hash_Entry *hashEntryPtr; - List_Links *hashList; - - for (i=0; i<10; i++) { - count[i] = 0; - } - overflow = 0; - for (i = 0; i < tablePtr->size; i++) { - j = 0; - hashList = &(tablePtr->bucketPtr[i]); - LIST_FORALL(hashList, (List_Links *) hashEntryPtr) { - j++; - } - if (j < 10) { - count[j]++; - } else { - overflow++; - } - } - - sprintf(msg, "Entries in table %d number of buckets %d\n", - tablePtr->numEntries, tablePtr->size); - (*proc)(clientData, msg); - for (i = 0; i < 10; i++) { - sprintf(msg, "Number of buckets with %d entries: %d.\n", - i, count[i]); - (*proc)(clientData, msg); - } - sprintf(msg, "Number of buckets with > 9 entries: %d.\n", - overflow); - (*proc)(clientData, msg); -} - -/* - *--------------------------------------------------------- - * - * Hash -- - * This is a local procedure to compute a hash table - * bucket address based on a string value. - * - * Results: - * The return value is an integer between 0 and size - 1. - * - * Side Effects: - * None. - * - * Design: - * It is expected that most keys are decimal numbers, - * so the algorithm behaves accordingly. The randomizing - * code is stolen straight from the rand library routine. - * - *--------------------------------------------------------- - */ - -static int -Hash(tablePtr, key) - register Hash_Table *tablePtr; - register char *key; -{ - register int i = 0; - register int j; - register int *intPtr; - - switch (tablePtr->keyType) { - case HASH_STRING_KEYS: - while (*key != 0) { - i = (i * 10) + (*key++ - '0'); - } - break; - case HASH_ONE_WORD_KEYS: - i = (int) key; - break; - case 2: - i = ((int *) key)[0] + ((int *) key)[1]; - break; - default: - j = tablePtr->keyType; - intPtr = (int *) key; - do { - i += *intPtr++; - j--; - } while (j > 0); - break; - } - - - return(((i*1103515245 + 12345) >> tablePtr->downShift) & tablePtr->mask); -} - -/* - *--------------------------------------------------------- - * - * ChainSearch -- - * - * Search the hash table for the entry in the hash chain. - * - * Results: - * Pointer to entry in hash chain, NULL if none found. - * - * Side Effects: - * None. - * - *--------------------------------------------------------- - */ - -static Hash_Entry * -ChainSearch(tablePtr, key, hashList) - Hash_Table *tablePtr; /* Hash table to search. */ - register Address key; /* A hash key. */ - register List_Links *hashList; -{ - register Hash_Entry *hashEntryPtr; - register int *hashKeyPtr; - int *keyPtr; - register int numKeys; - - numKeys = tablePtr->keyType; - LIST_FORALL(hashList, (List_Links *) hashEntryPtr) { - switch (numKeys) { - case 0: - if (strcmp(hashEntryPtr->key.name, key) == 0) { - return(hashEntryPtr); - } - break; - case 1: - if (hashEntryPtr->key.ptr == key) { - return(hashEntryPtr); - } - break; - case 2: - hashKeyPtr = hashEntryPtr->key.words; - keyPtr = (int *) key; - if (*hashKeyPtr++ == *keyPtr++ && *hashKeyPtr == *keyPtr) { - return(hashEntryPtr); - } - break; - default: - if (bcmp((Address) hashEntryPtr->key.words, - (Address) key, numKeys * sizeof(int))) { - return(hashEntryPtr); - } - break; - } - } - - /* - * The desired entry isn't there - */ - - return ((Hash_Entry *) NULL); -} - /* *--------------------------------------------------------- * @@ -611,44 +390,29 @@ ChainSearch(tablePtr, key, hashList) */ static void -RebuildTable(tablePtr) - Hash_Table *tablePtr; /* Table to be enlarged. */ +RebuildTable(t) + register Hash_Table *t; { - int oldSize; - int bucket; - List_Links *oldBucketPtr; - register Hash_Entry *hashEntryPtr; - register List_Links *oldHashList; - - oldBucketPtr = tablePtr->bucketPtr; - oldSize = tablePtr->size; - - /* - * Build a new table 4 times as large as the old one. - */ - - Hash_InitTable(tablePtr, tablePtr->size * 4, tablePtr->keyType); - - for (oldHashList = oldBucketPtr; oldSize > 0; oldSize--, oldHashList++) { - while (!List_IsEmpty(oldHashList)) { - hashEntryPtr = (Hash_Entry *) List_First(oldHashList); - List_Remove((List_Links *) hashEntryPtr); - switch (tablePtr->keyType) { - case HASH_STRING_KEYS: - bucket = Hash(tablePtr, (Address) hashEntryPtr->key.name); - break; - case HASH_ONE_WORD_KEYS: - bucket = Hash(tablePtr, (Address) hashEntryPtr->key.ptr); - break; - default: - bucket = Hash(tablePtr, (Address) hashEntryPtr->key.words); - break; - } - List_Insert((List_Links *) hashEntryPtr, - LIST_ATFRONT(&(tablePtr->bucketPtr[bucket]))); - tablePtr->numEntries++; + register Hash_Entry *e, *next, **hp, **xp; + register int i, mask; + register Hash_Entry **oldhp; + int oldsize; + + oldhp = t->bucketPtr; + oldsize = i = t->size; + i <<= 1; + t->size = i; + t->mask = mask = i - 1; + t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i); + while (--i >= 0) + *hp++ = NULL; + for (hp = oldhp, i = oldsize; --i >= 0;) { + for (e = *hp++; e != NULL; e = next) { + next = e->next; + xp = &t->bucketPtr[e->namehash & mask]; + e->next = *xp; + *xp = e; + } } - } - - free((Address) oldBucketPtr); + free((char *)oldhp); }