/* $Id$ */
/*
* This file is part of OpenTTD.
* OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
* OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
* See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see .
*/
/** @file queue.cpp Implementation of the Queue/Hash. */
#include "../../stdafx.h"
#include "../../core/alloc_func.hpp"
#include "queue.h"
/*
* Binary Heap
* For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm
*/
const int Queue::BINARY_HEAP_BLOCKSIZE_BITS = 10; ///< The number of elements that will be malloc'd at a time.
const int Queue::BINARY_HEAP_BLOCKSIZE = 1 << Queue::BINARY_HEAP_BLOCKSIZE_BITS;
const int Queue::BINARY_HEAP_BLOCKSIZE_MASK = Queue::BINARY_HEAP_BLOCKSIZE - 1;
/**
* Clears the queue, by removing all values from it. Its state is
* effectively reset. If free_items is true, each of the items cleared
* in this way are free()'d.
*/
void Queue::Clear(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 < this->blocks; i++) {
if (this->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 ((this->size >> BINARY_HEAP_BLOCKSIZE_BITS) == i &&
(this->size & BINARY_HEAP_BLOCKSIZE_MASK) == j) {
break; // We're past the last element
}
free(this->elements[i][j].item);
}
}
if (i != 0) {
/* Leave the first block of memory alone */
free(this->elements[i]);
this->elements[i] = NULL;
}
}
this->size = 0;
this->blocks = 1;
}
/**
* Frees the queue, by reclaiming all memory allocated by it. After
* this it is no longer usable. If free_items is true, any remaining
* items are free()'d too.
*/
void Queue::Free(bool free_values)
{
uint i;
this->Clear(free_values);
for (i = 0; i < this->blocks; i++) {
if (this->elements[i] == NULL) break;
free(this->elements[i]);
}
free(this->elements);
}
/**
* Pushes an element into the queue, at the appropriate place for the queue.
* Requires the queue pointer to be of an appropriate type, of course.
*/
bool Queue::Push(void *item, int priority)
{
#ifdef QUEUE_DEBUG
printf("[BinaryHeap] Pushing an element. There are %d elements left\n", this->size);
#endif
if (this->size == this->max_size) return false;
assert(this->size < this->max_size);
if (this->elements[this->size >> BINARY_HEAP_BLOCKSIZE_BITS] == NULL) {
/* The currently allocated blocks are full, allocate a new one */
assert((this->size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
this->elements[this->size >> BINARY_HEAP_BLOCKSIZE_BITS] = MallocT(BINARY_HEAP_BLOCKSIZE);
this->blocks++;
#ifdef QUEUE_DEBUG
printf("[BinaryHeap] Increasing size of elements to %d nodes\n", this->blocks * BINARY_HEAP_BLOCKSIZE);
#endif
}
/* Add the item at the end of the array */
this->GetElement(this->size + 1).priority = priority;
this->GetElement(this->size + 1).item = item;
this->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 = this->size;
while (i > 1) {
/* Get the parent of this object (divide by 2) */
j = i / 2;
/* Is the parent bigger than the current, switch them */
if (this->GetElement(i).priority <= this->GetElement(j).priority) {
temp = this->GetElement(j);
this->GetElement(j) = this->GetElement(i);
this->GetElement(i) = temp;
i = j;
} else {
/* It is not, we're done! */
break;
}
}
}
return true;
}
/**
* Deletes the item from the queue. priority should be specified if
* known, which speeds up the deleting for some queue's. Should be -1
* if not known.
*/
bool Queue::Delete(void *item, int priority)
{
uint i = 0;
#ifdef QUEUE_DEBUG
printf("[BinaryHeap] Deleting an element. There are %d elements left\n", this->size);
#endif
/* First, we try to find the item.. */
do {
if (this->GetElement(i + 1).item == item) break;
i++;
} while (i < this->size);
/* We did not find the item, so we return false */
if (i == this->size) return false;
/* Now we put the last item over the current item while decreasing the size of the elements */
this->size--;
this->GetElement(i + 1) = this->GetElement(this->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 <= this->size) {
/* Is this child smaller than the parent? */
if (this->GetElement(j).priority >= this->GetElement(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 (this->GetElement(i).priority >= this->GetElement(2 * j + 1).priority) i = 2 * j + 1;
/* Do we have one child? */
} else if (2 * j <= this->size) {
if (this->GetElement(j).priority >= this->GetElement(2 * j).priority) i = 2 * j;
}
/* One of our childs is smaller than we are, switch */
if (i != j) {
temp = this->GetElement(j);
this->GetElement(j) = this->GetElement(i);
this->GetElement(i) = temp;
} else {
/* None of our childs is smaller, so we stay here.. stop :) */
break;
}
}
}
return true;
}
/**
* Pops the first element from the queue. What exactly is the first element,
* is defined by the exact type of queue.
*/
void *Queue::Pop()
{
void *result;
#ifdef QUEUE_DEBUG
printf("[BinaryHeap] Popping an element. There are %d elements left\n", this->size);
#endif
if (this->size == 0) return NULL;
/* The best item is always on top, so give that as result */
result = this->GetElement(1).item;
/* And now we should get rid of this item... */
this->Delete(this->GetElement(1).item, this->GetElement(1).priority);
return result;
}
/**
* Initializes a binary heap and allocates internal memory for maximum of
* max_size elements
*/
void Queue::Init(uint max_size)
{
this->max_size = max_size;
this->size = 0;
/* We malloc memory in block of BINARY_HEAP_BLOCKSIZE
* It autosizes when it runs out of memory */
this->elements = CallocT((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);
this->elements[0] = MallocT(BINARY_HEAP_BLOCKSIZE);
this->blocks = 1;
#ifdef QUEUE_DEBUG
printf("[BinaryHeap] Initial size of elements is %d nodes\n", BINARY_HEAP_BLOCKSIZE);
#endif
}
/* 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 = (HashNode*)MallocT(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);
for (i = 0; i < num_buckets; i++) h->buckets_in_use[i] = false;
}
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
}
#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 = MallocT(1);
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;
}