From 66bbf336c6af7353ef0aeed58002c46543b30635 Mon Sep 17 00:00:00 2001 From: rubidium Date: Tue, 2 Jan 2007 19:19:48 +0000 Subject: (svn r7759) -Merge: makefile rewrite. This merge features: - A proper ./configure, so everything needs to be configured only once, not for every make. - Usage of makedepend when available. This greatly reduces the time needed for generating the dependencies. - A generator for all project files. There is a single file with sources, which is used to generate Makefiles and the project files for MSVC. - Proper support for OSX universal binaries. - Object files for non-MSVC compiles are also placed in separate directories, making is faster to switch between debug and release compiles and it does not touch the directory with the source files. - Functionality to make a bundle of all needed files for for example a nightly or distribution of a binary with all needed GRFs and language files. Note: as this merge moves almost all files, it is recommended to make a backup of your working copy before updating your working copy. --- src/queue.c | 736 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 736 insertions(+) create mode 100644 src/queue.c (limited to 'src/queue.c') diff --git a/src/queue.c b/src/queue.c new file mode 100644 index 000000000..9986442bf --- /dev/null +++ b/src/queue.c @@ -0,0 +1,736 @@ +/* $Id$ */ + +#include "stdafx.h" +#include "openttd.h" +#include "queue.h" + +static void Stack_Clear(Queue* q, bool free_values) +{ + if (free_values) { + uint i; + + for (i = 0; i < q->data.stack.size; i++) free(q->data.stack.elements[i]); + } + q->data.stack.size = 0; +} + +static void Stack_Free(Queue* q, bool free_values) +{ + q->clear(q, free_values); + free(q->data.stack.elements); + if (q->freeq) free(q); +} + +static bool Stack_Push(Queue* q, void* item, int priority) +{ + if (q->data.stack.size == q->data.stack.max_size) return false; + q->data.stack.elements[q->data.stack.size++] = item; + return true; +} + +static void* Stack_Pop(Queue* q) +{ + if (q->data.stack.size == 0) return NULL; + return q->data.stack.elements[--q->data.stack.size]; +} + +static bool Stack_Delete(Queue* q, void* item, int priority) +{ + return false; +} + +static Queue* init_stack(Queue* q, uint max_size) +{ + q->push = Stack_Push; + q->pop = Stack_Pop; + q->del = Stack_Delete; + q->clear = Stack_Clear; + q->free = Stack_Free; + q->data.stack.max_size = max_size; + q->data.stack.size = 0; + q->data.stack.elements = malloc(max_size * sizeof(*q->data.stack.elements)); + q->freeq = false; + return q; +} + +Queue* new_Stack(uint max_size) +{ + Queue* q = malloc(sizeof(*q)); + + init_stack(q, max_size); + q->freeq = true; + return q; +} + +/* + * Fifo + */ + +static void Fifo_Clear(Queue* q, bool free_values) +{ + if (free_values) { + uint head = q->data.fifo.head; + uint tail = q->data.fifo.tail; /* cache for speed */ + + while (head != tail) { + free(q->data.fifo.elements[tail]); + tail = (tail + 1) % q->data.fifo.max_size; + } + } + q->data.fifo.head = 0; + q->data.fifo.tail = 0; +} + +static void Fifo_Free(Queue* q, bool free_values) +{ + q->clear(q, free_values); + free(q->data.fifo.elements); + if (q->freeq) free(q); +} + +static bool Fifo_Push(Queue* q, void* item, int priority) +{ + uint next = (q->data.fifo.head + 1) % q->data.fifo.max_size; + + if (next == q->data.fifo.tail) return false; + q->data.fifo.elements[q->data.fifo.head] = item; + + q->data.fifo.head = next; + return true; +} + +static void* Fifo_Pop(Queue* q) +{ + void* result; + + if (q->data.fifo.head == q->data.fifo.tail) return NULL; + result = q->data.fifo.elements[q->data.fifo.tail]; + + q->data.fifo.tail = (q->data.fifo.tail + 1) % q->data.fifo.max_size; + return result; +} + +static bool Fifo_Delete(Queue* q, void* item, int priority) +{ + return false; +} + +static Queue* init_fifo(Queue* q, uint max_size) +{ + q->push = Fifo_Push; + q->pop = Fifo_Pop; + q->del = Fifo_Delete; + q->clear = Fifo_Clear; + q->free = Fifo_Free; + q->data.fifo.max_size = max_size; + q->data.fifo.head = 0; + q->data.fifo.tail = 0; + q->data.fifo.elements = malloc(max_size * sizeof(*q->data.fifo.elements)); + q->freeq = false; + return q; +} + +Queue* new_Fifo(uint max_size) +{ + Queue* q = malloc(sizeof(*q)); + + init_fifo(q, max_size); + q->freeq = true; + return q; +} + + +/* + * Insertion Sorter + */ + +static void InsSort_Clear(Queue* q, bool free_values) +{ + InsSortNode* node = q->data.inssort.first; + InsSortNode* prev; + + while (node != NULL) { + if (free_values) free(node->item); + prev = node; + node = node->next; + free(prev); + } + q->data.inssort.first = NULL; +} + +static void InsSort_Free(Queue* q, bool free_values) +{ + q->clear(q, free_values); + if (q->freeq) free(q); +} + +static bool InsSort_Push(Queue* q, void* item, int priority) +{ + InsSortNode* newnode = malloc(sizeof(*newnode)); + + if (newnode == NULL) return false; + newnode->item = item; + newnode->priority = priority; + if (q->data.inssort.first == NULL || + q->data.inssort.first->priority >= priority) { + newnode->next = q->data.inssort.first; + q->data.inssort.first = newnode; + } else { + InsSortNode* node = q->data.inssort.first; + while (node != NULL) { + if (node->next == NULL || node->next->priority >= priority) { + newnode->next = node->next; + node->next = newnode; + break; + } + node = node->next; + } + } + return true; +} + +static void* InsSort_Pop(Queue* q) +{ + InsSortNode* node = q->data.inssort.first; + void* result; + + if (node == NULL) return NULL; + result = node->item; + q->data.inssort.first = q->data.inssort.first->next; + assert(q->data.inssort.first == NULL || q->data.inssort.first->priority >= node->priority); + free(node); + return result; +} + +static bool InsSort_Delete(Queue* q, void* item, int priority) +{ + return false; +} + +void init_InsSort(Queue* q) +{ + q->push = InsSort_Push; + q->pop = InsSort_Pop; + q->del = InsSort_Delete; + q->clear = InsSort_Clear; + q->free = InsSort_Free; + q->data.inssort.first = NULL; + q->freeq = false; +} + +Queue* new_InsSort(void) +{ + Queue* q = malloc(sizeof(*q)); + + init_InsSort(q); + q->freeq = true; + return q; +} + + +/* + * Binary Heap + * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm + */ + +#define BINARY_HEAP_BLOCKSIZE (1 << BINARY_HEAP_BLOCKSIZE_BITS) +#define BINARY_HEAP_BLOCKSIZE_MASK (BINARY_HEAP_BLOCKSIZE - 1) + +// To make our life easy, we make the next define +// Because Binary Heaps works with array from 1 to n, +// and C with array from 0 to n-1, and we don't like typing +// q->data.binaryheap.elements[i - 1] every time, we use this define. +#define BIN_HEAP_ARR(i) q->data.binaryheap.elements[((i) - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][((i) - 1) & BINARY_HEAP_BLOCKSIZE_MASK] + +static void BinaryHeap_Clear(Queue* q, bool free_values) +{ + /* Free all items if needed and free all but the first blocks of memory */ + uint i; + uint j; + + for (i = 0; i < q->data.binaryheap.blocks; i++) { + if (q->data.binaryheap.elements[i] == NULL) { + /* No more allocated blocks */ + break; + } + /* For every allocated block */ + if (free_values) { + for (j = 0; j < (1 << BINARY_HEAP_BLOCKSIZE_BITS); j++) { + /* For every element in the block */ + if ((q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS) == i && + (q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == j) { + break; /* We're past the last element */ + } + free(q->data.binaryheap.elements[i][j].item); + } + } + if (i != 0) { + /* Leave the first block of memory alone */ + free(q->data.binaryheap.elements[i]); + q->data.binaryheap.elements[i] = NULL; + } + } + q->data.binaryheap.size = 0; + q->data.binaryheap.blocks = 1; +} + +static void BinaryHeap_Free(Queue* q, bool free_values) +{ + uint i; + + q->clear(q, free_values); + for (i = 0; i < q->data.binaryheap.blocks; i++) { + if (q->data.binaryheap.elements[i] == NULL) break; + free(q->data.binaryheap.elements[i]); + } + free(q->data.binaryheap.elements); + if (q->freeq) free(q); +} + +static bool BinaryHeap_Push(Queue* q, void* item, int priority) +{ +#ifdef QUEUE_DEBUG + printf("[BinaryHeap] Pushing an element. There are %d elements left\n", q->data.binaryheap.size); +#endif + + if (q->data.binaryheap.size == q->data.binaryheap.max_size) return false; + assert(q->data.binaryheap.size < q->data.binaryheap.max_size); + + if (q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) { + /* The currently allocated blocks are full, allocate a new one */ + assert((q->data.binaryheap.size & BINARY_HEAP_BLOCKSIZE_MASK) == 0); + q->data.binaryheap.elements[q->data.binaryheap.size >> BINARY_HEAP_BLOCKSIZE_BITS] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(*q->data.binaryheap.elements[0])); + q->data.binaryheap.blocks++; +#ifdef QUEUE_DEBUG + printf("[BinaryHeap] Increasing size of elements to %d nodes\n", q->data.binaryheap.blocks * BINARY_HEAP_BLOCKSIZE); +#endif + } + + // Add the item at the end of the array + BIN_HEAP_ARR(q->data.binaryheap.size + 1).priority = priority; + BIN_HEAP_ARR(q->data.binaryheap.size + 1).item = item; + q->data.binaryheap.size++; + + // Now we are going to check where it belongs. As long as the parent is + // bigger, we switch with the parent + { + BinaryHeapNode temp; + int i; + int j; + + i = q->data.binaryheap.size; + while (i > 1) { + // Get the parent of this object (divide by 2) + j = i / 2; + // Is the parent bigger then the current, switch them + if (BIN_HEAP_ARR(i).priority <= BIN_HEAP_ARR(j).priority) { + temp = BIN_HEAP_ARR(j); + BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i); + BIN_HEAP_ARR(i) = temp; + i = j; + } else { + // It is not, we're done! + break; + } + } + } + + return true; +} + +static bool BinaryHeap_Delete(Queue* q, void* item, int priority) +{ + uint i = 0; + +#ifdef QUEUE_DEBUG + printf("[BinaryHeap] Deleting an element. There are %d elements left\n", q->data.binaryheap.size); +#endif + + // First, we try to find the item.. + do { + if (BIN_HEAP_ARR(i + 1).item == item) break; + i++; + } while (i < q->data.binaryheap.size); + // We did not find the item, so we return false + if (i == q->data.binaryheap.size) return false; + + // Now we put the last item over the current item while decreasing the size of the elements + q->data.binaryheap.size--; + BIN_HEAP_ARR(i + 1) = BIN_HEAP_ARR(q->data.binaryheap.size + 1); + + // Now the only thing we have to do, is resort it.. + // On place i there is the item to be sorted.. let's start there + { + uint j; + BinaryHeapNode temp; + /* Because of the fact that Binary Heap uses array from 1 to n, we need to + * increase i by 1 + */ + i++; + + for (;;) { + j = i; + // Check if we have 2 childs + if (2 * j + 1 <= q->data.binaryheap.size) { + // Is this child smaller than the parent? + if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j; + // Yes, we _need_ to use i here, not j, because we want to have the smallest child + // This way we get that straight away! + if (BIN_HEAP_ARR(i).priority >= BIN_HEAP_ARR(2 * j + 1).priority) i = 2 * j + 1; + // Do we have one child? + } else if (2 * j <= q->data.binaryheap.size) { + if (BIN_HEAP_ARR(j).priority >= BIN_HEAP_ARR(2 * j).priority) i = 2 * j; + } + + // One of our childs is smaller than we are, switch + if (i != j) { + temp = BIN_HEAP_ARR(j); + BIN_HEAP_ARR(j) = BIN_HEAP_ARR(i); + BIN_HEAP_ARR(i) = temp; + } else { + // None of our childs is smaller, so we stay here.. stop :) + break; + } + } + } + + return true; +} + +static void* BinaryHeap_Pop(Queue* q) +{ + void* result; + +#ifdef QUEUE_DEBUG + printf("[BinaryHeap] Popping an element. There are %d elements left\n", q->data.binaryheap.size); +#endif + + if (q->data.binaryheap.size == 0) return NULL; + + // The best item is always on top, so give that as result + result = BIN_HEAP_ARR(1).item; + // And now we should get rid of this item... + BinaryHeap_Delete(q, BIN_HEAP_ARR(1).item, BIN_HEAP_ARR(1).priority); + + return result; +} + +void init_BinaryHeap(Queue* q, uint max_size) +{ + assert(q != NULL); + q->push = BinaryHeap_Push; + q->pop = BinaryHeap_Pop; + q->del = BinaryHeap_Delete; + q->clear = BinaryHeap_Clear; + q->free = BinaryHeap_Free; + q->data.binaryheap.max_size = max_size; + q->data.binaryheap.size = 0; + // We malloc memory in block of BINARY_HEAP_BLOCKSIZE + // It autosizes when it runs out of memory + q->data.binaryheap.elements = calloc((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1, sizeof(*q->data.binaryheap.elements)); + q->data.binaryheap.elements[0] = malloc(BINARY_HEAP_BLOCKSIZE * sizeof(*q->data.binaryheap.elements[0])); + q->data.binaryheap.blocks = 1; + q->freeq = false; +#ifdef QUEUE_DEBUG + printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE); +#endif +} + +Queue* new_BinaryHeap(uint max_size) +{ + Queue* q = malloc(sizeof(*q)); + + init_BinaryHeap(q, max_size); + q->freeq = true; + return q; +} + +// Because we don't want anyone else to bother with our defines +#undef BIN_HEAP_ARR + +/* + * Hash + */ + +void init_Hash(Hash* h, Hash_HashProc* hash, uint num_buckets) +{ + /* Allocate space for the Hash, the buckets and the bucket flags */ + uint i; + + assert(h != NULL); +#ifdef HASH_DEBUG + debug("Allocated hash: %p", h); +#endif + h->hash = hash; + h->size = 0; + h->num_buckets = num_buckets; + h->buckets = malloc(num_buckets * (sizeof(*h->buckets) + sizeof(*h->buckets_in_use))); +#ifdef HASH_DEBUG + debug("Buckets = %p", h->buckets); +#endif + h->buckets_in_use = (bool*)(h->buckets + num_buckets); + h->freeh = false; + for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false; +} + +Hash* new_Hash(Hash_HashProc* hash, int num_buckets) +{ + Hash* h = malloc(sizeof(*h)); + + init_Hash(h, hash, num_buckets); + h->freeh = true; + return h; +} + +void delete_Hash(Hash* h, bool free_values) +{ + uint i; + + /* Iterate all buckets */ + for (i = 0; i < h->num_buckets; i++) { + if (h->buckets_in_use[i]) { + HashNode* node; + + /* Free the first value */ + if (free_values) free(h->buckets[i].value); + node = h->buckets[i].next; + while (node != NULL) { + HashNode* prev = node; + + node = node->next; + /* Free the value */ + if (free_values) free(prev->value); + /* Free the node */ + free(prev); + } + } + } + free(h->buckets); + /* No need to free buckets_in_use, it is always allocated in one + * malloc with buckets */ +#ifdef HASH_DEBUG + debug("Freeing Hash: %p", h); +#endif + if (h->freeh) free(h); +} + +#ifdef HASH_STATS +static void stat_Hash(const Hash* h) +{ + uint used_buckets = 0; + uint max_collision = 0; + uint max_usage = 0; + uint usage[200]; + uint i; + + for (i = 0; i < lengthof(usage); i++) usage[i] = 0; + for (i = 0; i < h->num_buckets; i++) { + uint collision = 0; + if (h->buckets_in_use[i]) { + const HashNode* node; + + used_buckets++; + for (node = &h->buckets[i]; node != NULL; node = node->next) collision++; + if (collision > max_collision) max_collision = collision; + } + if (collision >= lengthof(usage)) collision = lengthof(usage) - 1; + usage[collision]++; + if (collision > 0 && usage[collision] >= max_usage) { + max_usage = usage[collision]; + } + } + printf( + "---\n" + "Hash size: %d\n" + "Nodes used: %d\n" + "Non empty buckets: %d\n" + "Max collision: %d\n", + h->num_buckets, h->size, used_buckets, max_collision + ); + printf("{ "); + for (i = 0; i <= max_collision; i++) { + if (usage[i] > 0) { + printf("%d:%d ", i, usage[i]); +#if 0 + if (i > 0) { + uint j; + + for (j = 0; j < usage[i] * 160 / 800; j++) putchar('#'); + } + printf("\n"); +#endif + } + } + printf ("}\n"); +} +#endif + +void clear_Hash(Hash* h, bool free_values) +{ + uint i; + +#ifdef HASH_STATS + if (h->size > 2000) stat_Hash(h); +#endif + + /* Iterate all buckets */ + for (i = 0; i < h->num_buckets; i++) { + if (h->buckets_in_use[i]) { + HashNode* node; + + h->buckets_in_use[i] = false; + /* Free the first value */ + if (free_values) free(h->buckets[i].value); + node = h->buckets[i].next; + while (node != NULL) { + HashNode* prev = node; + + node = node->next; + if (free_values) free(prev->value); + free(prev); + } + } + } + h->size = 0; +} + +/* Finds the node that that saves this key pair. If it is not + * found, returns NULL. If it is found, *prev is set to the + * node before the one found, or if the node found was the first in the bucket + * to NULL. If it is not found, *prev is set to the last HashNode in the + * bucket, or NULL if it is empty. prev can also be NULL, in which case it is + * not used for output. + */ +static HashNode* Hash_FindNode(const Hash* h, uint key1, uint key2, HashNode** prev_out) +{ + uint hash = h->hash(key1, key2); + HashNode* result = NULL; + +#ifdef HASH_DEBUG + debug("Looking for %u, %u", key1, key2); +#endif + /* Check if the bucket is empty */ + if (!h->buckets_in_use[hash]) { + if (prev_out != NULL) *prev_out = NULL; + result = NULL; + /* Check the first node specially */ + } else if (h->buckets[hash].key1 == key1 && h->buckets[hash].key2 == key2) { + /* Save the value */ + result = h->buckets + hash; + if (prev_out != NULL) *prev_out = NULL; +#ifdef HASH_DEBUG + debug("Found in first node: %p", result); +#endif + /* Check all other nodes */ + } else { + HashNode* prev = h->buckets + hash; + HashNode* node; + + for (node = prev->next; node != NULL; node = node->next) { + if (node->key1 == key1 && node->key2 == key2) { + /* Found it */ + result = node; +#ifdef HASH_DEBUG + debug("Found in other node: %p", result); +#endif + break; + } + prev = node; + } + if (prev_out != NULL) *prev_out = prev; + } +#ifdef HASH_DEBUG + if (result == NULL) debug("Not found"); +#endif + return result; +} + +void* Hash_Delete(Hash* h, uint key1, uint key2) +{ + void* result; + HashNode* prev; /* Used as output var for below function call */ + HashNode* node = Hash_FindNode(h, key1, key2, &prev); + + if (node == NULL) { + /* not found */ + result = NULL; + } else if (prev == NULL) { + /* It is in the first node, we can't free that one, so we free + * the next one instead (if there is any)*/ + /* Save the value */ + result = node->value; + if (node->next != NULL) { + HashNode* next = node->next; + /* Copy the second to the first */ + *node = *next; + /* Free the second */ +#ifndef NOFREE + free(next); +#endif + } else { + /* This was the last in this bucket */ + /* Mark it as empty */ + uint hash = h->hash(key1, key2); + h->buckets_in_use[hash] = false; + } + } else { + /* It is in another node */ + /* Save the value */ + result = node->value; + /* Link previous and next nodes */ + prev->next = node->next; + /* Free the node */ +#ifndef NOFREE + free(node); +#endif + } + if (result != NULL) h->size--; + return result; +} + + +void* Hash_Set(Hash* h, uint key1, uint key2, void* value) +{ + HashNode* prev; + HashNode* node = Hash_FindNode(h, key1, key2, &prev); + + if (node != NULL) { + /* Found it */ + void* result = node->value; + + node->value = value; + return result; + } + /* It is not yet present, let's add it */ + if (prev == NULL) { + /* The bucket is still empty */ + uint hash = h->hash(key1, key2); + h->buckets_in_use[hash] = true; + node = h->buckets + hash; + } else { + /* Add it after prev */ + node = malloc(sizeof(*node)); + prev->next = node; + } + node->next = NULL; + node->key1 = key1; + node->key2 = key2; + node->value = value; + h->size++; + return NULL; +} + +void* Hash_Get(const Hash* h, uint key1, uint key2) +{ + HashNode* node = Hash_FindNode(h, key1, key2, NULL); + +#ifdef HASH_DEBUG + debug("Found node: %p", node); +#endif + return (node != NULL) ? node->value : NULL; +} + +uint Hash_Size(const Hash* h) +{ + return h->size; +} -- cgit v1.2.3-54-g00ecf