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