tron@2186: /* $Id$ */
tron@2186: 
truelight@84: #include "stdafx.h"
Darkvater@1891: #include "openttd.h"
truelight@84: #include "queue.h"
truelight@84: 
tron@1095: static void Stack_Clear(Queue* q, bool free_values)
truelight@84: {
truelight@84: 	uint i;
truelight@84: 	if (free_values)
truelight@107: 		for (i=0;i<q->data.stack.size;i++)
truelight@107: 			free(q->data.stack.elements[i]);
truelight@107: 	q->data.stack.size = 0;
truelight@84: }
truelight@84: 
tron@1095: static void Stack_Free(Queue* q, bool free_values)
truelight@84: {
truelight@84: 	q->clear(q, free_values);
truelight@107: 	free(q->data.stack.elements);
truelight@84: 	if (q->freeq)
truelight@84: 		free(q);
truelight@84: }
truelight@84: 
tron@1095: static bool Stack_Push(Queue* q, void* item, int priority)
tron@1095: {
truelight@107: 	if (q->data.stack.size == q->data.stack.max_size)
truelight@84: 		return false;
truelight@107: 	q->data.stack.elements[q->data.stack.size++] = item;
truelight@84: 	return true;
truelight@84: }
truelight@84: 
tron@1095: static void* Stack_Pop(Queue* q)
tron@1095: {
truelight@84: 	void* result;
truelight@107: 	if (q->data.stack.size == 0)
truelight@84: 		return NULL;
truelight@107: 	result = q->data.stack.elements[--q->data.stack.size];
truelight@84: 
truelight@84: 	return result;
truelight@84: }
truelight@84: 
tron@1095: static bool Stack_Delete(Queue* q, void* item, int priority)
truelight@84: {
truelight@84: 	return false;
truelight@84: }
truelight@84: 
tron@1095: static Queue* init_stack(Queue* q, uint max_size)
tron@1095: {
truelight@84: 	q->push = Stack_Push;
truelight@84: 	q->pop = Stack_Pop;
truelight@84: 	q->del = Stack_Delete;
truelight@84: 	q->clear = Stack_Clear;
truelight@84: 	q->free = Stack_Free;
truelight@107: 	q->data.stack.max_size = max_size;
truelight@107: 	q->data.stack.size = 0;
truelight@107: 	q->data.stack.elements = malloc(max_size * sizeof(void*));
truelight@84: 	q->freeq = false;
truelight@84: 	return q;
truelight@84: }
truelight@84: 
truelight@84: Queue* new_Stack(uint max_size)
truelight@84: {
truelight@84: 	Queue* q = malloc(sizeof(Queue));
truelight@84: 	init_stack(q, max_size);
truelight@84: 	q->freeq = true;
truelight@84: 	return q;
truelight@84: }
truelight@84: 
truelight@84: /*
truelight@84:  * Fifo
truelight@84:  */
truelight@84: 
tron@1095: static void Fifo_Clear(Queue* q, bool free_values)
truelight@84: {
truelight@84: 	uint head, tail;
truelight@84: 	if (free_values) {
truelight@107: 		head = q->data.fifo.head;
truelight@107: 		tail = q->data.fifo.tail; /* cache for speed */
truelight@84: 		while (head != tail) {
truelight@107: 			free(q->data.fifo.elements[tail]);
truelight@107: 			tail = (tail + 1) % q->data.fifo.max_size;
truelight@84: 		}
truelight@84: 	}
truelight@107: 	q->data.fifo.head = q->data.fifo.tail = 0;
truelight@84: }
truelight@84: 
tron@1095: static void Fifo_Free(Queue* q, bool free_values)
truelight@84: {
truelight@84: 	q->clear(q, free_values);
truelight@107: 	free(q->data.fifo.elements);
truelight@84: 	if (q->freeq)
truelight@84: 		free(q);
truelight@84: }
truelight@84: 
tron@1095: static bool Fifo_Push(Queue* q, void* item, int priority)
tron@1095: {
truelight@107: 	uint next = (q->data.fifo.head + 1) % q->data.fifo.max_size;
truelight@107: 	if (next == q->data.fifo.tail)
truelight@84: 		return false;
truelight@107: 	q->data.fifo.elements[q->data.fifo.head] = item;
truelight@84: 
truelight@84: 
truelight@107: 	q->data.fifo.head = next;
truelight@84: 	return true;
truelight@84: }
truelight@84: 
tron@1095: static void* Fifo_Pop(Queue* q)
tron@1095: {
truelight@84: 	void* result;
truelight@107: 	if (q->data.fifo.head == q->data.fifo.tail)
truelight@84: 		return NULL;
truelight@107: 	result = q->data.fifo.elements[q->data.fifo.tail];
truelight@84: 
truelight@84: 
truelight@107: 	q->data.fifo.tail = (q->data.fifo.tail + 1) % q->data.fifo.max_size;
truelight@84: 	return result;
truelight@84: }
truelight@84: 
tron@1095: static bool Fifo_Delete(Queue* q, void* item, int priority)
truelight@84: {
truelight@84: 	return false;
truelight@84: }
truelight@84: 
tron@1095: static Queue* init_fifo(Queue* q, uint max_size)
tron@1095: {
truelight@84: 	q->push = Fifo_Push;
truelight@84: 	q->pop = Fifo_Pop;
truelight@84: 	q->del = Fifo_Delete;
truelight@84: 	q->clear = Fifo_Clear;
truelight@84: 	q->free = Fifo_Free;
truelight@107: 	q->data.fifo.max_size = max_size;
truelight@107: 	q->data.fifo.head = 0;
truelight@107: 	q->data.fifo.tail = 0;
truelight@107: 	q->data.fifo.elements = malloc(max_size * sizeof(void*));
truelight@84: 	q->freeq = false;
truelight@84: 	return q;
truelight@84: }
truelight@84: 
truelight@84: Queue* new_Fifo(uint max_size)
truelight@84: {
truelight@84: 	Queue* q = malloc(sizeof(Queue));
truelight@84: 	init_fifo(q, max_size);
truelight@84: 	q->freeq = true;
truelight@84: 	return q;
truelight@84: }
truelight@84: 
truelight@84: 
truelight@84: /*
truelight@84:  * Insertion Sorter
truelight@84:  */
truelight@84: 
tron@1095: static void InsSort_Clear(Queue* q, bool free_values)
tron@1095: {
truelight@107: 	InsSortNode* node = q->data.inssort.first;
truelight@84: 	InsSortNode* prev;
truelight@84: 	while (node != NULL) {
truelight@84: 		if (free_values)
truelight@84: 			free(node->item);
truelight@84: 		prev = node;
truelight@84: 		node = node->next;
truelight@84: 		free(prev);
truelight@201: 
truelight@84: 	}
truelight@107: 	q->data.inssort.first = NULL;
truelight@84: }
truelight@84: 
tron@1095: static void InsSort_Free(Queue* q, bool free_values)
truelight@84: {
truelight@84: 	q->clear(q, free_values);
truelight@84: 	if (q->freeq)
truelight@84: 		free(q);
truelight@84: }
truelight@84: 
tron@1095: static bool InsSort_Push(Queue* q, void* item, int priority)
tron@1095: {
truelight@84: 	InsSortNode* newnode = malloc(sizeof(InsSortNode));
truelight@84: 	if (newnode == NULL) return false;
truelight@84: 	newnode->item = item;
truelight@84: 	newnode->priority = priority;
truelight@107: 	if (q->data.inssort.first == NULL || q->data.inssort.first->priority >= priority) {
truelight@107: 		newnode->next = q->data.inssort.first;
truelight@107: 		q->data.inssort.first = newnode;
truelight@84: 	} else {
truelight@107: 		InsSortNode* node = q->data.inssort.first;
truelight@84: 		while( node != NULL ) {
truelight@84: 			if (node->next == NULL || node->next->priority >= priority) {
truelight@84: 				newnode->next = node->next;
truelight@84: 				node->next = newnode;
truelight@84: 				break;
truelight@84: 			}
truelight@84: 			node = node->next;
truelight@84: 		}
truelight@84: 	}
truelight@84: 	return true;
truelight@84: }
truelight@84: 
tron@1095: static void* InsSort_Pop(Queue* q)
tron@1095: {
truelight@107: 	InsSortNode* node = q->data.inssort.first;
truelight@84: 	void* result;
truelight@84: 	if (node == NULL)
truelight@84: 		return NULL;
truelight@84: 	result = node->item;
truelight@107: 	q->data.inssort.first = q->data.inssort.first->next;
truelight@107: 	if (q->data.inssort.first)
truelight@107: 		assert(q->data.inssort.first->priority >= node->priority);
truelight@84: 	free(node);
truelight@84: 	return result;
truelight@84: }
truelight@84: 
tron@1095: static bool InsSort_Delete(Queue* q, void* item, int priority)
truelight@84: {
truelight@84: 	return false;
truelight@84: }
truelight@84: 
truelight@84: void init_InsSort(Queue* q) {
truelight@84: 	q->push = InsSort_Push;
truelight@84: 	q->pop = InsSort_Pop;
truelight@84: 	q->del = InsSort_Delete;
truelight@84: 	q->clear = InsSort_Clear;
truelight@84: 	q->free = InsSort_Free;
truelight@107: 	q->data.inssort.first = NULL;
truelight@84: 	q->freeq = false;
truelight@84: }
truelight@84: 
tron@1093: Queue* new_InsSort(void)
tron@1093: {
truelight@84: 	Queue* q = malloc(sizeof(Queue));
truelight@84: 	init_InsSort(q);
truelight@84: 	q->freeq = true;
truelight@84: 	return q;
truelight@84: }
truelight@84: 
truelight@84: 
truelight@84: /*
truelight@84:  * Binary Heap
truelight@84:  * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm
truelight@84:  */
truelight@84: 
truelight@84: #define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS)
truelight@84: #define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE-1)
truelight@84: 
truelight@84: // To make our life easy, we make the next define
truelight@84: //  Because Binary Heaps works with array from 1 to n,
truelight@84: //  and C with array from 0 to n-1, and we don't like typing
truelight@107: //  q->data.binaryheap.elements[i-1] every time, we use this define.
truelight@107: #define BIN_HEAP_ARR(i) q->data.binaryheap.elements[((i)-1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i)-1) & BINARY_HEAP_BLOCKSIZE_MASK]
truelight@84: 
tron@1095: static void BinaryHeap_Clear(Queue* q, bool free_values)
truelight@84: {
truelight@84: 	/* Free all items if needed and free all but the first blocks of
truelight@84: 	 * memory */
truelight@84: 	uint i,j;
truelight@107: 	for (i=0;i<q->data.binaryheap.blocks;i++) {
truelight@107: 		if (q->data.binaryheap.elements[i] == NULL) {
truelight@84: 			/* No more allocated blocks */
truelight@84: 			break;
truelight@84: 		}
truelight@84: 		/* For every allocated block */
truelight@84: 		if (free_values)
truelight@84: 			for (j=0;j<(1<<BINARY_HEAP_BLOCKSIZE_BITS);j++) {
truelight@84: 				/* For every element in the block */
truelight@107: 				if ((q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS) == i
truelight@107: 					&& (q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == j)
truelight@84: 					break; /* We're past the last element */
truelight@107: 				free(q->data.binaryheap.elements[i][j].item);
truelight@84: 			}
truelight@84: 		if (i != 0) {
truelight@84: 			/* Leave the first block of memory alone */
truelight@107: 			free(q->data.binaryheap.elements[i]);
truelight@107: 			q->data.binaryheap.elements[i] = NULL;
truelight@84: 		}
truelight@84: 	}
truelight@107: 	q->data.binaryheap.size = 0;
truelight@107: 	q->data.binaryheap.blocks = 1;
truelight@84: }
truelight@84: 
tron@1095: static void BinaryHeap_Free(Queue* q, bool free_values)
truelight@84: {
truelight@84: 	uint i;
truelight@84: 	q->clear(q, free_values);
truelight@107: 	for (i=0;i<q->data.binaryheap.blocks;i++) {
truelight@107: 		if (q->data.binaryheap.elements[i] == NULL)
truelight@84: 			break;
truelight@107: 		free(q->data.binaryheap.elements[i]);
truelight@84: 	}
tron@2799: 	free(q->data.binaryheap.elements);
truelight@84: 	if (q->freeq)
truelight@84: 		free(q);
truelight@84: }
truelight@84: 
tron@1095: static bool BinaryHeap_Push(Queue* q, void* item, int priority)
tron@1095: {
truelight@84: 	#ifdef QUEUE_DEBUG
truelight@107: 			printf("[BinaryHeap] Pushing an element. There are %d elements left\n", q->data.binaryheap.size);
truelight@84: 	#endif
truelight@107: 	if (q->data.binaryheap.size == q->data.binaryheap.max_size)
truelight@84: 		return false;
truelight@107: 	assert(q->data.binaryheap.size < q->data.binaryheap.max_size);
truelight@201: 
truelight@107: 	if (q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) {
truelight@84: 		/* The currently allocated blocks are full, allocate a new one */
truelight@107: 		assert((q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
truelight@107: 		q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(BinaryHeapNode));
truelight@107: 		q->data.binaryheap.blocks++;
truelight@84: #ifdef QUEUE_DEBUG
truelight@107: 		printf("[BinaryHeap] Increasing size of elements to %d nodes\n",q->data.binaryheap.blocks *  BINARY_HEAP_BLOCKSIZE);
truelight@84: #endif
truelight@84: 	}
truelight@84: 
truelight@84: 	// Add the item at the end of the array
truelight@107: 	BIN_HEAP_ARR(q->data.binaryheap.size+1).priority = priority;
truelight@107: 	BIN_HEAP_ARR(q->data.binaryheap.size+1).item = item;
truelight@107: 	q->data.binaryheap.size++;
truelight@84: 
truelight@84: 	// Now we are going to check where it belongs. As long as the parent is
truelight@84: 	// bigger, we switch with the parent
truelight@84: 	{
truelight@84: 		int i, j;
truelight@84: 		BinaryHeapNode temp;
truelight@107: 		i = q->data.binaryheap.size;
truelight@84: 		while (i > 1) {
truelight@84: 			// Get the parent of this object (divide by 2)
truelight@84: 			j = i / 2;
truelight@84: 			// Is the parent bigger then the current, switch them
truelight@84: 			if (BIN_HEAP_ARR(i).priority <= BIN_HEAP_ARR(j).priority) {
truelight@84: 				temp = BIN_HEAP_ARR(j);
truelight@84: 				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);
truelight@84: 				BIN_HEAP_ARR(i) = temp;
truelight@84: 				i = j;
truelight@84: 			} else {
truelight@84: 				// It is not, we're done!
truelight@84: 				break;
truelight@84: 			}
truelight@84: 		}
truelight@84: 	}
truelight@84: 
truelight@84: 	return true;
truelight@84: }
truelight@84: 
tron@1095: static bool BinaryHeap_Delete(Queue* q, void* item, int priority)
truelight@84: {
truelight@84: 	#ifdef QUEUE_DEBUG
truelight@107: 			printf("[BinaryHeap] Deleting an element. There are %d elements left\n", q->data.binaryheap.size);
truelight@84: 	#endif
truelight@84: 	uint i = 0;
truelight@84: 	// First, we try to find the item..
truelight@84: 	do {
truelight@84: 		if (BIN_HEAP_ARR(i+1).item == item) break;
truelight@84: 		i++;
truelight@107: 	} while (i < q->data.binaryheap.size);
truelight@84: 	// We did not find the item, so we return false
truelight@107: 	if (i == q->data.binaryheap.size) return false;
truelight@84: 
truelight@84: 	// Now we put the last item over the current item while decreasing the size of the elements
truelight@107: 	q->data.binaryheap.size--;
truelight@107: 	BIN_HEAP_ARR(i+1) = BIN_HEAP_ARR(q->data.binaryheap.size+1);
truelight@84: 
truelight@84: 	// Now the only thing we have to do, is resort it..
truelight@84: 	// On place i there is the item to be sorted.. let's start there
truelight@84: 	{
truelight@84: 		uint j;
truelight@84: 		BinaryHeapNode temp;
truelight@84: 		// Because of the fast that Binary Heap uses array from 1 to n, we need to increase
truelight@84: 		//   i with 1
truelight@84: 		i++;
truelight@84: 
truelight@84: 		for (;;) {
truelight@84: 			j = i;
truelight@84: 			// Check if we have 2 childs
truelight@107: 			if (2*j+1 <= q->data.binaryheap.size) {
miham@826: 				// Is this child smaller than the parent?
truelight@84: 				if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2*j).priority) {i = 2*j; }
truelight@84: 				// Yes, we _need_ to use i here, not j, because we want to have the smallest child
truelight@84: 				//  This way we get that straight away!
truelight@84: 				if (BIN_HEAP_ARR(i).priority >= BIN_HEAP_ARR(2*j+1).priority) { i = 2*j+1; }
truelight@84: 			// Do we have one child?
truelight@107: 			} else if (2*j <= q->data.binaryheap.size) {
truelight@84: 				if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2*j).priority) { i = 2*j; }
truelight@84: 			}
truelight@84: 
miham@826: 			// One of our childs is smaller than we are, switch
truelight@84: 			if (i != j) {
truelight@84: 				temp = BIN_HEAP_ARR(j);
truelight@84: 				BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i);
truelight@84: 				BIN_HEAP_ARR(i) = temp;
truelight@84: 			} else {
truelight@84: 				// None of our childs is smaller, so we stay here.. stop :)
truelight@84: 				break;
truelight@84: 			}
truelight@84: 		}
truelight@84: 	}
truelight@84: 
truelight@84: 	return true;
truelight@84: }
truelight@84: 
tron@1095: static void* BinaryHeap_Pop(Queue* q)
tron@1095: {
truelight@84: 	#ifdef QUEUE_DEBUG
truelight@107: 			printf("[BinaryHeap] Popping an element. There are %d elements left\n", q->data.binaryheap.size);
truelight@84: 	#endif
truelight@84: 	void* result;
truelight@107: 	if (q->data.binaryheap.size == 0)
truelight@84: 		return NULL;
truelight@84: 
truelight@84: 	// The best item is always on top, so give that as result
truelight@84: 	result = BIN_HEAP_ARR(1).item;
truelight@84: 	// And now we should get ride of this item...
truelight@84: 	BinaryHeap_Delete(q,BIN_HEAP_ARR(1).item, BIN_HEAP_ARR(1).priority);
truelight@84: 
truelight@84: 	return result;
truelight@84: }
truelight@84: 
truelight@84: void init_BinaryHeap(Queue* q, uint max_size)
truelight@84: {
truelight@84: 	assert(q);
truelight@84: 	q->push = BinaryHeap_Push;
truelight@84: 	q->pop = BinaryHeap_Pop;
truelight@84: 	q->del = BinaryHeap_Delete;
truelight@84: 	q->clear = BinaryHeap_Clear;
truelight@84: 	q->free = BinaryHeap_Free;
truelight@107: 	q->data.binaryheap.max_size = max_size;
truelight@107: 	q->data.binaryheap.size = 0;
truelight@84: 	// We malloc memory in block of BINARY_HEAP_BLOCKSIZE
truelight@84: 	//   It autosizes when it runs out of memory
matthijs@1247: 	q->data.binaryheap.elements = calloc(1, ((max_size - 1) / BINARY_HEAP_BLOCKSIZE*sizeof(BinaryHeapNode)) + 1);
truelight@107: 	q->data.binaryheap.elements[0] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(BinaryHeapNode));
truelight@107: 	q->data.binaryheap.blocks = 1;
truelight@84: 	q->freeq = false;
truelight@84: #ifdef QUEUE_DEBUG
truelight@84: 		printf("[BinaryHeap] Initial size of elements is %d nodes\n",(1024));
truelight@84: #endif
truelight@84: }
truelight@84: 
truelight@84: Queue* new_BinaryHeap(uint max_size) {
truelight@84: 	Queue* q = malloc(sizeof(Queue));
truelight@84: 	init_BinaryHeap(q, max_size);
truelight@84: 	q->freeq = true;
truelight@84: 	return q;
truelight@84: }
truelight@84: 
truelight@84: // Because we don't want anyone else to bother with our defines
truelight@84: #undef BIN_HEAP_ARR
truelight@84: 
truelight@84: /*
truelight@84:  * Hash
truelight@84:  */
truelight@84: 
matthijs@1661: void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets) {
truelight@84: 	/* Allocate space for the Hash, the buckets and the bucket flags */
matthijs@1661: 	uint i;
truelight@84: 	assert(h);
truelight@84: 	#ifdef HASH_DEBUG
truelight@84: 	debug("Allocated hash: %p", h);
truelight@84: 	#endif
truelight@84: 	h->hash = hash;
truelight@84: 	h->size = 0;
truelight@84: 	h->num_buckets = num_buckets;
truelight@84: 	h->buckets = malloc(num_buckets * (sizeof(HashNode) + sizeof(bool)));
truelight@84: 	#ifdef HASH_DEBUG
truelight@84: 	debug("Buckets = %p", h->buckets);
truelight@84: 	#endif
truelight@84: 	h->buckets_in_use = (bool*)(h->buckets + num_buckets);
truelight@84: 	h->freeh = false;
truelight@84: 	for (i=0;i<num_buckets;i++)
truelight@84: 		h->buckets_in_use[i] = false;
truelight@84: }
truelight@84: 
truelight@84: Hash* new_Hash(Hash_HashProc* hash, int num_buckets) {
truelight@84: 	Hash* h = malloc(sizeof(Hash));
truelight@84: 	init_Hash(h, hash, num_buckets);
truelight@84: 	h->freeh = true;
truelight@84: 	return h;
truelight@84: }
truelight@84: 
truelight@84: void delete_Hash(Hash* h, bool free_values) {
truelight@84: 	uint i;
truelight@84: 	/* Iterate all buckets */
truelight@84: 	for (i=0;i<h->num_buckets;i++)
truelight@84: 	{
truelight@84: 		if (h->buckets_in_use[i]) {
truelight@84: 			HashNode* node;
truelight@84: 			/* Free the first value */
truelight@201: 			if (free_values)
truelight@84: 				free(h->buckets[i].value);
truelight@84: 			node = h->buckets[i].next;
truelight@84: 			while (node != NULL) {
truelight@84: 				HashNode* prev = node;
truelight@84: 				node = node->next;
truelight@84: 				/* Free the value */
truelight@201: 				if (free_values)
truelight@84: 					free(prev->value);
truelight@84: 				/* Free the node */
truelight@84: 				free(prev);
truelight@84: 			}
truelight@84: 		}
truelight@84: 	}
truelight@84: 	free(h->buckets);
truelight@84: 	/* No need to free buckets_in_use, it is always allocated in one
truelight@84: 	 * malloc with buckets */
truelight@84: 	#ifdef HASH_DEBUG
truelight@84: 	debug("Freeing Hash: %p", h);
truelight@84: 	#endif
truelight@84: 	if (h->freeh)
truelight@84: 		free(h);
truelight@84: }
truelight@84: 
tron@2752: #ifdef HASH_STATS
tron@2752: static void stat_Hash(Hash* h)
matthijs@1661: {
matthijs@1661: 	uint used_buckets = 0;
matthijs@1661: 	uint max_collision = 0;
matthijs@1661: 	uint max_usage = 0;
matthijs@1661: 	uint usage[200];
matthijs@1662: 	uint i;
matthijs@1661: 	uint collision;
matthijs@1661: 	HashNode* node;
matthijs@1661: 
matthijs@1661: 	for (i=0;i<200;i++) usage[i] = 0;
matthijs@1661: 	for (i=0;i<h->num_buckets;i++) {
matthijs@1661: 		collision = 0;
matthijs@1661: 		if (h->buckets_in_use[i]) {
matthijs@1661: 			used_buckets++;
matthijs@1661: 			node = &h->buckets[i];
matthijs@1661: 			while (node != NULL) {
matthijs@1661: 				collision++;
matthijs@1661: 				node = node->next;
matthijs@1661: 			}
matthijs@1661: 			if (collision > max_collision) max_collision = collision;
matthijs@1661: 		}
matthijs@1661: 		if (collision > 199) collision = 199;
matthijs@1661: 		usage[collision]++;
matthijs@1661: 		if (collision >0 && usage[collision] >= max_usage) max_usage = usage[collision];
matthijs@1661: 	}
matthijs@1661: 	printf("---\nHash size: %d\nNodes used: %d\nNon empty buckets: %d\nMax collision: %d\n", h->num_buckets, h->size, used_buckets, max_collision);
matthijs@1661: 	printf("{ ");
matthijs@1661: 	for (i=0;i<=max_collision;i++)
matthijs@1661: 		if (usage[i]) {
matthijs@1661: 			printf("%d:%d ", i, usage[i]);
matthijs@1662: /*
tron@2026: 			if (i>0){
matthijs@1662: 				uint j;
matthijs@1661: 				for (j=0;j<(usage[i] * 160 / 800);j++)
matthijs@1661: 					printf("#");
matthijs@1662: 			}
matthijs@1661: 			printf("\n");
matthijs@1661: 			*/
matthijs@1661: 		}
matthijs@1661: 	printf ("}\n");
matthijs@1661: }
tron@2752: #endif
matthijs@1661: 
truelight@84: void clear_Hash(Hash* h, bool free_values)
truelight@84: {
truelight@84: 	uint i;
truelight@84: 	HashNode* node;
matthijs@1661: #ifdef HASH_STATS
matthijs@1661: 	if (h->size > 2000)
matthijs@1661: 		stat_Hash(h);
matthijs@1661: #endif
truelight@84: 	/* Iterate all buckets */
truelight@84: 	for (i=0;i<h->num_buckets;i++)
truelight@84: 	{
truelight@84: 		if (h->buckets_in_use[i]) {
truelight@84: 			h->buckets_in_use[i] = false;
truelight@84: 			/* Free the first value */
truelight@84: 			if (free_values)
truelight@84: 				free(h->buckets[i].value);
truelight@84: 			node = h->buckets[i].next;
truelight@84: 			while (node != NULL) {
truelight@84: 				HashNode* prev = node;
truelight@84: 				node = node->next;
truelight@84: 				if (free_values)
tron@2026: 					free(prev->value);
truelight@84: 				free(prev);
truelight@84: 			}
truelight@84: 		}
truelight@84: 	}
truelight@84: 	h->size = 0;
truelight@84: }
truelight@84: 
truelight@84: /* Finds the node that that saves this key pair. If it is not
truelight@84:  * found, returns NULL. If it is found, *prev is set to the
truelight@84:  * node before the one found, or if the node found was the first in the bucket
truelight@84:  * to NULL. If it is not found, *prev is set to the last HashNode in the
truelight@84:  * bucket, or NULL if it is empty. prev can also be NULL, in which case it is
truelight@84:  * not used for output.
truelight@84:  */
tron@1095: static HashNode* Hash_FindNode(Hash* h, uint key1, uint key2, HashNode** prev_out)
tron@1095: {
truelight@84: 	uint hash = h->hash(key1, key2);
truelight@84: 	HashNode* result = NULL;
truelight@84: 	#ifdef HASH_DEBUG
truelight@84: 	debug("Looking for %u, %u", key1, key2);
truelight@84: 	#endif
truelight@84: 	/* Check if the bucket is empty */
truelight@84: 	if (!h->buckets_in_use[hash]) {
truelight@84: 		if (prev_out)
truelight@84: 			*prev_out = NULL;
truelight@84: 		result = NULL;
truelight@84: 	/* Check the first node specially */
truelight@84: 	} else if (h->buckets[hash].key1 == key1 && h->buckets[hash].key2 == key2) {
truelight@84: 		/* Save the value */
truelight@84: 		result = h->buckets + hash;
truelight@84: 		if (prev_out)
truelight@84: 			*prev_out = NULL;
truelight@84: 	#ifdef HASH_DEBUG
truelight@84: 		debug("Found in first node: %p", result);
truelight@84: 	#endif
truelight@84: 	/* Check all other nodes */
truelight@84: 	} else {
truelight@84: 		HashNode* prev = h->buckets + hash;
truelight@84: 		HashNode* node = prev->next;
truelight@84: 		while (node != NULL) {
truelight@84: 			if (node->key1 == key1 && node->key2 == key2) {
truelight@84: 				/* Found it */
truelight@84: 				result = node;
truelight@84: 	#ifdef HASH_DEBUG
truelight@84: 				debug("Found in other node: %p", result);
truelight@84: 	#endif
truelight@84: 				break;
truelight@84: 			}
truelight@84: 			prev = node;
truelight@84: 			node = node->next;
truelight@84: 		}
truelight@84: 		if (prev_out)
truelight@84: 			*prev_out = prev;
truelight@84: 	}
truelight@84: 	#ifdef HASH_DEBUG
truelight@84: 	if (result == NULL)
truelight@84: 		debug("Not found");
truelight@84: 	#endif
truelight@84: 	return result;
truelight@84: }
truelight@84: 
truelight@84: void* Hash_Delete(Hash* h, uint key1, uint key2) {
truelight@84: 	void* result;
truelight@84: 	HashNode* prev; /* Used as output var for below function call */
truelight@84: 	HashNode* node = Hash_FindNode(h, key1, key2, &prev);
truelight@84: 
truelight@84: 	if (node == NULL) {
truelight@84: 		/* not found */
truelight@84: 		result = NULL;
truelight@84: 	} else if (prev == NULL) {
truelight@84: 		/* It is in the first node, we can't free that one, so we free
truelight@84: 		 * the next one instead (if there is any)*/
truelight@84: 		/* Save the value */
truelight@84: 		result = node->value;
truelight@84: 		if (node->next != NULL) {
truelight@84: 			HashNode* next = node->next;
truelight@84: 			/* Copy the second to the first */
truelight@84: 			*node = *next;
truelight@84: 			/* Free the second */
truelight@84: 		#ifndef NOFREE
truelight@84: 			free(next);
truelight@84: 		#endif
truelight@84: 		} else {
truelight@84: 			/* This was the last in this bucket */
truelight@84: 			/* Mark it as empty */
truelight@84: 			uint hash = h->hash(key1, key2);
truelight@84: 			h->buckets_in_use[hash] = false;
truelight@84: 		}
truelight@84: 	} else {
truelight@84: 		/* It is in another node */
truelight@84: 		/* Save the value */
truelight@84: 		result = node->value;
truelight@84: 		/* Link previous and next nodes */
truelight@84: 		prev->next = node->next;
truelight@84: 		/* Free the node */
truelight@84: 		#ifndef NOFREE
truelight@84: 		free(node);
truelight@84: 		#endif
truelight@84: 	}
truelight@84: 	if (result != NULL)
truelight@84: 		h->size--;
truelight@84: 	return result;
truelight@84: }
truelight@84: 
truelight@84: 
truelight@84: void* Hash_Set(Hash* h, uint key1, uint key2, void* value) {
truelight@84: 	HashNode* prev;
truelight@84: 	HashNode* node = Hash_FindNode(h, key1, key2, &prev);
truelight@84: 	void* result = NULL;
truelight@84: 	if (node != NULL) {
truelight@84: 		/* Found it */
truelight@84: 		result = node->value;
truelight@84: 		node->value = value;
truelight@84: 		return result;
truelight@84: 	}
truelight@84: 	/* It is not yet present, let's add it */
truelight@84: 	if (prev == NULL) {
truelight@84: 		/* The bucket is still empty */
truelight@84: 		uint hash = h->hash(key1, key2);
truelight@84: 		h->buckets_in_use[hash] = true;
truelight@84: 		node = h->buckets + hash;
truelight@84: 	} else {
truelight@84: 		/* Add it after prev */
truelight@84: 		node = malloc(sizeof(HashNode));
truelight@84: 		prev->next = node;
truelight@84: 	}
truelight@84: 	node->next = NULL;
truelight@84: 	node->key1 = key1;
truelight@84: 	node->key2 = key2;
truelight@84: 	node->value = value;
truelight@84: 	h->size++;
truelight@84: 	return NULL;
truelight@84: }
truelight@84: 
truelight@84: void* Hash_Get(Hash* h, uint key1, uint key2) {
truelight@84: 	HashNode* node = Hash_FindNode(h, key1, key2, NULL);
truelight@84: 	#ifdef HASH_DEBUG
truelight@84: 	debug("Found node: %p", node);
truelight@84: 	#endif
truelight@84: 	if (node == NULL) {
truelight@84: 		/* Node not found */
truelight@84: 		return NULL;
truelight@84: 	} else {
truelight@84: 		return node->value;
truelight@84: 	}
truelight@84: }
truelight@84: 
truelight@84: uint Hash_Size(Hash* h) {
truelight@84:     return h->size;
truelight@84: }