/*#io
docCopyright("Steve Dekorte", 2002)
docCopyright("Marc Fauconneau", 2007)
docLicense("BSD revised")
docDescription("""
	PHash - Cuckoo Hash
	keys and values are references (they are not copied or freed)
	key pointers are assumed unique

""")
*/

#ifdef PHASH_C
#define IO_IN_C_FILE
#endif
#include "Common_inline.h"
#ifdef IO_DECLARE_INLINES

#include <stdio.h>

#define PHASH_RECORDS_AT_(self, tableIndex, index) (self->records + self->tableSize*tableIndex + index)
#define PHASH_RECORDS_AT_HASH_(self, tableIndex, hash) \
(self->records + self->tableSize*tableIndex + (hash & self->mask))

IOINLINE unsigned int PHash_count(PHash *self)
{
	return self->numKeys;
}

IOINLINE void PHashRecord_swap(PHashRecord* r1, PHashRecord* r2)
{
	PHashRecord t = *r1;
	*r1 = *r2;
	*r2 = t;
}

#define PHashKey_value(k) k

/*
IOINLINE void *PHashKey_value(void *key)
{
	return key;
}
*/

IOINLINE unsigned int PHashKey_isEqual_(void *key1, void *key2)
{
//	return key2 && (PHashKey_value(key1) == PHashKey_value(key2));
	return key1 == key2;
}

// simple hash functions, should be enough for pointers
IOINLINE unsigned int PHash_hash(PHash *self, void *key)
{
	intptr_t k = (intptr_t)PHashKey_value(key);
	return k^(k>>4);
}

IOINLINE unsigned int PHash_hash_more(PHash *self, unsigned int hash)
{
	return hash ^ (hash >> self->log2tableSize);
}

// -----------------------------------

IOINLINE void PHash_clean(PHash *self)
{
	memset(self->records, 0, sizeof(PHashRecord) * self->tableSize * 2);
	self->numKeys = 0;
}

IOINLINE PHashRecord *PHash_recordAt_(PHash *self, void *key)
{
	unsigned int hash;
	PHashRecord *record;

	hash = PHash_hash(self, key);
	record = PHASH_RECORDS_AT_HASH_(self, 0, hash);

	// we try the second location
	hash = PHash_hash_more(self, hash);
	record = (key == record->key) ? record : PHASH_RECORDS_AT_HASH_(self, 1, hash);

	return (key == record->key) ? record : &self->nullRecord;
}

IOINLINE void *PHash_at_(PHash *self, void *key)
{
	return PHash_recordAt_(self, key)->value;
}

IOINLINE unsigned char PHash_at_update_(PHash *self, void *key, void *value)
{
	PHashRecord *record = PHash_recordAt_(self, key);

	if (record->key)
	{
		// already a matching key, replace it
		if (PHashKey_isEqual_(key, record->key))
		{
			if (record->value == value)
			{
				return 0; // return 0 if no change
			}

			record->value = value;
			return 1;
		}
	}

	return 0;
}

IOINLINE void PHash_at_put_(PHash *self, void *key, void *value)
{
	PHashRecord thisRecord;
	PHashRecord *record;

	record = PHash_recordAt_(self, key);

	// already a matching key, replace it
	if (record != &self->nullRecord && PHashKey_isEqual_(key, record->key))
	{
		record->value = value;
		return;
	}

	thisRecord.key = key;
	thisRecord.value = value;

	record = PHash_cuckoo_(self, &thisRecord);

	if (!record) // collision
	{
		PHash_growWithRecord(self, &thisRecord);
	}
	else
	{
		*record = thisRecord;
		self->numKeys ++;
		if (self->numKeys > PHash_maxKeys(self))
			PHash_grow(self);
	}
}

IOINLINE void PHash_removeKey_(PHash *self, void *key)
{
	PHashRecord *record = PHash_recordAt_(self, key);
	void *rkey = record->key;

	if (rkey && PHashKey_value(rkey) == PHashKey_value(key))
	{
		self->numKeys --;
		memset(record, 0, sizeof(PHashRecord));
	}
}

// --- enumeration --------------------------------------------------

#define PHASH_FOREACH(self, pkey, pvalue, code) \
{\
	PHash *_self = (self);\
	unsigned int _i, _j, _size = _self->tableSize;\
	void * pkey;\
	void * pvalue;\
	\
	for (_j = 0; _j < 2; _j ++)\
	for (_i = 0; _i < _size; _i ++)\
	{\
		PHashRecord *_record = PHASH_RECORDS_AT_(_self, _j, _i);\
		if (_record->key)\
		{\
			pkey = _record->key;\
			pvalue = _record->value;\
			code;\
		}\
	}\
}

/*
typedef BASEKIT_API void (PHashDoCallback)(void *);

IOINLINE void PHash_do_(PHash *self, PHashDoCallback *callback)
{ PHASH_FOREACH(self, k, v, (*callback)(v)); }

IOINLINE void *PHash_detect_(PHash *self, PHashDetectCallback *callback)
{ PHASH_FOREACH(self, k, v, if ((*callback)(v)) return k; ); return NULL; }

IOINLINE void PHash_doOnKeys_(PHash *self, PHashDoCallback *callback)
{ PHASH_FOREACH(self, k, v, (*callback)(k)); }

IOINLINE void PHash_doOnKeyAndValue_(PHash *self, PHashDoCallback *callback)
{ PHASH_FOREACH(self, k, v, (*callback)(k); (*callback)(v);); }
*/

#undef IO_IN_C_FILE
#endif
