Return to hash.c CVS log

Up to [GCC 2.x] / gcc / objc

Annotation of gcc/objc/hash.c, revision 1.1.1.2

1.1.1.2 ! root        1: /* Hash tables for Objective C internal structures
        !             2:    Copyright (C) 1993 Free Software Foundation, Inc.
1.1       root        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, 675 Mass Ave, Cambridge, MA 02139, USA.  */
                     19: 
                     20: /* As a special exception, if you link this library with files
                     21:    compiled with GCC to produce an executable, this does not cause
                     22:    the resulting executable to be covered by the GNU General Public License.
                     23:    This exception does not however invalidate any other reasons why
                     24:    the executable file might be covered by the GNU General Public License.  */
                     25: 
                     26: #include "assert.h"
                     27: 
1.1.1.2 ! root       28: #include "objc/hash.h"
        !            29: #include "objc/objc.h"
1.1       root       30: 
1.1.1.2 ! root       31: #include "runtime.h"           /* for DEBUG_PRINTF */
1.1       root       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: 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
                     53:      its initialization for default values.  */
1.1.1.2 ! root       54:   cache = (cache_ptr) __objc_xcalloc (1, sizeof (struct cache));
1.1       root       55:   assert (cache);
                     56: 
                     57:   /* Allocate the array of buckets for the cache.
                     58:      calloc initializes all of the pointers to NULL.  */
                     59:   cache->node_table
