|
@@ -80,27 +80,20 @@ void BinaryHeap::Free(bool free_values)
|
|
|
/**
|
|
|
* 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 BinaryHeap::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<BinaryHeapNode>(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++;
|
|
@@ -138,16 +131,12 @@ bool BinaryHeap::Push(void *item, int pr
|
|
|
* if not known.
|
|
|
*/
|
|
|
bool BinaryHeap::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 */
|
|
@@ -201,16 +190,12 @@ bool BinaryHeap::Delete(void *item, int
|
|
|
* is defined by the exact type of queue.
|
|
|
*/
|
|
|
void *BinaryHeap::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);
|
|
@@ -228,15 +213,12 @@ void BinaryHeap::Init(uint 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<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);
|
|
|
this->elements[0] = MallocT<BinaryHeapNode>(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
|
|
|
|
|
|
/*
|
|
@@ -249,22 +231,16 @@ void BinaryHeap::Init(uint max_size)
|
|
|
*/
|
|
|
void Hash::Init(Hash_HashProc *hash, uint num_buckets)
|
|
|
{
|
|
|
/* Allocate space for the Hash, the buckets and the bucket flags */
|
|
|
uint i;
|
|
|
|
|
|
#ifdef HASH_DEBUG
|
|
|
debug("Allocated hash: %p", this);
|
|
|
#endif
|
|
|
this->hash = hash;
|
|
|
this->size = 0;
|
|
|
this->num_buckets = num_buckets;
|
|
|
this->buckets = (HashNode*)MallocT<byte>(num_buckets * (sizeof(*this->buckets) + sizeof(*this->buckets_in_use)));
|
|
|
#ifdef HASH_DEBUG
|
|
|
debug("Buckets = %p", this->buckets);
|
|
|
#endif
|
|
|
this->buckets_in_use = (bool*)(this->buckets + num_buckets);
|
|
|
for (i = 0; i < num_buckets; i++) this->buckets_in_use[i] = false;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Deletes the hash and cleans up. Only cleans up memory allocated by new_Hash
|
|
@@ -294,15 +270,12 @@ void Hash::Delete(bool free_values)
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
free(this->buckets);
|
|
|
/* No need to free buckets_in_use, it is always allocated in one
|
|
|
* malloc with buckets */
|
|
|
#ifdef HASH_DEBUG
|
|
|
debug("Freeing Hash: %p", this);
|
|
|
#endif
|
|
|
}
|
|
|
|
|
|
#ifdef HASH_STATS
|
|
|
void Hash::PrintStatistics() const
|
|
|
{
|
|
|
uint used_buckets = 0;
|
|
@@ -358,13 +331,13 @@ void Hash::PrintStatistics() const
|
|
|
*/
|
|
|
void Hash::Clear(bool free_values)
|
|
|
{
|
|
|
uint i;
|
|
|
|
|
|
#ifdef HASH_STATS
|
|
|
if (this->size > 2000) stat_Hash(this);
|
|
|
if (this->size > 2000) this->PrintStatistics();
|
|
|
#endif
|
|
|
|
|
|
/* Iterate all buckets */
|
|
|
for (i = 0; i < this->num_buckets; i++) {
|
|
|
if (this->buckets_in_use[i]) {
|
|
|
HashNode *node;
|
|
@@ -395,48 +368,36 @@ void Hash::Clear(bool free_values)
|
|
|
*/
|
|
|
HashNode *Hash::FindNode(uint key1, uint key2, HashNode** prev_out) const
|
|
|
{
|
|
|
uint hash = this->hash(key1, key2);
|
|
|
HashNode *result = NULL;
|
|
|
|
|
|
#ifdef HASH_DEBUG
|
|
|
debug("Looking for %u, %u", key1, key2);
|
|
|
#endif
|
|
|
/* Check if the bucket is empty */
|
|
|
if (!this->buckets_in_use[hash]) {
|
|
|
if (prev_out != NULL) *prev_out = NULL;
|
|
|
result = NULL;
|
|
|
/* Check the first node specially */
|
|
|
} else if (this->buckets[hash].key1 == key1 && this->buckets[hash].key2 == key2) {
|
|
|
/* Save the value */
|
|
|
result = this->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 = this->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;
|
|
|
}
|
|
|
|
|
|
/**
|
|
|
* Deletes the value with the specified key pair from the hash and returns
|
|
|
* that value. Returns NULL when the value was not present. The value returned
|
|
@@ -458,15 +419,13 @@ void *Hash::DeleteValue(uint key1, uint
|
|
|
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 = this->hash(key1, key2);
|
|
|
this->buckets_in_use[hash] = false;
|
|
|
}
|
|
@@ -474,15 +433,13 @@ void *Hash::DeleteValue(uint key1, uint
|
|
|
/* 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) this->size--;
|
|
|
return result;
|
|
|
}
|
|
|
|
|
|
/**
|
|
@@ -525,11 +482,8 @@ void *Hash::Set(uint key1, uint key2, vo
|
|
|
* present.
|
|
|
*/
|
|
|
void *Hash::Get(uint key1, uint key2) const
|
|
|
{
|
|
|
HashNode *node = this->FindNode(key1, key2, NULL);
|
|
|
|
|
|
#ifdef HASH_DEBUG
|
|
|
debug("Found node: %p", node);
|
|
|
#endif
|
|
|
return (node != NULL) ? node->value : NULL;
|
|
|
}
|