replace hash.c; speedup/cleanup from Chris Torek

[unix-history] / 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 780742c..0dca32b 100644 (file)
--- a/usr/src/usr.bin/make/hash.c
+++ b/usr/src/usr.bin/make/hash.c
@@ -11,7 +11,7 @@
  */
 
 #ifndef lint
  */
 
 #ifndef lint

-static char sccsid[] = "@(#)hash.c     5.4 (Berkeley) %G%";
+static char sccsid[] = "@(#)hash.c     5.5 (Berkeley) %G%";

 #endif /* not lint */
 
 /* hash.c --
 #endif /* not lint */
 
 /* hash.c --


@@ -24,15 +24,12 @@ static char sccsid[] = "@(#)hash.c  5.4 (Berkeley) %G%";
 
 #include "sprite.h"
 #include "hash.h"
 
 #include "sprite.h"
 #include "hash.h"

-#include "list.h"

 
 /*
  * Forward references to local procedures that are used before they're
  * defined:
  */
 
 
 /*
  * Forward references to local procedures that are used before they're
  * defined:
  */
 

-static Hash_Entry *    ChainSearch();
-static int             Hash();

 static void            RebuildTable();
 
 /* 
 static void            RebuildTable();
 
 /* 


@@ -40,8 +37,8 @@ static void           RebuildTable();
  * at which we rebuild the table to make it larger.
  */
 
  * at which we rebuild the table to make it larger.
  */
 

-static rebuildLimit = 3;
-\f
+#define rebuildLimit 8
+

 /*
  *---------------------------------------------------------
  * 
 /*
  *---------------------------------------------------------
  * 


@@ -59,56 +56,34 @@ static rebuildLimit = 3;
  */
 
 void
  */
 
 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;

 }
 }

-\f
+

 /*
  *---------------------------------------------------------
  *
 /*
  *---------------------------------------------------------
  *


@@ -128,33 +103,27 @@ Hash_InitTable(tablePtr, numBuckets, keyType)
  */
 
 void
  */
 
 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;

 }
 }

-\f
+

 /*
  *---------------------------------------------------------
  *
 /*
  *---------------------------------------------------------
  *


@@ -174,14 +143,23 @@ Hash_DeleteTable(tablePtr)
  */
 
 Hash_Entry *
  */
 
 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);

 }
 }

-\f
+

 /*
  *---------------------------------------------------------
  *
 /*
  *---------------------------------------------------------
  *


@@ -202,87 +180,55 @@ Hash_FindEntry(tablePtr, key)
  */
 
 Hash_Entry *
  */
 
 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);

 }
 }

-\f
+

 /*
  *---------------------------------------------------------
  *
 /*
  *---------------------------------------------------------
  *


@@ -301,17 +247,27 @@ Hash_CreateEntry(tablePtr, key, newPtr)
  */
 
 void
  */
 
 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();

 }
 }

-\f
+

 /*
  *---------------------------------------------------------
  *
 /*
  *---------------------------------------------------------
  *


@@ -324,7 +280,7 @@ Hash_DeleteEntry(tablePtr, hashEntryPtr)
  *     the hash table, or NULL if the table is empty.
  *
  * Side Effects:
  *     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.
  *
  *     calls to Hash_Next will return successive HashEntry's
  *     from the table.
  *


@@ -332,15 +288,15 @@ Hash_DeleteEntry(tablePtr, hashEntryPtr)
  */
 
 Hash_Entry *
  */
 
 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);

 }
 
 /*
 }
 
 /*


@@ -355,232 +311,41 @@ Hash_EnumFirst(tablePtr, hashSearchPtr)
  *    reached.
  *
  * Side Effects:
  *    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 *
  *    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. */
 {
                                            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);

 }
 }

-\f
-/*
- *---------------------------------------------------------
- *
- * 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);
-}
-\f
-/*
- *---------------------------------------------------------
- *
- * 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);
-}
-\f
-/*
- *---------------------------------------------------------
- *
- * 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);
-}
-\f

 /*
  *---------------------------------------------------------
  *
 /*
  *---------------------------------------------------------
  *


@@ -599,44 +364,29 @@ ChainSearch(tablePtr, key, hashList)
  */
 
 static void
  */
 
 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);

 }
 }