Changeset 51 for trunk/src/kmk/hash.c


Ignore:
Timestamp:
Apr 7, 2003, 3:30:32 AM (22 years ago)
Author:
bird
Message:

kMk and porting to kLib.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/kmk/hash.c

    r35 r51  
    1818 * 3. All advertising materials mentioning features or use of this software
    1919 *    must display the following acknowledgement:
    20  *      This product includes software developed by the University of
    21  *      California, Berkeley and its contributors.
     20 *      This product includes software developed by the University of
     21 *      California, Berkeley and its contributors.
    2222 * 4. Neither the name of the University nor the names of its contributors
    2323 *    may be used to endorse or promote products derived from this software
    … …  
    3939#ifndef lint
    4040#if 0
    41 static char sccsid[] = "@(#)hash.c      8.1 (Berkeley) 6/6/93";
     41static char sccsid[] = "@(#)hash.c      8.1 (Berkeley) 6/6/93";
    4242#else
    4343static const char rcsid[] =
    4444  "$FreeBSD: src/usr.bin/make/hash.c,v 1.9 1999/09/11 13:08:01 hoek Exp $";
    4545#endif
     46#define KLIBFILEDEF rcsid
    4647#endif /* not lint */
    4748
    4849/* hash.c --
    4950 *
    50  *      This module contains routines to manipulate a hash table.
    51  *      See hash.h for a definition of the structure of the hash
    52  *      table.  Hash tables grow automatically as the amount of
    53  *      information increases.
     51 *      This module contains routines to manipulate a hash table.
     52 *      See hash.h for a definition of the structure of the hash
     53 *      table.  Hash tables grow automatically as the amount of
     54 *      information increases.
    5455 */
    5556#include "sprite.h"
    … …  
    7677 * Hash_InitTable --
    7778 *
    78  *      This routine just sets up the hash table.
    79  *
    80  * Results:
    81  *      None.
    82  *
    83  * Side Effects:
    84  *      Memory is allocated for the initial bucket area.
     79 *      This routine just sets up the hash table.
     80 *
     81 * Results:
     82 *      None.
     83 *
     84 * Side Effects:
     85 *      Memory is allocated for the initial bucket area.
    8586 *
    8687 *---------------------------------------------------------
    … …  
    8990void
    9091Hash_InitTable(t, numBuckets)
    91         register Hash_Table *t; /* Structure to use to hold table. */
    92         int numBuckets;         /* How many buckets to create for starters.
    93                                 * This number is rounded up to a power of
    94                                 * two.   If <= 0, a reasonable default is
    95                                 * chosen. The table will grow in size later
    96                                 * as needed. */
    97 {
    98         register int i;
    99         register struct Hash_Entry **hp;
    100 
    101         /*
    102         * Round up the size to a power of two.
    103         */
    104         if (numBuckets <= 0)
    105                 i = 16;
    106         else {
    107                 for (i = 2; i < numBuckets; i <<= 1)
    108                         continue;
    109         }
    110         t->numEntries = 0;
    111         t->size = i;
    112         t->mask = i - 1;
    113         t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i);
    114         while (--i >= 0)
    115                 *hp++ = NULL;
     92        register Hash_Table *t; /* Structure to use to hold table. */
     93        int numBuckets;         /* How many buckets to create for starters.
     94                                * This number is rounded up to a power of
     95                                * two.   If <= 0, a reasonable default is
     96                                * chosen. The table will grow in size later
     97                                * as needed. */
     98{
     99        register int i;
     100        register struct Hash_Entry **hp;
     101
     102        /*
     103        * Round up the size to a power of two.
     104        */
     105        if (numBuckets <= 0)
     106                i = 16;
     107        else {
     108                for (i = 2; i < numBuckets; i <<= 1)
     109                        continue;
     110        }
     111        t->numEntries = 0;
     112        t->size = i;
     113        t->mask = i - 1;
     114        t->bucketPtr = hp = (struct Hash_Entry **)emalloc(sizeof(*hp) * i);
     115        while (--i >= 0)
     116                *hp++ = NULL;
    116117}
    117118
    … …  
    121122 * Hash_DeleteTable --
    122123 *
    123  *      This routine removes everything from a hash table
    124  *      and frees up the memory space it occupied (except for
    125  *      the space in the Hash_Table structure).
    126  *
    127  * Results:
    128  *      None.
    129  *
    130  * Side Effects:
    131  *      Lots of memory is freed up.
     124 *      This routine removes everything from a hash table
     125 *      and frees up the memory space it occupied (except for
     126 *      the space in the Hash_Table structure).
     127 *
     128 * Results:
     129 *      None.
     130 *
     131 * Side Effects:
     132 *      Lots of memory is freed up.
    132133 *
    133134 *---------------------------------------------------------
    … …  
    136137void
    137138Hash_DeleteTable(t)
    138         Hash_Table *t;
    139 {
    140         register struct Hash_Entry **hp, *h, *nexth = NULL;
    141         register int i;
    142 
    143         for (hp = t->bucketPtr, i = t->size; --i >= 0;) {
    144                 for (h = *hp++; h != NULL; h = nexth) {
    145                         nexth = h->next;
    146                         efree((char *)h);
    147                 }
    148         }
    149         efree((char *)t->bucketPtr);
    150 
    151         /*
    152         * Set up the hash table to cause memory faults on any future access
    153         * attempts until re-initialization.
    154         */
    155         t->bucketPtr = NULL;
     139        Hash_Table *t;
     140{
     141        register struct Hash_Entry **hp, *h, *nexth = NULL;
     142        register int i;
     143
     144        for (hp = t->bucketPtr, i = t->size; --i >= 0;) {
     145                for (h = *hp++; h != NULL; h = nexth) {
     146                        nexth = h->next;
     147                        efree((char *)h);
     148                }
     149        }
     150        efree((char *)t->bucketPtr);
     151
     152        /*
     153        * Set up the hash table to cause memory faults on any future access
     154        * attempts until re-initialization.
     155        */
     156        t->bucketPtr = NULL;
    156157}
    157158
    … …  
    161162 * Hash_FindEntry --
    162163 *
    163  *      Searches a hash table for an entry corresponding to key.
    164  *
    165  * Results:
    166  *      The return value is a pointer to the entry for key,
    167  *      if key was present in the table.  If key was not
    168  *      present, NULL is returned.
    169  *
    170  * Side Effects:
    171  *      None.
     164 *      Searches a hash table for an entry corresponding to key.
     165 *
     166 * Results:
     167 *      The return value is a pointer to the entry for key,
     168 *      if key was present in the table.  If key was not
     169 *      present, NULL is returned.
     170 *
     171 * Side Effects:
     172 *      None.
    172173 *
    173174 *---------------------------------------------------------
    … …  
    176177Hash_Entry *
    177178Hash_FindEntry(t, key)
    178         Hash_Table *t;          /* Hash table to search. */
    179         char *key;              /* A hash key. */
    180 {
    181         register Hash_Entry *e;
    182         register unsigned h;
    183         register char *p;
    184 
    185         for (h = 0, p = key; *p;)
    186                 h = (h << 5) - h + *p++;
    187         p = key;
    188         for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)
    189                 if (e->namehash == h && strcmp(e->name, p) == 0)
    190                         return (e);
    191         return (NULL);
     179        Hash_Table *t;          /* Hash table to search. */
     180        char *key;              /* A hash key. */
     181{
     182        register Hash_Entry *e;
     183        register unsigned h;
     184        register char *p;
     185
     186        for (h = 0, p = key; *p;)
     187                h = (h << 5) - h + *p++;
     188        p = key;
     189        for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next)
     190                if (e->namehash == h && strcmp(e->name, p) == 0)
     191                        return (e);
     192        return (NULL);
    192193}
    193194
    … …  
    197198 * Hash_CreateEntry --
    198199 *
    199  *      Searches a hash table for an entry corresponding to
    200  *      key.  If no entry is found, then one is created.
    201  *
    202  * Results:
    203  *      The return value is a pointer to the entry.  If *newPtr
    204  *      isn't NULL, then *newPtr is filled in with TRUE if a
    205  *      new entry was created, and FALSE if an entry already existed
    206  *      with the given key.
    207  *
    208  * Side Effects:
    209  *      Memory may be allocated, and the hash buckets may be modified.
     200 *      Searches a hash table for an entry corresponding to
     201 *      key.  If no entry is found, then one is created.
     202 *
     203 * Results:
     204 *      The return value is a pointer to the entry.  If *newPtr
     205 *      isn't NULL, then *newPtr is filled in with TRUE if a
     206 *      new entry was created, and FALSE if an entry already existed
     207 *      with the given key.
     208 *
     209 * Side Effects:
     210 *      Memory may be allocated, and the hash buckets may be modified.
    210211 *---------------------------------------------------------
    211212 */
    … …  
    213214Hash_Entry *
    214215Hash_CreateEntry(t, key, newPtr)
    215         register Hash_Table *t; /* Hash table to search. */
    216         char *key;              /* A hash key. */
    217         Boolean *newPtr;        /* Filled in with TRUE if new entry created,
    218                                 * FALSE otherwise. */
    219 {
    220         register Hash_Entry *e;
    221         register unsigned h;
    222         register char *p;
    223         int keylen;
    224         struct Hash_Entry **hp;
    225 
    226         /*
    227         * Hash the key.  As a side effect, save the length (strlen) of the
    228         * key in case we need to create the entry.
    229         */
    230         for (h = 0, p = key; *p;)
    231                 h = (h << 5) - h + *p++;
    232         keylen = p - key;
    233         p = key;
    234         for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
    235                 if (e->namehash == h && strcmp(e->name, p) == 0) {
    236                         if (newPtr != NULL)
    237                                 *newPtr = FALSE;
    238                         return (e);
    239                 }
    240         }
    241 
    242         /*
    243         * The desired entry isn't there.  Before allocating a new entry,
    244         * expand the table if necessary (and this changes the resulting
    245         * bucket chain).
    246         */
    247         if (t->numEntries >= rebuildLimit * t->size)
    248                 RebuildTable(t);
    249         e = (Hash_Entry *) emalloc(sizeof(*e) + keylen);
    250         hp = &t->bucketPtr[h & t->mask];
    251         e->next = *hp;
    252         *hp = e;
    253         e->clientData = NULL;
    254         e->namehash = h;
    255         (void) strcpy(e->name, p);
    256         t->numEntries++;
    257 
    258         if (newPtr != NULL)
    259                 *newPtr = TRUE;
    260         return (e);
     216        register Hash_Table *t; /* Hash table to search. */
     217        char *key;              /* A hash key. */
     218        Boolean *newPtr;        /* Filled in with TRUE if new entry created,
     219                                * FALSE otherwise. */
     220{
     221        register Hash_Entry *e;
     222        register unsigned h;
     223        register char *p;
     224        int keylen;
     225        struct Hash_Entry **hp;
     226
     227        /*
     228        * Hash the key.  As a side effect, save the length (strlen) of the
     229        * key in case we need to create the entry.
     230        */
     231        for (h = 0, p = key; *p;)
     232                h = (h << 5) - h + *p++;
     233        keylen = p - key;
     234        p = key;
     235        for (e = t->bucketPtr[h & t->mask]; e != NULL; e = e->next) {
     236                if (e->namehash == h && strcmp(e->name, p) == 0) {
     237                        if (newPtr != NULL)
     238                                *newPtr = FALSE;
     239                        return (e);
     240                }
     241        }
     242
     243        /*
     244        * The desired entry isn't there.  Before allocating a new entry,
     245        * expand the table if necessary (and this changes the resulting
     246        * bucket chain).
     247        */
     248        if (t->numEntries >= rebuildLimit * t->size)
     249                RebuildTable(t);
     250        e = (Hash_Entry *) emalloc(sizeof(*e) + keylen);
     251        hp = &t->bucketPtr[h & t->mask];
     252        e->next = *hp;
     253        *hp = e;
     254        e->clientData = NULL;
     255        e->namehash = h;
     256        (void) strcpy(e->name, p);
     257        t->numEntries++;
     258
     259        if (newPtr != NULL)
     260                *newPtr = TRUE;
     261        return (e);
    261262}
    262263
    … …  
    266267 * Hash_DeleteEntry --
    267268 *
    268  *      Delete the given hash table entry and efree memory associated with
    269  *      it.
    270  *
    271  * Results:
    272  *      None.
    273  *
    274  * Side Effects:
    275  *      Hash chain that entry lives in is modified and memory is freed.
     269 *      Delete the given hash table entry and efree memory associated with
     270 *      it.
     271 *
     272 * Results:
     273 *      None.
     274 *
     275 * Side Effects:
     276 *      Hash chain that entry lives in is modified and memory is freed.
    276277 *
    277278 *---------------------------------------------------------
    … …  
    280281void
    281282Hash_DeleteEntry(t, e)
    282         Hash_Table *t;
    283         Hash_Entry *e;
    284 {
    285         register Hash_Entry **hp, *p;
    286 
    287         if (e == NULL)
    288                 return;
    289         for (hp = &t->bucketPtr[e->namehash & t->mask];
    290              (p = *hp) != NULL; hp = &p->next) {
    291                 if (p == e) {
    292                         *hp = p->next;
    293                         efree((char *)p);
    294                         t->numEntries--;
    295                         return;
    296                 }
    297         }
    298         (void) write(2, "bad call to Hash_DeleteEntry\n", 29);
    299         abort();
     283        Hash_Table *t;
     284        Hash_Entry *e;
     285{
     286        register Hash_Entry **hp, *p;
     287
     288        if (e == NULL)
     289                return;
     290        for (hp = &t->bucketPtr[e->namehash & t->mask];
     291             (p = *hp) != NULL; hp = &p->next) {
     292                if (p == e) {
     293                        *hp = p->next;
     294                        efree((char *)p);
     295                        t->numEntries--;
     296                        return;
     297                }
     298        }
     299        (void) write(STDERR_FILENO, "bad call to Hash_DeleteEntry\n", 29);
     300        abort();
    300301}
    301302
    … …  
    304305 *
    305306 * Hash_EnumFirst --
    306  *      This procedure sets things up for a complete search
    307  *      of all entries recorded in the hash table.
    308  *
    309  * Results:
    310  *      The return value is the address of the first entry in
    311  *      the hash table, or NULL if the table is empty.
    312  *
    313  * Side Effects:
    314  *      The information in searchPtr is initialized so that successive
    315  *      calls to Hash_Next will return successive HashEntry's
    316  *      from the table.
     307 *      This procedure sets things up for a complete search
     308 *      of all entries recorded in the hash table.
     309 *
     310 * Results:
     311 *      The return value is the address of the first entry in
     312 *      the hash table, or NULL if the table is empty.
     313 *
     314 * Side Effects:
     315 *      The information in searchPtr is initialized so that successive
     316 *      calls to Hash_Next will return successive HashEntry's
     317 *      from the table.
    317318 *
    318319 *---------------------------------------------------------
    … …  
    321322Hash_Entry *
    322323Hash_EnumFirst(t, searchPtr)
    323         Hash_Table *t;                  /* Table to be searched. */
    324         register Hash_Search *searchPtr;/* Area in which to keep state
    325                                         * about search.*/
    326 {
    327         searchPtr->tablePtr = t;
    328         searchPtr->nextIndex = 0;
    329         searchPtr->hashEntryPtr = NULL;
    330         return Hash_EnumNext(searchPtr);
     324        Hash_Table *t;                  /* Table to be searched. */
     325        register Hash_Search *searchPtr;/* Area in which to keep state
     326                                        * about search.*/
     327{
     328        searchPtr->tablePtr = t;
     329        searchPtr->nextIndex = 0;
     330        searchPtr->hashEntryPtr = NULL;
     331        return Hash_EnumNext(searchPtr);
    331332}
    332333
    … …  
    351352Hash_Entry *
    352353Hash_EnumNext(searchPtr)
    353         register Hash_Search *searchPtr; /* Area used to keep state about
    354                                             search. */
    355 {
    356         register Hash_Entry *e;
    357         Hash_Table *t = searchPtr->tablePtr;
    358 
    359         /*
    360         * The hashEntryPtr field points to the most recently returned
    361         * entry, or is nil if we are starting up.  If not nil, we have
    362         * to start at the next one in the chain.
    363         */
    364         e = searchPtr->hashEntryPtr;
    365         if (e != NULL)
    366                 e = e->next;
    367         /*
    368         * If the chain ran out, or if we are starting up, we need to
    369         * find the next nonempty chain.
    370         */
    371         while (e == NULL) {
    372                 if (searchPtr->nextIndex >= t->size)
    373                         return (NULL);
    374                 e = t->bucketPtr[searchPtr->nextIndex++];
    375         }
    376         searchPtr->hashEntryPtr = e;
    377         return (e);
     354        register Hash_Search *searchPtr; /* Area used to keep state about
     355                                            search. */
     356{
     357        register Hash_Entry *e;
     358        Hash_Table *t = searchPtr->tablePtr;
     359
     360        /*
     361        * The hashEntryPtr field points to the most recently returned
     362        * entry, or is nil if we are starting up.  If not nil, we have
     363        * to start at the next one in the chain.
     364        */
     365        e = searchPtr->hashEntryPtr;
     366        if (e != NULL)
     367                e = e->next;
     368        /*
     369        * If the chain ran out, or if we are starting up, we need to
     370        * find the next nonempty chain.
     371        */
     372        while (e == NULL) {
     373                if (searchPtr->nextIndex >= t->size)
     374                        return (NULL);
     375                e = t->bucketPtr[searchPtr->nextIndex++];
     376        }
     377        searchPtr->hashEntryPtr = e;
     378        return (e);
    378379}
    379380
    … …  
    382383 *
    383384 * RebuildTable --
    384  *      This local routine makes a new hash table that
    385  *      is larger than the old one.
    386  *
    387  * Results:
    388  *      None.
    389  *
    390  * Side Effects:
    391  *      The entire hash table is moved, so any bucket numbers
    392  *      from the old table are invalid.
     385 *      This local routine makes a new hash table that
     386 *      is larger than the old one.
     387 *
     388 * Results:
     389 *      None.
     390 *
     391 * Side Effects:
     392 *      The entire hash table is moved, so any bucket numbers
     393 *      from the old table are invalid.
    393394 *
    394395 *---------------------------------------------------------
    … …  
    397398static void
    398399RebuildTable(t)
    399         register Hash_Table *t;
    400 {
    401         register Hash_Entry *e, *next = NULL, **hp, **xp;
    402         register int i, mask;
     400        register Hash_Table *t;
     401{
     402        register Hash_Entry *e, *next = NULL, **hp, **xp;
     403        register int i, mask;
    403404        register Hash_Entry **oldhp;
    404         int oldsize;
    405 
    406         oldhp = t->bucketPtr;
    407         oldsize = i = t->size;
    408         i <<= 1;
    409         t->size = i;
    410         t->mask = mask = i - 1;
    411         t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i);
    412         while (--i >= 0)
    413                 *hp++ = NULL;
    414         for (hp = oldhp, i = oldsize; --i >= 0;) {
    415                 for (e = *hp++; e != NULL; e = next) {
    416                         next = e->next;
    417                         xp = &t->bucketPtr[e->namehash & mask];
    418                         e->next = *xp;
    419                         *xp = e;
    420                 }
    421         }
    422         efree((char *)oldhp);
    423 }
     405        int oldsize;
     406
     407        oldhp = t->bucketPtr;
     408        oldsize = i = t->size;
     409        i <<= 1;
     410        t->size = i;
     411        t->mask = mask = i - 1;
     412        t->bucketPtr = hp = (struct Hash_Entry **) emalloc(sizeof(*hp) * i);
     413        while (--i >= 0)
     414                *hp++ = NULL;
     415        for (hp = oldhp, i = oldsize; --i >= 0;) {
     416                for (e = *hp++; e != NULL; e = next) {
     417                        next = e->next;
     418                        xp = &t->bucketPtr[e->namehash & mask];
     419                        e->next = *xp;
     420                        *xp = e;
     421                }
     422        }
     423        efree((char *)oldhp);
     424}
Note: See TracChangeset for help on using the changeset viewer.