/*	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
};

