From 2db2bea5cbb72b8a69759af8302bbe0876b0a56d Mon Sep 17 00:00:00 2001 From: Dennis Glatting Date: Mon, 13 Apr 1992 11:43:08 +0000 Subject: [PATCH] Check in after array version of run-time works. Expect more changes as hash version and other changes are made. From-SVN: r734 --- gcc/objc/hash.c | 97 ++++++++++++++++++++++++++++++------------- gcc/objc/hash.h | 126 +++++++++++++++++++++++++++++++++++++++++++++++++++----- gcc/objc/objc.h | 28 ++++++------- 3 files changed, 197 insertions(+), 54 deletions(-) diff --git a/gcc/objc/hash.c b/gcc/objc/hash.c index 6cc7b9a..4c095cd 100644 --- a/gcc/objc/hash.c +++ b/gcc/objc/hash.c @@ -16,10 +16,14 @@ * 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.10 1991/12/10 12:05:28 dennisg Exp dennisg $ + $Header: /usr/user/dennis_glatting/ObjC/c-runtime/hash/RCS/hash.c,v 0.11 1992/01/03 02:55:03 dennisg Exp dennisg $ $Author: dennisg $ - $Date: 1991/12/10 12:05:28 $ + $Date: 1992/01/03 02:55:03 $ $Log: hash.c,v $ + * Revision 0.11 1992/01/03 02:55:03 dennisg + * modified to handle new initialization scheme. + * fixed code structure. + * * Revision 0.10 1991/12/10 12:05:28 dennisg * Cleaned up file format for a distribution. * @@ -65,9 +69,9 @@ #include -#include -#include -#include +#include +#include +#include #include #include @@ -85,24 +89,19 @@ #define FULLNESS(cache) \ ((((cache)->sizeOfHash * 75 ) / 100) <= (cache)->entriesInHash) #define EXPANSION(cache) \ - (((cache)->sizeOfHash * 175 ) / 100 ) - -#define MEMORY_ALLOCATION_ADJUST(i) \ - ((i&0x01)?i:(i-1)) + ((cache)->sizeOfHash * 2 ) -Cache_t hash_new (u_int sizeOfHash) { +Cache_t +hash_new (u_int sizeOfHash, HashFunc aHashFunc, CompareFunc aCompareFunc) { Cache_t retCache; + /* Pass me a value greater + than 0 and a power of 2. */ assert(sizeOfHash); + assert( !(sizeOfHash & (sizeOfHash - 1))); - /* Memory is allocated on this - machine in even address - chunks. Therefore the - modulus must be odd. */ - sizeOfHash = MEMORY_ALLOCATION_ADJUST(sizeOfHash); - /* Allocate the cache structure. calloc () insures its initialization for @@ -112,23 +111,39 @@ Cache_t hash_new (u_int sizeOfHash) { /* Allocate the array of buckets for the cache. - calloc () initializes all of + calloc() initializes all of the pointers to NULL. */ retCache->theNodeTable = calloc (sizeOfHash, sizeof (CacheNode_t)); assert(retCache->theNodeTable); retCache->sizeOfHash = sizeOfHash; + /* This should work for all + processor architectures? */ + retCache->mask = ( sizeOfHash - 1 ); + + /* Store the hashing function + so that codes can be + computed. */ + retCache->hashFunc = aHashFunc; + + /* Store the function that + compares hash keys to + determine if they are + equal. */ + retCache->compareFunc = aCompareFunc; + return retCache; } -void hash_delete (Cache_t theCache) { +void +hash_delete (Cache_t theCache) { CacheNode_t aNode; - /* Purge all key/value pairs + /* Purge all key/value pairs from the table. */ while (aNode = hash_next (theCache, NULL)) hash_remove (theCache, aNode->theKey); @@ -140,9 +155,10 @@ void hash_delete (Cache_t theCache) { } -void hash_add (Cache_t* theCache, void* aKey, void* aValue) { +void +hash_add (Cache_t* theCache, void* aKey, void* aValue) { - u_int indx = hashIndex(*theCache, aKey); + u_int indx = (* (*theCache)->hashFunc)(*theCache, aKey); CacheNode_t aCacheNode = calloc (1, sizeof (CacheNode)); @@ -191,8 +207,9 @@ void hash_add (Cache_t* theCache, void* aKey, void* aValue) { increasing its correctness. */ CacheNode_t aNode = NULL; - Cache_t newCache = - hash_new (MEMORY_ALLOCATION_ADJUST( EXPANSION (*theCache))); + Cache_t newCache = hash_new (EXPANSION (*theCache), + (*theCache)->hashFunc, + (*theCache)->compareFunc); DEBUG_PRINTF (stderr, "Expanding cache %#x from %d to %d\n", *theCache, (*theCache)->sizeOfHash, newCache->sizeOfHash); @@ -213,9 +230,10 @@ void hash_add (Cache_t* theCache, void* aKey, void* aValue) { } -void hash_remove (Cache_t theCache, void* aKey) { +void +hash_remove (Cache_t theCache, void* aKey) { - u_int indx = hashIndex(theCache, aKey); + u_int indx = (*theCache->hashFunc)(theCache, aKey); CacheNode_t aCacheNode = (*theCache->theNodeTable)[ indx ]; @@ -227,7 +245,7 @@ void hash_remove (Cache_t theCache, void* aKey) { /* Special case. First element is the key/value pair to be removed. */ - if (aCacheNode->theKey == aKey) { + if ((*theCache->compareFunc)(aCacheNode->theKey, aKey)) { (*theCache->theNodeTable)[ indx ] = aCacheNode->nextNode; free (aCacheNode); } else { @@ -238,7 +256,7 @@ void hash_remove (Cache_t theCache, void* aKey) { do { - if (aCacheNode->theKey == aKey) { + if ((*theCache->compareFunc)(aCacheNode->theKey, aKey)) { prevHashNode->nextNode = aCacheNode->nextNode, removed = YES; free (aCacheNode); } else @@ -253,7 +271,8 @@ void hash_remove (Cache_t theCache, void* aKey) { } -CacheNode_t hash_next (Cache_t theCache, CacheNode_t aCacheNode) { +CacheNode_t +hash_next (Cache_t theCache, CacheNode_t aCacheNode) { CacheNode_t theCacheNode = aCacheNode; @@ -303,3 +322,25 @@ CacheNode_t hash_next (Cache_t theCache, CacheNode_t aCacheNode) { } + /* Given key, return its + value. Return NULL if the + key/value pair isn't in + the hash. */ +void* +hash_value_for_key (Cache_t theCache, void* aKey) { + + CacheNode_t aCacheNode = + (*theCache->theNodeTable)[(*theCache->hashFunc)(theCache, aKey)]; + void* retVal = NULL; + + + if (aCacheNode) + do { + if ((*theCache->compareFunc)(aCacheNode->theKey, aKey)) + retVal = aCacheNode->theValue; + else + aCacheNode = aCacheNode->nextNode; + } while (!retVal && aCacheNode); + + return retVal; +} diff --git a/gcc/objc/hash.h b/gcc/objc/hash.h index 62b48f8..e2fc776 100644 --- a/gcc/objc/hash.h +++ b/gcc/objc/hash.h @@ -21,10 +21,13 @@ * 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.h,v 0.7 1991/12/03 02:01:23 dennisg Exp dennisg $ + $Header: /usr/user/dennis_glatting/ObjC/c-runtime/hash/RCS/hash.h,v 0.8 1991/12/10 12:05:28 dennisg Exp dennisg $ $Author: dennisg $ - $Date: 1991/12/03 02:01:23 $ + $Date: 1991/12/10 12:05:28 $ $Log: hash.h,v $ + * Revision 0.8 1991/12/10 12:05:28 dennisg + * Cleaned up file format for a distribution. + * * Revision 0.7 1991/12/03 02:01:23 dennisg * fixed assert macro. * added memory allocation adjustment macro for hash size allocation. @@ -65,8 +68,10 @@ extern "C" { #endif +#include #include +#include /* * This data structure is used to hold items @@ -90,6 +95,27 @@ typedef struct cache_node { /* + * This data type is the function that computes a hash code given a key. + * Therefore, the key can be a pointer to anything and the function specific + * to the key type. + * + * Unfortunately there is a mutual data structure reference problem with this + * typedef. Therefore, to remove compiler warnings the functions passed to + * hash_new() will have to be casted to this type. + */ +typedef u_int (*HashFunc)(void*, void*); + +/* + * This data type is the function that compares two hash keys and returns an + * integer greater than, equal to, or less than 0, according as the first + * parameter is lexico-graphically greater than, equal to, or less than the + * second. + */ + +typedef int (*CompareFunc)(void*, void*); + + +/* * This data structure is the cache. * * It must be passed to all of the hashing routines @@ -112,8 +138,9 @@ typedef struct cache { entries allocated for "theNodeTable"). Must be a power of two. */ - entriesInHash; /* Current number of entries - in ther hash table. */ + entriesInHash, /* Current number of entries + in the hash table. */ + mask; /* Precomputed mask. */ /* * Variables used to implement indexing * through the hash table. @@ -121,19 +148,30 @@ typedef struct cache { u_int lastBucket; /* Tracks which entry in the array where the last value was returned. */ + /* Function used to compute + a hash code given a key. + This function is specified + when the hash table is + created. */ + HashFunc hashFunc; + /* Function used to compare + two hash keys to determine + if they are equal. */ + CompareFunc compareFunc; } Cache, *Cache_t; /* Prototypes for hash functions. */ /* Allocate and initialize - a hash table. Hash table - size taken as a parameter. */ -Cache_t hash_new (u_int sizeOfHash); + a hash table. */ +Cache_t +hash_new (u_int sizeOfHash, HashFunc aHashFunc, CompareFunc aCompareFunc); /* Deallocate all of the hash nodes and the cache itself. */ -void hash_delete (Cache_t theCache); +void +hash_delete (Cache_t theCache); /* Add the key/value pair to the hash table. If the hash table reaches a @@ -142,12 +180,14 @@ void hash_delete (Cache_t theCache); assert() if the key is already in the hash. */ -void hash_add (Cache_t* theCache, void* aKey, void* aValue); +void +hash_add (Cache_t* theCache, void* aKey, void* aValue); /* Remove the key/value pair from the hash table. assert() if the key isn't in the table. */ -void hash_remove (Cache_t theCache, void* aKey); +void +hash_remove (Cache_t theCache, void* aKey); /* Used to index through the hash table. Start with NULL to get the first entry. @@ -160,7 +200,71 @@ void hash_remove (Cache_t theCache, void* aKey); Cache nodes are returned such that key or value can ber extracted. */ -CacheNode_t hash_next (Cache_t theCache, CacheNode_t aCacheNode); +CacheNode_t +hash_next (Cache_t theCache, CacheNode_t aCacheNode); + + /* Used to return a value from + a hash table using a given + key. */ +void* +hash_value_for_key (Cache_t theCache, void* aKey); + + +/************************************************ + + Useful hashing functions. + + Declared inline for your pleaseure. + +************************************************/ + + /* Calculate a hash code by + performing some manipulation + of the key pointer. */ +static inline u_int +intHash(Cache_t theCache, void* aKey) { + + + assert(sizeof (u_int) == sizeof (aKey)); + + return ((u_int)aKey >> (sizeof(void*) - 1)) & theCache->mask ; +} + + /* Calculate a hash code by + iterating over a NULL + terminate string. */ +static inline u_int +strHash(Cache_t theCache, void* aKey) { + + u_int ret = 0; + u_int ctr = 0; + + + while(*(char*)aKey) { + ret ^= *(char*)aKey++ << ctr; + ctr = (ctr + 1) % sizeof(void*); + } + + return ret & theCache->mask ; +} + + + /* Compare two integers. */ +static inline int +intCmp(void* k1, void* k2) { + + + return !((int)k1 - (int)k2); +} + + + /* Compare two strings. */ +static inline int +strCmp(void* k1, void* k2) { + + + return !strcmp( k1, k2 ); +} #ifdef __cplusplus diff --git a/gcc/objc/objc.h b/gcc/objc/objc.h index 7628679..0ba6716 100644 --- a/gcc/objc/objc.h +++ b/gcc/objc/objc.h @@ -19,10 +19,14 @@ * 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/include/RCS/ObjC.h,v 0.9 1991/12/10 12:04:22 dennisg Exp dennisg $ + $Header: /usr/user/dennis_glatting/ObjC/c-runtime/include/RCS/ObjC.h,v 0.10 1991/12/31 20:16:08 dennisg Exp dennisg $ $Author: dennisg $ - $Date: 1991/12/10 12:04:22 $ + $Date: 1991/12/31 20:16:08 $ $Log: ObjC.h,v $ + * Revision 0.10 1991/12/31 20:16:08 dennisg + * Deleted index variable stuff. Index variables are a hack to the language. + * Cleaned up some documentation. + * * Revision 0.9 1991/12/10 12:04:22 dennisg * Cleaned up file format for a distribution. * @@ -69,12 +73,12 @@ extern "C" { #endif #include -#include +#include #include -#define nil ( id )0 /* id of Nil instance */ -#define Nil ( Class_t )0 /* id of Nil class */ +#define nil (id)0 /* id of Nil instance */ +#define Nil (Class_t)0 /* id of Nil class */ typedef char* STR; /* String alias */ /* Boolean typedefs */ @@ -292,11 +296,8 @@ typedef struct objc_metaClass { Object. Should be ignored. */ MethodList_t methods; /* Linked List of factory methods for the class. */ - Cache_t cache; /* Used to cache factory methods - defined for the class and its - super classes. Entries are - made to the cache as the - messager receives them. */ + Record_t* cache; /* Pointer to factory method + dispatch table. */ } MetaClass, *MetaClass_t; @@ -334,11 +335,8 @@ typedef struct objc_class { MethodList_t methods; /* Linked list of instance methods defined for the class. */ - Cache_t cache; /* Used to cache instance methods - defined for the class and its - super classes. Entries are - made to the cache as the - messager receives them. */ + Record_t* cache; /* Pointer to instance method + dispatch table. */ } Class, *Class_t; -- 2.7.4