Return to hash.c CVS log

Up to [CSRG BSD Unix] / 43BSDReno / usr.bin / make

Annotation of 43BSDReno/usr.bin/make/hash.c, revision 1.1

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.