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

    This is a perfect hash. When a new key collides with an
    existing one, it is rehashed until no collisions are found. 
    This means lookups are fast but the number of keys must remain 
    small(<100) - otherwise the storage size will get too big.
""")
*/

#ifndef PHASH_DEFINED
#define PHASH_DEFINED 1

#include "Common.h"
#include <stdlib.h>
#include <string.h>
#include <stddef.h>

#ifdef __cplusplus
extern "C" {
#endif

//#define PHASH_USE_CACHE 1
	
typedef struct 
{
    void *key;
    void *value;
} PHashRecord;

typedef struct 
{
    PHashRecord *records;
    unsigned int tableSize; // total number of records (power of 2)
    unsigned int numKeys;   // number of used records 
    unsigned int index;     // enumeration index 

    unsigned int a;         // hash mix parameter 1
    unsigned int b;         // hash mix parameter 2
    unsigned int mask;      // hash bit mask
#ifdef PHASH_USE_CACHE
    unsigned int cachedLookup;
#endif
} PHash;

PHash *PHash_new(void);
void PHash_free(PHash *self);
PHash *PHash_clone(PHash *self);
void PHash_copy_(PHash *self, PHash *other);

unsigned int PHash_size(PHash *self);
size_t PHash_memorySize(PHash *self);
void PHash_compact(PHash *self);
void PHash_collapseRecordsAndAddKey_value_(PHash *self, void *key, void *value);
void PHash_rehashWithCollapsedRecords(PHash *self);

void *PHash_firstValue(PHash *self);
void *PHash_nextValue(PHash *self);

void *PHash_firstKey(PHash *self);
void *PHash_nextKey(PHash *self);

unsigned int PHash_count(PHash *self);
unsigned int PHash_doCount(PHash *self);
/*
unsigned int PHash_countRecords_size_(unsigned char *records, unsigned int size);
*/

PHashRecord *PHash_recordAtIndex_(PHash *self, unsigned int index);
void *PHash_keyAt_(PHash *self, unsigned int index);
void *PHash_valueAt_(PHash *self, unsigned int index);
int PHash_indexForValue_(PHash *self, void *v);
void *PHash_firstKeyForValue_(PHash *self, void *v);

// --- perform -------------------------------------------------- 

typedef void (PHashDoCallback)(void *);
void PHash_do_(PHash *self, PHashDoCallback *callback);

typedef int (PHashDetectCallback)(void *);
void *PHash_detect_(PHash *self, PHashDetectCallback *callback); // returns matching key
void PHash_doOnKeys_(PHash *self, PHashDoCallback *callback);
void PHash_removeValue_(PHash *self, void *value);

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

/* #define PHASHFUNCTION(v, size) (int)((ptrdiff_t)v)%(size - 1) */

/* a bit of a hack for transparent futures - this only works for Objects with
   unique data pointers (this won't work with Number objects, for example). 
   v is always a String except for the PHash used for protos. 
   Need to move that off of PHash...
*/

/*
#ifndef OBJECT_STRUCT_DEFINED
#include "../IoMessage.h"
#include "../IoObject_struct.h"
#endif
*/

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

#include "PHash_inline.h"

#ifdef __cplusplus
}
#endif
#endif

