libobjc/hash.c

   1 /* Hash tables for Objective C internal structures
   2    Copyright (C) 1993, 1996, 1997, 2004, 2009 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC 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 3, or (at your option)
   9 any later version.
  10
  11 GCC 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 Under Section 7 of GPL version 3, you are granted additional
  17 permissions described in the GCC Runtime Library Exception, version
  18 3.1, as published by the Free Software Foundation.
  19
  20 You should have received a copy of the GNU General Public License and
  21 a copy of the GCC Runtime Library Exception along with this program;
  22 see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 <http://www.gnu.org/licenses/>.  */
  24
  25 #include "assert.h"
  26
  27 #include "objc/hash.h"
  28
  29 #include "objc/runtime.h"               /* for DEBUG_PRINTF */
  30
  31 /* These two macros determine when a hash table is full and
  32    by how much it should be expanded respectively.
  33
  34    These equations are percentages.  */
  35 #define FULLNESS(cache) \
  36    ((((cache)->size * 75) / 100) <= (cache)->used)
  37 #define EXPANSION(cache) \
  38   ((cache)->size * 2)
  39
  40 cache_ptr
  41 objc_hash_new (unsigned int size, hash_func_type hash_func,
  42                compare_func_type compare_func)
  43 {
  44   cache_ptr cache;
  45
  46   /* Pass me a value greater than 0 and a power of 2.  */
  47   assert (size);
  48   assert (! (size & (size - 1)));
  49
  50   /* Allocate the cache structure.  calloc insures
  51      its initialization for default values.  */
  52   cache = (cache_ptr) objc_calloc (1, sizeof (struct cache));
  53   assert (cache);
  54
  55   /* Allocate the array of buckets for the cache.
  56      calloc initializes all of the pointers to NULL.  */
  57   cache->node_table
  58     = (node_ptr *) objc_calloc (size, sizeof (node_ptr));
  59   assert (cache->node_table);
  60
  61   cache->size  = size;
  62
  63   /* This should work for all processor architectures? */
  64   cache->mask = (size - 1);
  65
  66   /* Store the hashing function so that codes can be computed.  */
  67   cache->hash_func = hash_func;
  68
  69   /* Store the function that compares hash keys to
  70      determine if they are equal.  */
  71   cache->compare_func = compare_func;
  72
  73   return cache;
  74 }
  75
  76
  77 void
  78 objc_hash_delete (cache_ptr cache)
  79 {
  80   node_ptr node;
  81   node_ptr next_node;
  82   unsigned int i;
  83
  84   /* Purge all key/value pairs from the table.  */
  85   /* Step through the nodes one by one and remove every node WITHOUT
  86      using objc_hash_next. this makes objc_hash_delete much more efficient. */
  87   for (i = 0;i < cache->size;i++) {
  88     if ((node = cache->node_table[i])) {
  89       /* an entry in the hash table has been found, now step through the
  90          nodes next in the list and free them. */
  91       while ((next_node = node->next)) {
  92         objc_hash_remove (cache,node->key);
  93         node = next_node;
  94       }
  95
  96       objc_hash_remove (cache,node->key);
  97     }
  98   }
  99
 100   /* Release the array of nodes and the cache itself.  */
 101   objc_free(cache->node_table);
 102   objc_free(cache);
 103 }
 104
 105
 106 void
 107 objc_hash_add (cache_ptr *cachep, const void *key, void *value)
 108 {
 109   size_t indx = (*(*cachep)->hash_func)(*cachep, key);
 110   node_ptr node = (node_ptr) objc_calloc (1, sizeof (struct cache_node));
 111
 112
 113   assert (node);
 114
 115   /* Initialize the new node.  */
 116   node->key    = key;
 117   node->value  = value;
 118   node->next  = (*cachep)->node_table[indx];
 119
 120   /* Debugging.
 121      Check the list for another key.  */
 122 #ifdef DEBUG
 123   { node_ptr node1 = (*cachep)->node_table[indx];
 124
 125     while (node1) {
 126
 127       assert (node1->key != key);
 128       node1 = node1->next;
 129     }
 130   }
 131 #endif
 132
 133   /* Install the node as the first element on the list.  */
 134   (*cachep)->node_table[indx] = node;
 135
 136   /* Bump the number of entries in the cache.  */
 137   ++(*cachep)->used;
 138
 139   /* Check the hash table's fullness.   We're going
 140      to expand if it is above the fullness level.  */
 141   if (FULLNESS (*cachep)) {
 142
 143     /* The hash table has reached its fullness level.  Time to
 144        expand it.
 145
 146        I'm using a slow method here but is built on other
 147        primitive functions thereby increasing its
 148        correctness.  */
 149     node_ptr node1 = NULL;
 150     cache_ptr new = objc_hash_new (EXPANSION (*cachep),
 151                                    (*cachep)->hash_func,
 152                                    (*cachep)->compare_func);
 153
 154     DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
 155                   (int) *cachep, (*cachep)->size, new->size);
 156
 157     /* Copy the nodes from the first hash table to the new one.  */
 158     while ((node1 = objc_hash_next (*cachep, node1)))
 159       objc_hash_add (&new, node1->key, node1->value);
 160
 161     /* Trash the old cache.  */
 162     objc_hash_delete (*cachep);
 163
 164     /* Return a pointer to the new hash table.  */
 165     *cachep = new;
 166   }
 167 }
 168
 169
 170 void
 171 objc_hash_remove (cache_ptr cache, const void *key)
 172 {
 173   size_t indx = (*cache->hash_func)(cache, key);
 174   node_ptr node = cache->node_table[indx];
 175
 176
 177   /* We assume there is an entry in the table.  Error if it is not.  */
 178   assert (node);
 179
 180   /* Special case.  First element is the key/value pair to be removed.  */
 181   if ((*cache->compare_func)(node->key, key)) {
 182     cache->node_table[indx] = node->next;
 183     objc_free(node);
 184   } else {
 185
 186     /* Otherwise, find the hash entry.  */
 187     node_ptr prev = node;
 188     BOOL removed = NO;
 189
 190     do {
 191
 192       if ((*cache->compare_func)(node->key, key)) {
 193         prev->next = node->next, removed = YES;
 194         objc_free(node);
 195       } else
 196         prev = node, node = node->next;
 197     } while (! removed && node);
 198     assert (removed);
 199   }
 200
 201   /* Decrement the number of entries in the hash table.  */
 202   --cache->used;
 203 }
 204
 205
 206 node_ptr
 207 objc_hash_next (cache_ptr cache, node_ptr node)
 208 {
 209   /* If the scan is being started then reset the last node
 210      visitied pointer and bucket index.  */
 211   if (! node)
 212     cache->last_bucket  = 0;
 213
 214   /* If there is a node visited last then check for another
 215      entry in the same bucket;  Otherwise step to the next bucket.  */
 216   if (node) {
 217     if (node->next)
 218       /* There is a node which follows the last node
 219          returned.  Step to that node and retun it.  */
 220       return node->next;
 221     else
 222       ++cache->last_bucket;
 223   }
 224
 225   /* If the list isn't exhausted then search the buckets for
 226      other nodes.  */
 227   if (cache->last_bucket < cache->size) {
 228     /*  Scan the remainder of the buckets looking for an entry
 229         at the head of the list.  Return the first item found.  */
 230     while (cache->last_bucket < cache->size)
 231       if (cache->node_table[cache->last_bucket])
 232         return cache->node_table[cache->last_bucket];
 233       else
 234         ++cache->last_bucket;
 235
 236     /* No further nodes were found in the hash table.  */
 237     return NULL;
 238   } else
 239     return NULL;
 240 }
 241
 242
 243 /* Given KEY, return corresponding value for it in CACHE.
 244    Return NULL if the KEY is not recorded.  */
 245
 246 void *
 247 objc_hash_value_for_key (cache_ptr cache, const void *key)
 248 {
 249   node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
 250   void *retval = NULL;
 251
 252   if (node)
 253     do {
 254       if ((*cache->compare_func)(node->key, key)) {
 255         retval = node->value;
 256               break;
 257       } else
 258         node = node->next;
 259     } while (! retval && node);
 260
 261   return retval;
 262 }
 263
 264 /* Given KEY, return YES if it exists in the CACHE.
 265    Return NO if it does not */
 266
 267 BOOL
 268 objc_hash_is_key_in_hash (cache_ptr cache, const void *key)
 269 {
 270   node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
 271
 272   if (node)
 273     do {
 274       if ((*cache->compare_func)(node->key, key))
 275           return YES;
 276       else
 277         node = node->next;
 278     } while (node);
 279
 280   return NO;
 281 }