err.no Git - sope/blob - gnustep-objc/hash.h

   1 /* Hash tables for Objective C method dispatch.
   2    Copyright (C) 1993, 1995, 1996 Free Software Foundation, Inc.
   3
   4 This file is part of GNU CC.
   5
   6 GNU CC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 2, or (at your option)
   9 any later version.
  10
  11 GNU CC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GNU CC; see the file COPYING.  If not, write to
  18 the Free Software Foundation, 59 Temple Place - Suite 330,
  19 Boston, MA 02111-1307, USA.  */
  20
  21 /* As a special exception, if you link this library with files
  22    compiled with GCC to produce an executable, this does not cause
  23    the resulting executable to be covered by the GNU General Public License.
  24    This exception does not however invalidate any other reasons why
  25    the executable file might be covered by the GNU General Public License.  */
  26
  27
  28 #ifndef __hash_INCLUDE_GNU
  29 #define __hash_INCLUDE_GNU
  30
  31 #include <stddef.h>
  32 #include <stdlib.h>
  33 #include <objc/objc.h>
  34 #include <objc/objc-api.h>
  35
  36 /*
  37  * This data structure is used to hold items
  38  *  stored in a hash table.  Each node holds
  39  *  a key/value pair.
  40  *
  41  * Items in the cache are really of type void *.
  42  */
  43 typedef struct cache_node
  44 {
  45   struct cache_node *next;      /* Pointer to next entry on the list.
  46                                    NULL indicates end of list. */
  47   const void *key;              /* Key used to locate the value.  Used
  48                                    to locate value when more than one
  49                                    key computes the same hash
  50                                    value. */
  51   void *value;                  /* Value stored for the key. */
  52 } *node_ptr;
  53
  54 /*
  55  * This data structure is the cache.
  56  *
  57  * It must be passed to all of the hashing routines
  58  *   (except for new).
  59  */
  60 typedef struct cache
  61 {
  62   /* Variables used to implement the hash itself.  */
  63   node_ptr *node_table; /* Pointer to an array of hash nodes.  */
  64   /* Variables used to track the size of the hash table so to determine
  65     when to resize it.  */
  66   unsigned int size; /* Number of buckets allocated for the hash table
  67                         (number of array entries allocated for
  68                         "node_table").  Must be a power of two.  */
  69   unsigned int used; /* Current number of entries in the hash table.  */
  70   unsigned int mask; /* Precomputed mask.  */
  71
  72   /* Variables used to implement indexing through the hash table.  */
  73
  74   unsigned int last_bucket; /* Tracks which entry in the array where
  75                                the last value was returned.  */
  76
  77   char hashType; // 1 = string-hash, 0 = ptr-hash
  78 } *cache_ptr;
  79
  80 static __inline__ unsigned int objc_call_hash(cache_ptr cache, const void *key)
  81 {
  82   if (cache->hashType == 1) { // string hash
  83     register unsigned int ret = 0;
  84     register unsigned int ctr = 0;
  85
  86     while (*(char*)key) {
  87       ret ^= *(char*)key++ << ctr;
  88       ctr = (ctr + 1) % sizeof (void *);
  89     }
  90
  91     return (ret & cache->mask);
  92   }
  93   else if (cache->hashType == 0) // ptr hash
  94     return ((size_t)key / sizeof (void *)) & cache->mask;
  95   else
  96     abort();
  97 }
  98 static __inline__ int objc_call_compare(cache_ptr cache,
  99                                         const void *k1, const void *k2)
 100 {
 101   if (cache->hashType == 1) { // string compare
 102     if (k1 == k2)
 103       return 1;
 104     else if (k1 == 0 || k2 == 0)
 105       return 0;
 106     else {
 107       while ((*(char*)k1 == *(char*)k2) && (*(char*)k1 != '\0'))
 108         k1++, k2++;
 109
 110       return (*(char*)k1 == *(char*)k2) ? 1 : 0;
 111     }
 112   }
 113   else if (cache->hashType == 0) // ptr compare
 114     return !(k1 - k2);
 115   else
 116     abort();
 117 }
 118
 119 /* Two important hash tables.  */
 120 objc_EXPORT cache_ptr module_hash_table, class_hash_table;
 121
 122 #include <objc/objc-mem.h>
 123
 124 static __inline__ void hash_delete(cache_ptr cache);
 125 static __inline__ void hash_remove(cache_ptr cache, const void *key);
 126 static __inline__ unsigned int hash_ptr(cache_ptr cache, const void *key);
 127 static __inline__ int compare_ptrs(register const void *k1, register const void *k2);
 128 static __inline__ unsigned int hash_string(cache_ptr cache,register const void *key);
 129
 130 static __inline__ int
 131 compare_strings(register const char *k1,register const char *k2);
 132
 133 /* Allocate and initialize a hash table.  */
 134
 135 static __inline__ cache_ptr ptrhash_new(unsigned int size) {
 136   cache_ptr hash_new (unsigned int size,
 137                       char hashType);
 138   return hash_new(size, 0);
 139 }
 140 static __inline__ cache_ptr strhash_new(unsigned int size) {
 141   cache_ptr hash_new (unsigned int size,
 142                       char hashType);
 143   return hash_new(size, 1);
 144 }
 145
 146 /* Deallocate all of the hash nodes and the cache itself.  */
 147
 148 static __inline__ void hash_delete (cache_ptr cache) {
 149   node_ptr node;
 150   node_ptr next_node;
 151   unsigned int i;
 152
 153   /* Purge all key/value pairs from the table.  */
 154   /* Step through the nodes one by one and remove every node WITHOUT
 155      using hash_next. this makes hash_delete much more efficient. */
 156   for (i = 0;i < cache->size;i++) {
 157     if ((node = cache->node_table[i])) {
 158       /* an entry in the hash table has been found, now step through the
 159          nodes next in the list and free them. */
 160       while ((next_node = node->next)) {
 161         hash_remove (cache,node->key);
 162         node = next_node;
 163       }
 164
 165       hash_remove (cache,node->key);
 166     }
 167   }
 168
 169   /* Release the array of nodes and the cache itself.  */
 170 #if OBJC_WITH_GC
 171   GC_FREE(cache->node_table); cache->node_table = NULL;
 172   GC_FREE(cache); cache = NULL;
 173 #else
 174   objc_free(cache->node_table);
 175   objc_free(cache);
 176 #endif
 177 }
 178
 179 /* Add the key/value pair to the hash table.  If the
 180    hash table reaches a level of fullness then it will be resized.
 181
 182    assert if the key is already in the hash.  */
 183
 184 void hash_add (cache_ptr *cachep, const void *key, void *value);
 185
 186 /* Remove the key/value pair from the hash table.
 187    assert if the key isn't in the table.  */
 188
 189 static __inline__ void hash_remove (cache_ptr cache, const void *key) {
 190   size_t indx = objc_call_hash(cache, key);
 191   //size_t indx = (*cache->hash_func)(cache, key);
 192   node_ptr node = cache->node_table[indx];
 193
 194
 195   /* We assume there is an entry in the table.  Error if it is not.  */
 196   if (node == NULL) abort();
 197
 198   /* Special case.  First element is the key/value pair to be removed.  */
 199   //if ((*cache->compare_func)(node->key, key)) {
 200   if (objc_call_compare(cache, node->key, key)) {
 201     cache->node_table[indx] = node->next;
 202 #if OBJC_WITH_GC
 203     GC_FREE(node); node = NULL;
 204 #else
 205     objc_free(node);
 206 #endif
 207   }
 208   else {
 209     /* Otherwise, find the hash entry.  */
 210     node_ptr prev = node;
 211     BOOL removed = NO;
 212
 213     do {
 214       //if ((*cache->compare_func)(node->key, key)) {
 215       if (objc_call_compare(cache, node->key, key)) {
 216         prev->next = node->next, removed = YES;
 217 #if OBJC_WITH_GC
 218         GC_FREE(node); node = NULL;
 219 #else
 220         objc_free(node);
 221 #endif
 222       } else {
 223         prev = node, node = node->next;
 224       }
 225     } while (!removed && node);
 226     if(removed==0) abort();
 227   }
 228
 229   /* Decrement the number of entries in the hash table.  */
 230   --cache->used;
 231 }
 232
 233 /* Used to index through the hash table.  Start with NULL
 234    to get the first entry.
 235
 236    Successive calls pass the value returned previously.
 237    ** Don't modify the hash during this operation ***
 238
 239    Cache nodes are returned such that key or value can
 240    be extracted.  */
 241
 242 static __inline__ node_ptr hash_next (cache_ptr cache, node_ptr node) {
 243   /* If the scan is being started then reset the last node
 244      visitied pointer and bucket index.  */
 245   if (!node)
 246     cache->last_bucket  = 0;
 247
 248   /* If there is a node visited last then check for another
 249      entry in the same bucket;  Otherwise step to the next bucket.  */
 250   if (node) {
 251     if (node->next)
 252       /* There is a node which follows the last node
 253          returned.  Step to that node and retun it.  */
 254       return node->next;
 255     else
 256       ++cache->last_bucket;
 257   }
 258
 259   /* If the list isn't exhausted then search the buckets for
 260      other nodes.  */
 261   if (cache->last_bucket < cache->size) {
 262     /*  Scan the remainder of the buckets looking for an entry
 263         at the head of the list.  Return the first item found.  */
 264     while (cache->last_bucket < cache->size)
 265       if (cache->node_table[cache->last_bucket])
 266         return cache->node_table[cache->last_bucket];
 267       else
 268         ++cache->last_bucket;
 269
 270     /* No further nodes were found in the hash table.  */
 271     return NULL;
 272   } else
 273     return NULL;
 274 }
 275
 276 /* Used to return a value from a hash table using a given key.  */
 277
 278 static __inline__ void *hash_value_for_key (cache_ptr cache, const void *key) {
 279   /* Given KEY, return corresponding value for it in CACHE.
 280      Return NULL if the KEY is not recorded.  */
 281
 282   node_ptr node    = cache->node_table[objc_call_hash(cache, key)];
 283   //node_ptr node    = cache->node_table[(*cache->hash_func)(cache, key)];
 284   void     *retval = NULL;
 285
 286   if (node)
 287     do {
 288       //if ((*cache->compare_func)(node->key, key)) {
 289       if (objc_call_compare(cache, node->key, key)) {
 290         retval = node->value;
 291               break;
 292       } else
 293         node = node->next;
 294     } while (!retval && node);
 295
 296   return retval;
 297 }
 298
 299 /* Used to determine if the given key exists in the hash table */
 300
 301 static __inline__ BOOL hash_is_key_in_hash (cache_ptr cache, const void *key) {
 302   /* Given KEY, return YES if it exists in the CACHE.
 303      Return NO if it does not */
 304
 305   //node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
 306   register node_ptr node = cache->node_table[objc_call_hash(cache, key)];
 307
 308   if (node) {
 309     do {
 310       //if ((*cache->compare_func)(node->key, key))
 311       if (objc_call_compare(cache, node->key, key))
 312           return YES;
 313
 314       node = node->next;
 315     } while (node);
 316   }
 317   return NO;
 318 }
 319
 320 /************************************************
 321
 322         Useful hashing functions.
 323
 324         Declared inline for your pleasure.
 325
 326 ************************************************/
 327
 328 /* Calculate a hash code by performing some
 329    manipulation of the key pointer.  (Use the lowest bits
 330    except for those likely to be 0 due to alignment.)  */
 331
 332 static __inline__ unsigned int hash_ptr (cache_ptr cache, const void *key)
 333 {
 334   return ((size_t)key / sizeof (void *)) & cache->mask;
 335 }
 336
 337
 338 /* Calculate a hash code by iterating over a NULL
 339    terminate string.  */
 340 static __inline__ unsigned int
 341 hash_string (cache_ptr cache,register const void *key)
 342 {
 343   register unsigned int ret = 0;
 344   register unsigned int ctr = 0;
 345
 346   while (*(char*)key) {
 347     ret ^= *(char*)key++ << ctr;
 348     ctr = (ctr + 1) % sizeof (void *);
 349   }
 350
 351   return (ret & cache->mask);
 352 }
 353
 354
 355 /* Compare two pointers for equality.  */
 356 static __inline__ int
 357 compare_ptrs (register const void *k1, register const void *k2)
 358 {
 359   return !(k1 - k2);
 360 }
 361
 362
 363 /* Compare two strings.  */
 364 static __inline__ int
 365 compare_strings(register const char *k1,register const char *k2)
 366 {
 367   if (k1 == k2)
 368     return 1;
 369   else if (k1 == 0 || k2 == 0)
 370     return 0;
 371   else {
 372     while ((*k1 == *k2) && (*k1 != '\0')) {
 373       k1++;
 374       k2++;
 375     }
 376     return (*k1 == *k2) ? 1 : 0;
 377
 378     //return !strcmp (k1, k2);
 379   }
 380 }
 381
 382 #endif /* not __hash_INCLUDE_GNU */