gcc/objc/hash.c

   1 /* -*-c-*-
   2  * This file contains the hashing implementation.
   3  *
   4  * Copyright (C) 1991 Threaded Technologies Inc.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published
   8  * by the Free Software Foundation; either version 1, or any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License for more details.
  14  *
  15  * You should receive a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18  *
  19   $Header: /usr/user/dennis_glatting/ObjC/c-runtime/hash/RCS/hash.c,v 0.11 1992/01/03 02:55:03 dennisg Exp dennisg $
  20   $Author: dennisg $
  21   $Date: 1992/01/03 02:55:03 $
  22   $Log: hash.c,v $
  23  * Revision 0.11  1992/01/03  02:55:03  dennisg
  24  * modified to handle new initialization scheme.
  25  * fixed code structure.
  26  *
  27  * Revision 0.10  1991/12/10  12:05:28  dennisg
  28  * Cleaned up file format for a distribution.
  29  *
  30  * Revision 0.9  1991/12/03  02:01:23  dennisg
  31  * fixed assert macro.
  32  * added memory allocation adjustment macro for hash size allocation.
  33  *
  34  * Revision 0.8  1991/11/24  01:20:02  dennisg
  35  * changed shorts back to ints.
  36  * the efficiency gained didn't out weight the grossness of the code.
  37  *
  38  * Revision 0.7  1991/11/23  22:18:29  dennisg
  39  * deleted hashIndex() and moved it to hash-inline.h
  40  * converted hash_value_for_key () to a inline and moved it to hash-inline.h.
  41  *
  42  * Revision 0.6  1991/11/21  22:27:06  dennisg
  43  * changed hash value calculation.
  44  * func name changed from hashValue () to hashIndex().  the
  45  * func really calculated a index anyway.
  46  * changed hash func impl.  essentially it was calculating a hash value
  47  * from a hash value.  this is a implementation thing.
  48  *
  49  * Revision 0.5  1991/11/20  23:29:20  dennisg
  50  * converted hashIndex() to a inline.
  51  *
  52  * Revision 0.4  1991/11/19  12:34:41  dennisg
  53  * bug in hash_delete ().  It was using void* to obtain nodes to
  54  * pass to hash_remove ().  The value passed to hash_removed () is a
  55  * entry from the node structure rather than the node itself.  Using
  56  * void* removed compiler checking.
  57  * Modified to implement cache expansion.
  58  *
  59  * Revision 0.3  1991/11/07  23:23:40  dennisg
  60  * implemented hash table expansion as suggested by rms.
  61  *
  62  * Revision 0.2  1991/11/07  22:30:54  dennisg
  63  * added copyleft
  64  *
  65  * Revision 0.1  1991/10/24  00:45:39  dennisg
  66  * Initial check in.  Preliminary development stage.
  67  *
  68 */
  69
  70
  71 #include  <hash.h>
  72 #include  <objc.h>
  73 #include  <objcP.h>
  74 #include  <objc-protoP.h>
  75
  76 #include  <assert.h>
  77 #include  <math.h>
  78 #include  <stdio.h>
  79 #include  <stdlib.h>
  80
  81
  82                                                 /* These two macros determine
  83                                                   when a hash table is full and
  84                                                   by how much it should be
  85                                                   expanded respectively.
  86
  87                                                   These equations are
  88                                                   percentages. */
  89 #define FULLNESS(cache) \
  90    ((((cache)->sizeOfHash * 75  ) / 100) <= (cache)->entriesInHash)
  91 #define EXPANSION(cache) \
  92   ((cache)->sizeOfHash * 2 )
  93
  94 Cache_t
  95 hash_new (u_int sizeOfHash, HashFunc aHashFunc, CompareFunc aCompareFunc) {
  96
  97   Cache_t retCache;
  98
  99
 100                                                                                                                                                                                                 /* Pass me a value greater
 101                                                                                                                                                                                                         than 0 and a power of 2. */
 102   assert(sizeOfHash);
 103         assert( !(sizeOfHash & (sizeOfHash - 1)));
 104
 105                                                 /* Allocate the cache
 106                                                   structure.  calloc () insures
 107                                                   its initialization for
 108                                                   default values. */
 109   retCache = calloc (1, sizeof (Cache));
 110   assert(retCache);
 111
 112                                                 /* Allocate the array of
 113                                                   buckets for the cache.
 114                                                   calloc() initializes all of
 115                                                   the pointers to NULL. */
 116   retCache->theNodeTable = calloc (sizeOfHash, sizeof (CacheNode_t));
 117   assert(retCache->theNodeTable);
 118
 119   retCache->sizeOfHash  = sizeOfHash;
 120
 121                                                                                                                                                                                                 /* This should work for all
 122                                                                                                                                                                                                         processor architectures? */
 123         retCache->mask = ( sizeOfHash - 1 );
 124
 125                                                                                                                                                                                                 /* Store the hashing function
 126                                                                                                                                                                                                         so that codes can be
 127                                                                                                                                                                                                         computed. */
 128         retCache->hashFunc = aHashFunc;
 129
 130                                                                                                                                                                                                 /* Store the function that
 131                                                                                                                                                                                                         compares hash keys to
 132                                                                                                                                                                                                         determine if they are
 133                                                                                                                                                                                                         equal. */
 134         retCache->compareFunc = aCompareFunc;
 135
 136   return retCache;
 137 }
 138
 139
 140 void
 141 hash_delete (Cache_t theCache) {
 142
 143   CacheNode_t aNode;
 144
 145
 146                                                /* Purge all key/value pairs
 147                                                   from the table. */
 148   while (aNode = hash_next (theCache, NULL))
 149     hash_remove (theCache, aNode->theKey);
 150
 151                                                 /* Release the array of nodes
 152                                                   and the cache itself. */
 153   free (theCache->theNodeTable);
 154   free (theCache);
 155 }
 156
 157
 158 void
 159 hash_add (Cache_t* theCache, void* aKey, void* aValue) {
 160
 161   u_int       indx = (* (*theCache)->hashFunc)(*theCache, aKey);
 162   CacheNode_t aCacheNode = calloc (1, sizeof (CacheNode));
 163
 164
 165   assert(aCacheNode);
 166
 167                                                 /* Initialize the new node. */
 168   aCacheNode->theKey    = aKey;
 169   aCacheNode->theValue  = aValue;
 170   aCacheNode->nextNode  = (* (*theCache)->theNodeTable)[ indx ];
 171
 172                                                 /* Debugging.
 173
 174                                                   Check the list for another
 175                                                   key. */
 176 #ifdef DEBUG
 177     { CacheNode_t checkHashNode = (* (*theCache)->theNodeTable)[ indx ];
 178
 179       while (checkHashNode) {
 180
 181         assert(checkHashNode->theKey != aKey);
 182         checkHashNode = checkHashNode->nextNode;
 183       }
 184     }
 185 #endif
 186
 187                                                 /* Install the node as the
 188                                                   first element on the list. */
 189   (* (*theCache)->theNodeTable)[ indx ] = aCacheNode;
 190
 191                                                 /* Bump the number of entries
 192                                                   in the cache. */
 193   ++ (*theCache)->entriesInHash;
 194
 195                                                 /* Check the hash table's
 196                                                   fullness.   We're going
 197                                                   to expand if it is above
 198                                                   the fullness level. */
 199   if (FULLNESS (*theCache)) {
 200                                                 /* The hash table has reached
 201                                                   its fullness level.  Time to
 202                                                   expand it.
 203
 204                                                   I'm using a slow method
 205                                                   here but is built on other
 206                                                   primitive functions thereby
 207                                                   increasing its
 208                                                   correctness. */
 209     CacheNode_t aNode = NULL;
 210     Cache_t     newCache = hash_new (EXPANSION (*theCache),
 211                                                                                                                                                  (*theCache)->hashFunc,
 212                                                                                                                                                  (*theCache)->compareFunc);
 213
 214     DEBUG_PRINTF (stderr, "Expanding cache %#x from %d to %d\n",
 215       *theCache, (*theCache)->sizeOfHash, newCache->sizeOfHash);
 216
 217                                                 /* Copy the nodes from the
 218                                                   first hash table to the
 219                                                   new one. */
 220     while (aNode = hash_next (*theCache, aNode))
 221       hash_add (&newCache, aNode->theKey, aNode->theValue);
 222
 223                                                 /* Trash the old cache. */
 224     hash_delete (*theCache);
 225
 226                                                 /* Return a pointer to the new
 227                                                   hash table. */
 228     *theCache = newCache;
 229   }
 230 }
 231
 232
 233 void
 234 hash_remove (Cache_t theCache, void* aKey) {
 235
 236   u_int       indx = (*theCache->hashFunc)(theCache, aKey);
 237   CacheNode_t aCacheNode = (*theCache->theNodeTable)[ indx ];
 238
 239
 240                                                 /* We assume there is an entry
 241                                                   in the table.  Error if it
 242                                                   is not. */
 243   assert(aCacheNode);
 244
 245                                                 /* Special case.  First element
 246                                                   is the key/value pair to be
 247                                                   removed. */
 248   if ((*theCache->compareFunc)(aCacheNode->theKey, aKey)) {
 249     (*theCache->theNodeTable)[ indx ] = aCacheNode->nextNode;
 250     free (aCacheNode);
 251   } else {
 252                                                 /* Otherwise, find the hash
 253                                                   entry. */
 254     CacheNode_t prevHashNode = aCacheNode;
 255     BOOL        removed = NO;
 256
 257     do {
 258
 259       if ((*theCache->compareFunc)(aCacheNode->theKey, aKey)) {
 260         prevHashNode->nextNode = aCacheNode->nextNode, removed = YES;
 261         free (aCacheNode);
 262       } else
 263         prevHashNode = aCacheNode, aCacheNode = aCacheNode->nextNode;
 264     } while (!removed && aCacheNode);
 265     assert(removed);
 266   }
 267
 268                                                 /* Decrement the number of
 269                                                   entries in the hash table. */
 270   --theCache->entriesInHash;
 271 }
 272
 273
 274 CacheNode_t
 275 hash_next (Cache_t theCache, CacheNode_t aCacheNode) {
 276
 277   CacheNode_t theCacheNode = aCacheNode;
 278
 279
 280                                                 /* If the scan is being started
 281                                                   then reset the last node
 282                                                   visitied pointer and bucket
 283                                                   index. */
 284   if (!theCacheNode)
 285     theCache->lastBucket  = 0;
 286
 287                                                 /* If there is a node visited
 288                                                   last then check for another
 289                                                   entry in the same bucket;
 290                                                   Otherwise step to the next
 291                                                   bucket. */
 292   if (theCacheNode)
 293     if (theCacheNode->nextNode)
 294                                                 /* There is a node which
 295                                                   follows the last node
 296                                                   returned.  Step to that node
 297                                                   and retun it. */
 298       return theCacheNode->nextNode;
 299     else
 300       ++theCache->lastBucket;
 301
 302                                                 /* If the list isn't exhausted
 303                                                   then search the buckets for
 304                                                   other nodes. */
 305   if (theCache->lastBucket < theCache->sizeOfHash) {
 306                                                 /*  Scan the remainder of the
 307                                                   buckets looking for an entry
 308                                                   at the head of the list.
 309                                                   Return the first item
 310                                                   found. */
 311     while (theCache->lastBucket < theCache->sizeOfHash)
 312       if ((*theCache->theNodeTable)[ theCache->lastBucket ])
 313         return (*theCache->theNodeTable)[ theCache->lastBucket ];
 314       else
 315         ++theCache->lastBucket;
 316
 317                                                 /* No further nodes were found
 318                                                   in the hash table. */
 319     return NULL;
 320   } else
 321     return NULL;
 322 }
 323
 324
 325                                                 /* Given key, return its
 326                                                   value.  Return NULL if the
 327                                                   key/value pair isn't in
 328                                                   the hash. */
 329 void*
 330 hash_value_for_key (Cache_t theCache, void* aKey) {
 331
 332   CacheNode_t aCacheNode =
 333               (*theCache->theNodeTable)[(*theCache->hashFunc)(theCache, aKey)];
 334   void*       retVal = NULL;
 335
 336
 337   if (aCacheNode)
 338     do {
 339       if ((*theCache->compareFunc)(aCacheNode->theKey, aKey))
 340         retVal = aCacheNode->theValue;
 341       else
 342         aCacheNode = aCacheNode->nextNode;
 343     } while (!retVal && aCacheNode);
 344
 345   return retVal;
 346 }