-/* -*-c-*-
- * This file contains the hashing implementation.
- *
- * Copyright (C) 1991 Threaded Technologies Inc.
- *
- * This program is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published
- * by the Free Software Foundation; either version 1, or any later version.
- *
- * This program is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should receive a copy of the GNU General Public License
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
- *
- $Header: /usr/user/dennis_glatting/ObjC/c-runtime/lib/RCS/hash.c,v 0.3 1991/11/07 23:23:40 dennisg Exp dennisg $
- $Author: dennisg $
- $Date: 1991/11/07 23:23:40 $
- $Log: hash.c,v $
- * Revision 0.3 1991/11/07 23:23:40 dennisg
- * implemented hash table expansion as suggested by rms.
- *
- * Revision 0.2 1991/11/07 22:30:54 dennisg
- * added copyleft
- *
- * Revision 0.1 1991/10/24 00:45:39 dennisg
- * Initial check in. Preliminary development stage.
- *
-*/
-
-
-#include <hash.h>
-#include <ObjC.h>
-#include <ObjC-private.h>
-
-#include <assert.h>
-#include <libc.h>
-#include <math.h>
-
- /* These two macros determine
- when a hash table is full and
- by how much it should be
- expanded respectively.
-
- These equations are
- percentages. */
-#define FULLNESS(cache) \
- ((((cache)->sizeOfHash * 75 ) / 100 ) <= (cache)->entriesInHash)
-#define EXPANSION(cache) \
- (((cache)->sizeOfHash * 175 ) / 100 )
-
- /* Local forward decl. */
- u_int hashValue( Cache_t, void* );
-
-
-Cache_t hash_new( u_int sizeOfHash ) {
-
- Cache_t retCache;
- int i;
-
-
- assert( sizeOfHash );
-
- /* Allocate the cache
- structure. calloc() insures
- its initialization for
- default values. */
- retCache = calloc( 1, sizeof( Cache ));
- assert( retCache );
-
- /* Allocate the array of
- buckets for the cache.
- calloc() initializes all of
- the pointers to NULL. */
- retCache->theNodeTable = calloc( sizeOfHash, sizeof( CacheNode_t ));
- assert( retCache->theNodeTable );
-
- retCache->sizeOfHash = sizeOfHash;
-
- /* Calculate the number of
- bits required to represent
- the hash mask. */
- retCache->numberOfMaskBits =
- ceil( log( retCache->sizeOfHash ) / log( 2 ));
-
- /* Form a bit mask for the
- hash. */
- for( i = 0; i < retCache->numberOfMaskBits; ++i )
- retCache->mask = ( retCache->mask << 1 ) | 0x01 ;
-
- assert( retCache->numberOfMaskBits );
- assert( retCache->mask );
-
- return retCache;
-}
+/* Hash tables for Objective C internal structures
+ Copyright (C) 1993, 1996, 1997 Free Software Foundation, Inc.
+
+This file is part of GNU CC.
+
+GNU CC is free software; you can redistribute it and/or modify
+it under the terms of the GNU General Public License as published by
+the Free Software Foundation; either version 2, or (at your option)
+any later version.
+
+GNU CC is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License
+along with GNU CC; see the file COPYING. If not, write to
+the Free Software Foundation, 59 Temple Place - Suite 330,
+Boston, MA 02111-1307, USA. */
+
+/* As a special exception, if you link this library with files
+ compiled with GCC to produce an executable, this does not cause
+ the resulting executable to be covered by the GNU General Public License.
+ This exception does not however invalidate any other reasons why
+ the executable file might be covered by the GNU General Public License. */
+
+#include "assert.h"
+
+#include "objc/hash.h"
+
+#include "runtime.h" /* for DEBUG_PRINTF */
+
+/* These two macros determine when a hash table is full and
+ by how much it should be expanded respectively.
+
+ These equations are percentages. */
+#define FULLNESS(cache) \
+ ((((cache)->size * 75) / 100) <= (cache)->used)
+#define EXPANSION(cache) \
+ ((cache)->size * 2)
+
+cache_ptr
+hash_new (unsigned int size, hash_func_type hash_func,
+ compare_func_type compare_func)
+{
+ cache_ptr cache;
+
+ /* Pass me a value greater than 0 and a power of 2. */
+ assert (size);
+ assert (!(size & (size - 1)));
+
+ /* Allocate the cache structure. calloc insures
+ its initialization for default values. */
+ cache = (cache_ptr) objc_calloc (1, sizeof (struct cache));
+ assert (cache);
+
+ /* Allocate the array of buckets for the cache.
+ calloc initializes all of the pointers to NULL. */
+ cache->node_table
+ = (node_ptr *) objc_calloc (size, sizeof (node_ptr));
+ assert (cache->node_table);
+ cache->size = size;
-void hash_delete( Cache_t theCache ) {
+ /* This should work for all processor architectures? */
+ cache->mask = (size - 1);
+
+ /* Store the hashing function so that codes can be computed. */
+ cache->hash_func = hash_func;
+
+ /* Store the function that compares hash keys to
+ determine if they are equal. */
+ cache->compare_func = compare_func;
+
+ return cache;
+}
- CacheNode_t aNode;
-
- /* Purge all key/value pairs
- from the table. */
- while( aNode = hash_next( theCache, NULL ))
- hash_remove( theCache, aNode->theKey );
+void
+hash_delete (cache_ptr cache)
+{
+ node_ptr node;
+ node_ptr next_node;
+ unsigned int i;
+
+ /* Purge all key/value pairs from the table. */
+ /* Step through the nodes one by one and remove every node WITHOUT
+ using hash_next. this makes hash_delete much more efficient. */
+ for (i = 0;i < cache->size;i++) {
+ if ((node = cache->node_table[i])) {
+ /* an entry in the hash table has been found, now step through the
+ nodes next in the list and free them. */
+ while ((next_node = node->next)) {
+ hash_remove (cache,node->key);
+ node = next_node;
+ }
+
+ hash_remove (cache,node->key);
+ }
+ }
- /* Release the array of nodes
- and the cache itself. */
- free( theCache->theNodeTable );
- free( theCache );
+ /* Release the array of nodes and the cache itself. */
+ objc_free(cache->node_table);
+ objc_free(cache);
}
-void hash_add( Cache_t* theCache, void* aKey, void* aValue ) {
+void
+hash_add (cache_ptr *cachep, const void *key, void *value)
+{
+ size_t indx = (*(*cachep)->hash_func)(*cachep, key);
+ node_ptr node = (node_ptr) objc_calloc (1, sizeof (struct cache_node));
- u_int indx = hashValue( *theCache, aKey );
- CacheNode_t aCacheNode = calloc( 1, sizeof( CacheNode ));
+ assert (node);
- assert( aCacheNode );
-
- /* Initialize the new node. */
- aCacheNode->theKey = aKey;
- aCacheNode->theValue = aValue;
- aCacheNode->nextNode = ( *( *theCache )->theNodeTable )[ indx ];
-
- /* Debugging.
-
- Check the list for another
- key. */
+ /* Initialize the new node. */
+ node->key = key;
+ node->value = value;
+ node->next = (*cachep)->node_table[indx];
+
+ /* Debugging.
+ Check the list for another key. */
#ifdef DEBUG
- { CacheNode_t checkHashNode = ( *( *theCache )->theNodeTable )[ indx ];
-
- while( checkHashNode ) {
-
- assert( checkHashNode->theKey != aKey );
- checkHashNode = checkHashNode->nextNode;
- }
+ { node_ptr node1 = (*cachep)->node_table[indx];
+
+ while (node1) {
+
+ assert (node1->key != key);
+ node1 = node1->next;
}
+ }
#endif
- /* Install the node as the
- first element on the list. */
- ( *( *theCache )->theNodeTable )[ indx ] = aCacheNode;
+ /* Install the node as the first element on the list. */
+ (*cachep)->node_table[indx] = node;
- /* Bump the number of entries
- in the cache. */
- ++( *theCache )->entriesInHash;
-
- /* Check the hash table's
- fullness. We're going
- to expand if it is above
- the fullness level. */
- if(FULLNESS( *theCache )) {
- /* The hash table has reached
- its fullness level. Time to
- expand it.
-
- I'm using a slow method
- here but is built on other
- primitive functions thereby
- increasing its
- correctness. */
- Cache_t newCache = hash_new(EXPANSION( *theCache ));
- CacheNode_t aNode = NULL;
-
- DEBUG_PRINTF (stderr, "Expanding cache %#x from %d to %d\n",
- *theCache, ( *theCache )->sizeOfHash, newCache->sizeOfHash);
-
- /* Copy the nodes from the
- first hash table to the
- new one. */
- while( aNode = hash_next( *theCache, aNode ))
- hash_add( &newCache, aNode->theKey, aNode->theValue );
-
- /* Trash the old cache. */
- hash_delete( *theCache );
-
- /* Return a pointer to the new
- hash table. */
- *theCache = newCache;
- }
-}
+ /* Bump the number of entries in the cache. */
+ ++(*cachep)->used;
+ /* Check the hash table's fullness. We're going
+ to expand if it is above the fullness level. */
+ if (FULLNESS (*cachep)) {
-void hash_remove( Cache_t theCache, void* aKey ) {
-
- u_int indx = hashValue( theCache, aKey );
- CacheNode_t aCacheNode = ( *theCache->theNodeTable )[ indx ];
-
-
- /* We assume there is an entry
- in the table. Error if it
- is not. */
- assert( aCacheNode );
-
- /* Special case. First element
- is the key/value pair to be
- removed. */
- if( aCacheNode->theKey == aKey ) {
- ( *theCache->theNodeTable )[ indx ] = aCacheNode->nextNode;
- free( aCacheNode );
- } else {
- /* Otherwise, find the hash
- entry. */
- CacheNode_t prevHashNode = aCacheNode;
- BOOL removed = NO;
-
- do {
-
- if( aCacheNode->theKey == aKey ) {
- prevHashNode->nextNode = aCacheNode->nextNode, removed = YES;
- free( aCacheNode );
- } else
- prevHashNode = aCacheNode, aCacheNode = aCacheNode->nextNode;
- } while( !removed && aCacheNode );
- assert( removed );
+ /* The hash table has reached its fullness level. Time to
+ expand it.
+
+ I'm using a slow method here but is built on other
+ primitive functions thereby increasing its
+ correctness. */
+ node_ptr node1 = NULL;
+ cache_ptr new = hash_new (EXPANSION (*cachep),
+ (*cachep)->hash_func,
+ (*cachep)->compare_func);
+
+ DEBUG_PRINTF ("Expanding cache %#x from %d to %d\n",
+ *cachep, (*cachep)->size, new->size);
+
+ /* Copy the nodes from the first hash table to the new one. */
+ while ((node1 = hash_next (*cachep, node1)))
+ hash_add (&new, node1->key, node1->value);
+
+ /* Trash the old cache. */
+ hash_delete (*cachep);
+
+ /* Return a pointer to the new hash table. */
+ *cachep = new;
}
-
- /* Decrement the number of
- entries in the hash table. */
- --theCache->entriesInHash;
}
-void* hash_value_for_key( Cache_t theCache, void* aKey ) {
+void
+hash_remove (cache_ptr cache, const void *key)
+{
+ size_t indx = (*cache->hash_func)(cache, key);
+ node_ptr node = cache->node_table[indx];
+
- u_int indx = hashValue( theCache, aKey );
- CacheNode_t aCacheNode = ( *theCache->theNodeTable )[ indx ];
- void* retVal = NULL;
-
+ /* We assume there is an entry in the table. Error if it is not. */
+ assert (node);
+
+ /* Special case. First element is the key/value pair to be removed. */
+ if ((*cache->compare_func)(node->key, key)) {
+ cache->node_table[indx] = node->next;
+ objc_free(node);
+ } else {
+
+ /* Otherwise, find the hash entry. */
+ node_ptr prev = node;
+ BOOL removed = NO;
- if( aCacheNode ) {
- BOOL found = NO;
-
do {
- if( aCacheNode->theKey == aKey )
- retVal = aCacheNode->theValue, found = YES;
- else
- aCacheNode = aCacheNode->nextNode;
- } while( !found && aCacheNode );
+
+ if ((*cache->compare_func)(node->key, key)) {
+ prev->next = node->next, removed = YES;
+ objc_free(node);
+ } else
+ prev = node, node = node->next;
+ } while (!removed && node);
+ assert (removed);
}
-
- return retVal;
+
+ /* Decrement the number of entries in the hash table. */
+ --cache->used;
}
-CacheNode_t hash_next( Cache_t theCache, CacheNode_t aCacheNode ) {
-
- CacheNode_t theCacheNode = aCacheNode;
-
-
- /* If the scan is being started
- then reset the last node
- visitied pointer and bucket
- index. */
- if( !theCacheNode )
- theCache->lastBucket = 0;
-
- /* If there is a node visited
- last then check for another
- entry in the same bucket;
- Otherwise step to the next
- bucket. */
- if( theCacheNode )
- if( theCacheNode->nextNode )
- /* There is a node which
- follows the last node
- returned. Step to that node
- and retun it. */
- return theCacheNode->nextNode;
+node_ptr
+hash_next (cache_ptr cache, node_ptr node)
+{
+ /* If the scan is being started then reset the last node
+ visitied pointer and bucket index. */
+ if (!node)
+ cache->last_bucket = 0;
+
+ /* If there is a node visited last then check for another
+ entry in the same bucket; Otherwise step to the next bucket. */
+ if (node) {
+ if (node->next)
+ /* There is a node which follows the last node
+ returned. Step to that node and retun it. */
+ return node->next;
else
- ++theCache->lastBucket;
-
- /* If the list isn't exhausted
- then search the buckets for
- other nodes. */
- if( theCache->lastBucket < theCache->sizeOfHash ) {
- /* Scan the remainder of the
- buckets looking for an entry
- at the head of the list.
- Return the first item
- found. */
- while( theCache->lastBucket < theCache->sizeOfHash )
- if(( *theCache->theNodeTable )[ theCache->lastBucket ])
- return ( *theCache->theNodeTable )[ theCache->lastBucket ];
+ ++cache->last_bucket;
+ }
+
+ /* If the list isn't exhausted then search the buckets for
+ other nodes. */
+ if (cache->last_bucket < cache->size) {
+ /* Scan the remainder of the buckets looking for an entry
+ at the head of the list. Return the first item found. */
+ while (cache->last_bucket < cache->size)
+ if (cache->node_table[cache->last_bucket])
+ return cache->node_table[cache->last_bucket];
else
- ++theCache->lastBucket;
-
- /* No further nodes were found
- in the hash table. */
+ ++cache->last_bucket;
+
+ /* No further nodes were found in the hash table. */
return NULL;
} else
return NULL;
}
-u_int hashValue( Cache_t theCache, void* aKey ) {
+/* Given KEY, return corresponding value for it in CACHE.
+ Return NULL if the KEY is not recorded. */
+
+void *
+hash_value_for_key (cache_ptr cache, const void *key)
+{
+ node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
+ void *retval = NULL;
- u_int hash = 0;
- int i;
-
-
- assert( theCache->numberOfMaskBits );
- for( i = 0; i < ( sizeof( aKey ) * 8 ); i += theCache->numberOfMaskBits )
- hash ^= (( u_int )aKey ) >> i ;
+ if (node)
+ do {
+ if ((*cache->compare_func)(node->key, key)) {
+ retval = node->value;
+ break;
+ } else
+ node = node->next;
+ } while (!retval && node);
- return ( hash & theCache->mask ) % theCache->sizeOfHash;
+ return retval;
}
+/* Given KEY, return YES if it exists in the CACHE.
+ Return NO if it does not */
+
+BOOL
+hash_is_key_in_hash (cache_ptr cache, const void *key)
+{
+ node_ptr node = cache->node_table[(*cache->hash_func)(cache, key)];
+
+ if (node)
+ do {
+ if ((*cache->compare_func)(node->key, key))
+ return YES;
+ else
+ node = node->next;
+ } while (node);
+
+ return NO;
+}
OSDN Git Service
