// written in the D programming language

module chipmunkd.cpHashSet;

import chipmunkd.chipmunk;
import chipmunkd.chipmunk_types_h;
import chipmunkd.cpArray;
import chipmunkd.prime;

// cpHashSet uses a chained hashtable implementation.
// Other than the transformation functions, there is nothing fancy going on.

// cpHashSetBin's form the linked lists in the chained hash table.
struct cpHashSetBin {
	// Pointer to the element.
	void *elt;
	// Hash value of the element.
	cpHashValue hash;
	// Next element in the chain.
	cpHashSetBin *next;
}

// Equality function. Returns true if ptr is equal to elt.
alias cpBool function(void *ptr, void *elt) cpHashSetEqlFunc;
// Used by cpHashSetInsert(). Called to transform the ptr into an element.
alias void* function(void *ptr, void *data) cpHashSetTransFunc;

struct cpHashSet {
	// Number of elements stored in the table.
	int entries;
	// Number of cells in the table.
	int size;
	
	cpHashSetEqlFunc eql;
	cpHashSetTransFunc trans;
	
	// Default value returned by cpHashSetFind() when no element is found.
	// Defaults to null.
	void *default_value;
	
	// The table and recycled bins
	cpHashSetBin **table;
	cpHashSetBin *pooledBins;
	
	cpArray *allocatedBuffers;
}

alias void function(void *elt, void *data) cpHashSetIterFunc;
alias cpBool function(void *elt, void *data) cpHashSetFilterFunc;

static void freeWrap(void *ptr, void *unused){cpfree(ptr);}

void
cpHashSetDestroy(cpHashSet *set)
{
	// Free the table.
	cpfree(set.table);
	
	cpArrayEach(set.allocatedBuffers, &freeWrap, null);
	cpArrayFree(set.allocatedBuffers);
}

void
cpHashSetFree(cpHashSet *set)
{
	if(set){
		cpHashSetDestroy(set);
		cpfree(set);
	}
}

cpHashSet *
cpHashSetAlloc()
{
	return cast(cpHashSet *)cpcalloc(1, cpHashSet.sizeof);
}

cpHashSet *
cpHashSetInit(cpHashSet *set, int size, cpHashSetEqlFunc eqlFunc, cpHashSetTransFunc trans)
{
	set.size = next_prime(size);
	set.entries = 0;
	
	set.eql = eqlFunc;
	set.trans = trans;
	
	set.default_value = null;
	
	set.table = cast(cpHashSetBin **)cpcalloc(set.size, (cpHashSetBin *).sizeof);
	set.pooledBins = null;
	
	set.allocatedBuffers = cpArrayNew(0);
	
	return set;
}

cpHashSet *
cpHashSetNew(int size, cpHashSetEqlFunc eqlFunc, cpHashSetTransFunc trans)
{
	return cpHashSetInit(cpHashSetAlloc(), size, eqlFunc, trans);
}

static int
setIsFull(cpHashSet *set)
{
	return (set.entries >= set.size);
}

static void
cpHashSetResize(cpHashSet *set)
{
	// Get the next approximate doubled prime.
	int newSize = next_prime(set.size + 1);
	// Allocate a new table.
	cpHashSetBin **newTable = cast(cpHashSetBin **)cpcalloc(newSize, (cpHashSetBin *).sizeof);
	
	// Iterate over the chains.
	for(int i=0; i<set.size; i++){
		// Rehash the bins into the new table.
		cpHashSetBin *bin = set.table[i];
		while(bin){
			cpHashSetBin *next = bin.next;
			
			int idx = bin.hash%newSize;
			bin.next = newTable[idx];
			newTable[idx] = bin;
			
			bin = next;
		}
	}
	
	cpfree(set.table);
	
	set.table = newTable;
	set.size = newSize;
}

static void
recycleBin(cpHashSet *set, cpHashSetBin *bin)
{
	bin.next = set.pooledBins;
	set.pooledBins = bin;
	bin.elt = null;
}

static cpHashSetBin *
getUnusedBin(cpHashSet *set)
{
	cpHashSetBin *bin = set.pooledBins;
	
	if(bin){
		set.pooledBins = bin.next;
		return bin;
	} else {
		// Pool is exhausted, make more
		int count = CP_BUFFER_BYTES/cpHashSetBin.sizeof;
		assert(count!=0, "Buffer size is too small.");
		
		cpHashSetBin *buffer = cast(cpHashSetBin *)cpmalloc(CP_BUFFER_BYTES);
		cpArrayPush(set.allocatedBuffers, buffer);
		
		// push all but the first one, return the first instead
		for(int i=1; i<count; i++) recycleBin(set, buffer + i);
		return buffer;
	}
}

void *
cpHashSetInsert(cpHashSet *set, cpHashValue hash, void *ptr, void *data)
{
	int idx = hash%set.size;
	
	// Find the bin with the matching element.
	cpHashSetBin *bin = set.table[idx];
	while(bin && !set.eql(ptr, bin.elt))
		bin = bin.next;
	
	// Create it necessary.
	if(!bin){
		bin = getUnusedBin(set);
		bin.hash = hash;
		bin.elt = set.trans(ptr, data); // Transform the pointer.
		
		bin.next = set.table[idx];
		set.table[idx] = bin;
		
		set.entries++;
		
		// Resize the set if it's full.
		if(setIsFull(set))
			cpHashSetResize(set);
	}
	
	return bin.elt;
}

void *
cpHashSetRemove(cpHashSet *set, cpHashValue hash, void *ptr)
{
	int idx = hash%set.size;
	
	// Pointer to the previous bin pointer.
	cpHashSetBin **prev_ptr = &set.table[idx];
	// Pointer the the current bin.
	cpHashSetBin *bin = set.table[idx];
	
	// Find the bin
	while(bin && !set.eql(ptr, bin.elt)){
		prev_ptr = &bin.next;
		bin = bin.next;
	}
	
	// Remove it if it exists.
	if(bin){
		// Update the previous bin pointer to point to the next bin.
		(*prev_ptr) = bin.next;
		set.entries--;
		
		void *return_value = bin.elt;
		
		recycleBin(set, bin);
		
		return return_value;
	}
	
	return null;
}

void *
cpHashSetFind(cpHashSet *set, cpHashValue hash, void *ptr)
{	
	int idx = hash%set.size;
	cpHashSetBin *bin = set.table[idx];
	while(bin && !set.eql(ptr, bin.elt))
		bin = bin.next;
		
	return (bin ? bin.elt : set.default_value);
}

void
cpHashSetEach(cpHashSet *set, cpHashSetIterFunc func, void *data)
{
	for(int i=0; i<set.size; i++){
		cpHashSetBin *bin = set.table[i];
		while(bin){
			cpHashSetBin *next = bin.next;
			func(bin.elt, data);
			bin = next;
		}
	}
}

void
cpHashSetFilter(cpHashSet *set, cpHashSetFilterFunc func, void *data)
{
	// Iterate over all the chains.
	for(int i=0; i<set.size; i++){
		// The rest works similarly to cpHashSetRemove() above.
		cpHashSetBin **prev_ptr = &set.table[i];
		cpHashSetBin *bin = set.table[i];
		while(bin){
			cpHashSetBin *next = bin.next;
			
			if(func(bin.elt, data)){
				prev_ptr = &bin.next;
			} else {
				(*prev_ptr) = next;

				set.entries--;
				recycleBin(set, bin);
			}
			
			bin = next;
		}
	}
}