This is haptable.m in view mode; [Download] [Up]
/* haptable.m
Copyright 1990 NeXT, Inc.
Created by Bertrand Serlet, August 1990
*/
#ifdef SHLIB
#import "shlib.h"
#endif SHLIB
//#import "objc-private.h"
#import "haptable.h"
#import <string.h>
#import <stdlib.h>
#import <stdio.h>
#import <objc/Object.h>
#import <objc/hashtable.h>
/****** Macros and utilities ****************************/
#if DEBUG
#define INLINE
#else
#define INLINE inline
#endif
typedef struct _HapPair {
const void *key;
} HapPair;
static unsigned log2(unsigned x) { return (x<2) ? 0 : log2(x>>1)+1; };
static INLINE unsigned exp2m1(unsigned x) { return (1 << x) - 1; };
/* iff necessary this modulo can be optimized since the nbBuckets is of the form 2**n-1 */
static INLINE unsigned bucketOf(NXHapTable *table, const void *key) {
unsigned hash = (table->prototype->hash)(table, key);
unsigned xored = (hash & 0xffff) ^ (hash >> 16);
return ((xored * 65521) + hash) % table->nbBuckets;
}
static INLINE int isEqual(NXHapTable *table, const void *key1, const void *key2) {
return (key1 == key2) ? 1 : (table->prototype->isEqual)(table, key1, key2);
}
static INLINE unsigned nextIndex(NXHapTable *table, unsigned index) {
return (index+1 >= table->nbBuckets) ? 0 : index+1;
}
static INLINE void *allocBuckets(NXZone *zone, unsigned nb) {
HapPair *pairs = NXZoneMalloc(zone, (nb * sizeof(HapPair)));
HapPair *pair = pairs;
while (nb--) { pair->key = NX_HAPNOTAKEY; pair++; }
return pairs;
}
/***** Global data and bootstrap **********************/
static unsigned hashPrototype(const void *info, const void *data) {
NXHapTablePrototype *proto = (NXHapTablePrototype *) data;
return NXPtrHash(info, proto->hash) ^ NXPtrHash(info, proto->isEqual) ^ NXPtrHash(info, proto->free) ^ (unsigned) proto->style;
}
static int isEqualPrototype(const void *info, const void *data1, const void *data2) {
NXHapTablePrototype *proto1 = (NXHapTablePrototype *) data1;
NXHapTablePrototype *proto2 = (NXHapTablePrototype *) data2;
return (proto1->hash == proto2->hash) && (proto1->isEqual == proto2->isEqual) && (proto1->free == proto2->free) && (proto1->style == proto2->style);
}
static NXHashTablePrototype protoPrototype = {
hashPrototype, isEqualPrototype, NXNoEffectFree, 0
};
static NXHashTable *prototypes = NULL;
/* table of all prototypes */
/**** Fundamentals Operations **************/
NXHapTable *NXCreateHapTableFromZone(NXHapTablePrototype prototype, unsigned capacity, NXZone *zone) {
NXHapTable *table = NXZoneMalloc(zone, sizeof(NXHapTable));
NXHapTablePrototype *proto;
if (! prototypes) prototypes = NXCreateHashTable(protoPrototype, 0, NULL);
if (! prototype.hash || ! prototype.isEqual || ! prototype.free || prototype.style) {
printf("*** NXCreateHapTable: invalid creation parameters\n");
return NULL;
}
proto = NXHashGet(prototypes, &prototype);
if (! proto) {
proto = malloc(sizeof(NXHapTablePrototype));
*proto = prototype;
(void)NXHashInsert(prototypes, proto);
}
table->prototype = proto; table->count = 0;
table->nbBuckets = exp2m1(log2(capacity)+1);
table->buckets = allocBuckets(zone, table->nbBuckets);
return table;
}
NXHapTable *NXCreateHapTable(NXHapTablePrototype prototype, unsigned capacity) {
return NXCreateHapTableFromZone(prototype, capacity, NXDefaultMallocZone());
}
void NXFreeHapTable(NXHapTable *table) {
NXResetHapTable(table);
free(table->buckets);
free(table);
}
void NXResetHapTable(NXHapTable *table) {
HapPair *pairs = table->buckets;
void (*freeProc)(struct _NXHapTable *, void *) = table->prototype->free;
unsigned index = table->nbBuckets;
while (index--) {
if (pairs->key != NX_HAPNOTAKEY) {
freeProc(table, (void *)pairs->key);
pairs->key = NX_HAPNOTAKEY;
}
pairs++;
}
table->count = 0;
}
BOOL NXCompareHapTables(NXHapTable *table1, NXHapTable *table2) {
if (table1 == table2) return YES;
if (table1->count != table2->count) return NO;
else {
void *key;
NXHapState state = NXInitHapState(table1);
while (NXNextHapState(table1, &state, &key)) {
if (NXHapMember(table2, key) == NX_HAPNOTAKEY) return NO;
}
return YES;
}
}
unsigned NXCountHapTable(NXHapTable *table) { return table->count; }
static int hapSearch = 0;
static int hapSearchHit = 0;
static int hapSearchLoop = 0;
static INLINE void *_NXHapMember(NXHapTable *table, const void *key) {
HapPair *pairs = table->buckets;
unsigned index = bucketOf(table, key);
HapPair *pair = pairs + index;
if (pair->key == NX_HAPNOTAKEY) return NX_HAPNOTAKEY;
hapSearch ++;
if (isEqual(table, pair->key, key)) {
hapSearchHit ++;
return (void *)pair->key;
} else {
unsigned index2 = index;
while ((index2 = nextIndex(table, index2)) != index) {
hapSearchLoop ++;
pair = pairs + index2;
if (pair->key == NX_HAPNOTAKEY) return NX_HAPNOTAKEY;
if (isEqual(table, pair->key, key)) {
return (void *)pair->key;
}
}
return NX_HAPNOTAKEY;
}
}
void *NXHapMember(NXHapTable *table, const void *key) {
return _NXHapMember(table, key);
}
void *NXHapGet(NXHapTable *table, const void *key) {
void *oldKey = _NXHapMember(table, key);
return (oldKey != NX_HAPNOTAKEY) ? oldKey : NULL;
}
static int hapRehash = 0;
static int hapRehashSum = 0;
static void _NXHapRehash(NXHapTable *table) {
HapPair *pairs = table->buckets;
HapPair *pair = pairs;
unsigned index = table->nbBuckets;
unsigned oldCount = table->count;
table->nbBuckets += table->nbBuckets + 1; /* 2 times + 1 */
table->count = 0;
table->buckets = allocBuckets(NXZoneFromPtr(table), table->nbBuckets);
hapRehash ++;
hapRehashSum += table->count;
while (index--) {
if (pair->key != NX_HAPNOTAKEY) {
(void)NXHapInsert(table, pair->key);
}
pair++;
}
if (oldCount != table->count)
printf("*** haptable: count differs after rehashing; probably indicates a broken invariant: there are x and y such as isEqual(x, y) is TRUE but hash(x) != hash (y)\n");
free(pairs);
}
static int hapInsert = 0;
static int hapInsertHit = 0;
static int hapInsertLoop = 0;
void *NXHapInsert(NXHapTable *table, const void *key) {
HapPair *pairs = table->buckets;
unsigned index = bucketOf(table, key);
HapPair *pair = pairs + index;
if (key == NX_HAPNOTAKEY) {
printf("*** NXHapInsert: invalid key: -1\n");
return NULL;
}
hapInsert ++;
if (pair->key == NX_HAPNOTAKEY) {
hapInsertHit ++;
pair->key = key;
table->count++;
return NULL;
}
if (isEqual(table, pair->key, key)) {
hapInsertHit ++;
return (void *)pair->key;
} else if (table->count == table->nbBuckets) {
/* no room: rehash and retry */
_NXHapRehash(table);
return NXHapInsert(table, key);
} else {
unsigned index2 = index;
while ((index2 = nextIndex(table, index2)) != index) {
hapInsertLoop ++;
pair = pairs + index2;
if (pair->key == NX_HAPNOTAKEY) {
#if INSERT_TAIL
pair->key = key;
#else
HapPair current = {key};
index2 = index;
while (current.key != NX_HAPNOTAKEY) {
HapPair temp;
pair = pairs + index2;
temp = *pair;
*pair = current;
current = temp;
index2 = nextIndex(table, index2);
}
#endif
table->count++;
if (table->count * 4 > table->nbBuckets * 3) _NXHapRehash(table);
return NULL;
}
if (isEqual(table, pair->key, key)) {
return (void *)pair->key;
}
}
/* no room: can't happen! */
printf("**** NXHapInsert: bug\n");
return NULL;
}
}
static int hapRemove = 0;
void *NXHapRemove(NXHapTable *table, const void *key) {
HapPair *pairs = table->buckets;
unsigned index = bucketOf(table, key);
HapPair *pair = pairs + index;
unsigned chain = 1; /* number of non-nil pairs in a row */
int found = 0;
const void *old = NULL;
if (pair->key == NX_HAPNOTAKEY) return NULL;
hapRemove ++;
/* compute chain */
{
unsigned index2 = index;
if (isEqual(table, pair->key, key)) {found ++; old = pair->key;}
while ((index2 = nextIndex(table, index2)) != index) {
pair = pairs + index2;
if (pair->key == NX_HAPNOTAKEY) break;
if (isEqual(table, pair->key, key)) {found ++; old = pair->key; }
chain++;
}
}
if (! found) return NULL;
if (found != 1) printf("**** NXHapRemove: incorrect table\n");
/* remove then reinsert */
{
HapPair buffer[16];
HapPair *aux = (chain > 16) ? malloc(sizeof(HapPair)*(chain-1)) : buffer;
int auxnb = 0;
int nb = chain;
unsigned index2 = index;
while (nb--) {
pair = pairs + index2;
if (! isEqual(table, pair->key, key)) aux[auxnb++] = *pair;
pair->key = NX_HAPNOTAKEY;
index2 = nextIndex(table, index2);
}
table->count -= chain;
if (auxnb != chain-1) printf("**** NXHapRemove: bug\n");
while (auxnb--) NXHapInsert(table, aux[auxnb].key);
if (chain > 16) free(aux);
}
return (void *)old;
}
NXHapState NXInitHapState(NXHapTable *table) {
NXHapState state;
state.index = table->nbBuckets;
return state;
}
int NXNextHapState(NXHapTable *table, NXHapState *state, const void **key) {
HapPair *pairs = table->buckets;
while (state->index--) {
HapPair *pair = pairs + state->index;
if (pair->key != NX_HAPNOTAKEY) {
*key = pair->key;
return YES;
}
}
return NO;
}
/**** Conveniences *************************************/
unsigned _hapPtrHash(NXHapTable *table, const void *key) {
return (((unsigned) key) >> 16) ^ ((unsigned) key);
}
unsigned _hapStrHash(NXHapTable *table, const void *key) {
unsigned hash = 0;
unsigned char *s = (unsigned char *)key;
/* unsigned to avoid a sign-extend */
/* unroll the loop */
if (s) for (; ; ) {
if (*s == '\0') break;
hash ^= *s++;
if (*s == '\0') break;
hash ^= *s++ << 8;
if (*s == '\0') break;
hash ^= *s++ << 16;
if (*s == '\0') break;
hash ^= *s++ << 24;
}
return hash;
}
unsigned _hapObjectHash(NXHapTable *table, const void *key) {
return [(id)key hash];
}
int _hapPtrIsEqual(NXHapTable *table, const void *key1, const void *key2) {
return key1 == key2;
}
int _hapStrIsEqual(NXHapTable *table, const void *key1, const void *key2) {
if (key1 == key2) return YES;
if (! key1) return ! strlen ((char *) key2);
if (! key2) return ! strlen ((char *) key1);
if (((char *) key1)[0] != ((char *) key2)[0]) return NO;
return (strcmp((char *) key1, (char *) key2)) ? NO : YES;
}
int _hapObjectIsEqual(NXHapTable *table, const void *key1, const void *key2) {
return [(id)key1 isEqual:(id)key2];
}
void _hapNoFree(NXHapTable *table, void *key) {}
void _hapObjectFree(NXHapTable *table, void *key) {
[(id)key free];
}
const NXHapTablePrototype NXPtrValueHapPrototype = {
_hapPtrHash, _hapPtrIsEqual, _hapNoFree, 0
};
const NXHapTablePrototype NXStrValueHapPrototype = {
_hapStrHash, _hapStrIsEqual, _hapNoFree, 0
};
const NXHapTablePrototype NXObjectHapPrototype = {
_hapObjectHash, _hapObjectIsEqual, _hapObjectFree, 0
};
These are the contents of the former NiCE NeXT User Group NeXTSTEP/OpenStep software archive, currently hosted by Netfuture.ch.