1.1.1.2 ! root       60:     = (node_ptr *) __objc_xcalloc (size, sizeof (node_ptr));
1.1       root       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
                     72:      determine if they are equal.  */
                     73:   cache->compare_func = compare_func;
                     74: 
                     75:   return cache;
                     76: }
                     77: 
                     78: 
                     79: void
                     80: hash_delete (cache_ptr cache)
                     81: {
                     82:   node_ptr node;
                     83: 
                     84: 
                     85:   /* Purge all key/value pairs from the table.  */
1.1.1.2 ! root       86:   while ((node = hash_next (cache, NULL)))
1.1       root       87:     hash_remove (cache, node->key);
                     88: 
                     89:   /* Release the array of nodes and the cache itself.  */
                     90:   free (cache->node_table);
                     91:   free (cache);
                     92: }
                     93: 
                     94: 
                     95: void
                     96: hash_add (cache_ptr *cachep, const void *key, void *value)
                     97: {
                     98:   size_t indx = (*(*cachep)->hash_func)(*cachep, key);
1.1.1.2 ! root       99:   node_ptr node = (node_ptr) __objc_xcalloc (1, sizeof (struct cache_node));
1.1       root      100: 
                    101: 
                    102:   assert (node);
                    103: 
                    104:   /* Initialize the new node.  */
                    105:   node->key    = key;
                    106:   node->value  = value;
                    107:   node->next  = (*cachep)->node_table[indx];
                    108: 
                    109:   /* Debugging.
                    110:      Check the list for another key.  */
                    111: #ifdef DEBUG
                    112:   { node_ptr node1 = (*cachep)->node_table[indx];
                    113: 
                    114:     while (node1) {
                    115: 
                    116:       assert (node1->key != key);
                    117:       node1 = node1->next;
                    118:     }
                    119:   }
                    120: #endif
                    121: 
                    122:   /* Install the node as the first element on the list.  */
                    123:   (*cachep)->node_table[indx] = node;
                    124: 
                    125:   /* Bump the number of entries in the cache.  */
                    126:   ++(*cachep)->used;
                    127: 
                    128:   /* Check the hash table's fullness.   We're going
                    129:      to expand if it is above the fullness level.  */
                    130:   if (FULLNESS (*cachep)) {
                    131: 
                    132:     /* The hash table has reached its fullness level.  Time to
                    133:        expand it.
                    134: 
                    135:        I'm using a slow method here but is built on other
                    136:        primitive functions thereby increasing its
                    137:        correctness.  */
                    138:     node_ptr node1 = NULL;
                    139:     cache_ptr new = hash_new (EXPANSION (*cachep),
                    140:                              (*cachep)->hash_func,
                    141:                              (*cachep)->compare_func);
                    142: 
                    143:     DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
                    144:                  *cachep, (*cachep)->size, new->size);
                    145: 
                    146:     /* Copy the nodes from the first hash table to the new one.  */
1.1.1.2 ! root      147:     while ((node1 = hash_next (*cachep, node1)))
1.1       root      148:       hash_add (&new, node1->key, node1->value);
                    149: 
                    150:     /* Trash the old cache.  */
                    151:     hash_delete (*cachep);
                    152: 
                    153:     /* Return a pointer to the new hash table.  */
                    154:     *cachep = new;
                    155:   }
                    156: }
                    157: 
                    158: 
                    159: void
                    160: hash_remove (cache_ptr cache, const void *key)
                    161: {
                    162:   size_t indx = (*cache->hash_func)(cache, key);
                    163:   node_ptr node = cache->node_table[indx];
                    164: 
                    165: 
                    166:   /* We assume there is an entry in the table.  Error if it is not.  */
                    167:   assert (node);
                    168: 
                    169:   /* Special case.  First element is the key/value pair to be removed.  */
                    170:   if ((*cache->compare_func)(node->key, key)) {
                    171:     cache->node_table[indx] = node->next;
                    172:     free (node);
                    173:   } else {
                    174: 
                    175:     /* Otherwise, find the hash entry.  */
                    176:     node_ptr prev = node;
                    177:     BOOL removed = NO;
                    178: 
                    179:     do {
                    180: 
                    181:       if ((*cache->compare_func)(node->key, key)) {
                    182:         prev->next = node->next, removed = YES;
                    183:         free (node);
                    184:       } else
                    185:         prev = node, node = node->next;
                    186:     } while (!removed && node);
                    187:     assert (removed);
                    188:   }
                    189: 
                    190:   /* Decrement the number of entries in the hash table.  */
                    191:   --cache->used;
                    192: }
                    193: 
                    194: 
                    195: node_ptr
                    196: hash_next (cache_ptr cache, node_ptr node)
                    197: {
                    198:   /* If the scan is being started then reset the last node
                    199:      visitied pointer and bucket index.  */
                    200:   if (!node)
                    201:     cache->last_bucket  = 0;
                    202: 
                    203:   /* If there is a node visited last then check for another
                    204:      entry in the same bucket;  Otherwise step to the next bucket.  */
                    205:   if (node) {
                    206:     if (node->next)
                    207:       /* There is a node which follows the last node
                    208:         returned.  Step to that node and retun it.  */
                    209:       return node->next;
                    210:     else
                    211:       ++cache->last_bucket;
                    212:   }
                    213: 
                    214:   /* If the list isn't exhausted then search the buckets for
                    215:      other nodes.  */
                    216:   if (cache->last_bucket < cache->size) {
                    217:     /*  Scan the remainder of the buckets looking for an entry
                    218:        at the head of the list.  Return the first item found.  */
                    219:     while (cache->last_bucket < cache->size)
                    220:       if (cache->node_table[cache->last_bucket])
                    221:         return cache->node_table[cache->last_bucket];
                    222:       else
                    223:         ++cache->last_bucket;
                    224: 
                    225:     /* No further nodes were found in the hash table.  */
                    226:     return NULL;
                    227:   } else
                    228:     return NULL;
                    229: }
                    230: 
                    231: 
                    232: /* Given KEY, return corresponding value for it in CACHE.
                    233:    Return NULL if the KEY is not recorded.  */
                    234: 
                    235: void *
                    236: hash_value_for_key (cache_ptr cache, const void *key)
                    237: {
                    238:   node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
                    239:   void *retval = NULL;
                    240: 
                    241:   if (node)
                    242:     do {
                    243:       if ((*cache->compare_func)(node->key, key))
                    244:         retval = node->value;
                    245:       else
                    246:         node = node->next;
                    247:     } while (!retval && node);
                    248: 
                    249:   return retval;
                    250: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.