Return to hash.c CVS log

Up to [Apple XNU] / GNUtools / cc / objc

Annotation of GNUtools/cc/objc/hash.c, revision 1.1

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

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