10 #include "../../stdafx.h" 11 #include "../../core/alloc_func.hpp" 14 #include "../../safeguards.h" 24 const int BinaryHeap::BINARY_HEAP_BLOCKSIZE_MASK = BinaryHeap::BINARY_HEAP_BLOCKSIZE - 1;
37 for (i = 0; i < this->
blocks; i++) {
38 if (this->elements[i] ==
nullptr) {
47 (this->size & BINARY_HEAP_BLOCKSIZE_MASK) == j) {
50 free(this->elements[i][j].item);
55 free(this->elements[i]);
56 this->elements[i] =
nullptr;
72 this->
Clear(free_values);
73 for (i = 0; i < this->
blocks; i++) {
74 if (this->elements[i] ==
nullptr)
break;
75 free(this->elements[i]);
86 if (this->size == this->max_size)
return false;
87 assert(this->size < this->max_size);
91 assert((this->size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
97 this->
GetElement(this->size + 1).priority = priority;
139 if (this->
GetElement(i + 1).item == item)
break;
141 }
while (i < this->size);
143 if (i == this->size)
return false;
162 if (2 * j + 1 <= this->size) {
169 }
else if (2 * j <= this->size) {
196 if (this->size == 0)
return nullptr;
212 this->max_size = max_size;
216 this->elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);
217 this->elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
242 this->num_buckets = num_buckets;
243 this->buckets = (
HashNode*)MallocT<byte>(num_buckets * (
sizeof(*this->buckets) +
sizeof(*this->buckets_in_use)));
244 this->buckets_in_use = (
bool*)(this->buckets + num_buckets);
245 for (i = 0; i < num_buckets; i++) this->buckets_in_use[i] =
false;
258 for (i = 0; i < this->num_buckets; i++) {
259 if (this->buckets_in_use[i]) {
263 if (free_values)
free(this->buckets[i].value);
264 node = this->buckets[i].next;
265 while (node !=
nullptr) {
270 if (free_values)
free(prev->value);
282 void Hash::PrintStatistics()
const 284 uint used_buckets = 0;
285 uint max_collision = 0;
290 for (i = 0; i <
lengthof(usage); i++) usage[i] = 0;
291 for (i = 0; i < this->num_buckets; i++) {
293 if (this->buckets_in_use[i]) {
297 for (node = &this->buckets[i]; node !=
nullptr; node = node->next) collision++;
298 if (collision > max_collision) max_collision = collision;
302 if (collision > 0 && usage[collision] >= max_usage) {
303 max_usage = usage[collision];
310 "Non empty buckets: %d\n" 311 "Max collision: %d\n",
312 this->num_buckets, this->size, used_buckets, max_collision
315 for (i = 0; i <= max_collision; i++) {
317 printf(
"%d:%d ", i, usage[i]);
322 for (j = 0; j < usage[i] * 160 / 800; j++) putchar(
'#');
340 if (this->size > 2000) this->PrintStatistics();
344 for (i = 0; i < this->num_buckets; i++) {
345 if (this->buckets_in_use[i]) {
348 this->buckets_in_use[i] =
false;
350 if (free_values)
free(this->buckets[i].value);
351 node = this->buckets[i].next;
352 while (node !=
nullptr) {
356 if (free_values)
free(prev->value);
374 uint hash = this->hash(key1, key2);
378 if (!this->buckets_in_use[hash]) {
379 if (prev_out !=
nullptr) *prev_out =
nullptr;
382 }
else if (this->buckets[hash].key1 == key1 && this->buckets[hash].key2 == key2) {
384 result = this->buckets + hash;
385 if (prev_out !=
nullptr) *prev_out =
nullptr;
388 HashNode *prev = this->buckets + hash;
391 for (node = prev->next; node !=
nullptr; node = node->next) {
392 if (node->key1 == key1 && node->key2 == key2) {
399 if (prev_out !=
nullptr) *prev_out = prev;
413 HashNode *node = this->FindNode(key1, key2, &prev);
415 if (node ==
nullptr) {
418 }
else if (prev ==
nullptr) {
422 result = node->value;
423 if (node->next !=
nullptr) {
432 uint hash = this->hash(key1, key2);
433 this->buckets_in_use[hash] =
false;
438 result = node->value;
440 prev->next = node->next;
444 if (result !=
nullptr) this->size--;
455 HashNode *node = this->FindNode(key1, key2, &prev);
457 if (node !=
nullptr) {
459 void *result = node->value;
465 if (prev ==
nullptr) {
467 uint hash = this->hash(key1, key2);
468 this->buckets_in_use[hash] =
true;
469 node = this->buckets + hash;
472 node = MallocT<HashNode>(1);
475 node->next =
nullptr;
489 HashNode *node = this->FindNode(key1, key2,
nullptr);
491 return (node !=
nullptr) ? node->value :
nullptr;
void Free(bool free_values)
Frees the queue, by reclaiming all memory allocated by it.
void Delete(bool free_values)
Deletes the hash and cleans up.
void Clear(bool free_values)
Cleans the hash, but keeps the memory allocated.
BinaryHeapNode & GetElement(uint i)
Get an element from the #elements.
bool Delete(void *item, int priority)
Deletes the item from the queue.
void * Set(uint key1, uint key2, void *value)
Sets the value associated with the given key pair to the given value.
void Clear(bool free_values)
Clears the queue, by removing all values from it.
Binary heap implementation, hash implementation.
uint blocks
The amount of blocks for which space is reserved in elements.
void * DeleteValue(uint key1, uint key2)
Deletes the value with the specified key pair from the hash and returns that value.
uint Hash_HashProc(uint key1, uint key2)
Generates a hash code from the given key pair.
#define lengthof(x)
Return the length of an fixed size array.
void * Pop()
Pops the first element from the queue.
void Init(Hash_HashProc *hash, uint num_buckets)
Builds a new hash in an existing struct.
HashNode * FindNode(uint key1, uint key2, HashNode **prev_out) const
Finds the node that that saves this key pair.
void * Get(uint key1, uint key2) const
Gets the value associated with the given key pair, or nullptr when it is not present.
void Init(uint max_size)
Initializes a binary heap and allocates internal memory for maximum of max_size elements.
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
bool Push(void *item, int priority)
Pushes an element into the queue, at the appropriate place for the queue.
static const int BINARY_HEAP_BLOCKSIZE_BITS
The number of elements that will be malloc'd at a time.
static void CheckAllocationConstraints(size_t element_size, size_t num_elements)
Checks whether allocating memory would overflow size_t.