--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/trunk/chipmunkd/cpHashSet.d	Thu Dec 02 02:11:26 2010 +0100
@@ -0,0 +1,277 @@
+
+// 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;
+		}
+	}
+}