summaryrefslogtreecommitdiff
path: root/src/queue.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/queue.cpp')
-rw-r--r--src/queue.cpp736
1 files changed, 736 insertions, 0 deletions
diff --git a/src/queue.cpp b/src/queue.cpp
new file mode 100644
index 000000000..9986442bf
--- /dev/null
+++ b/src/queue.cpp
@@ -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;
+}
generated by cgit v1.2.3-70-g09d2 (git 2.47.0) at 2024-11-05 21:52:48 +0000