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: %u\n"
311 "Max collision: %u\n",
312 this->num_buckets, this->size, used_buckets, max_collision
315 for (i = 0; i <= max_collision; i++) {
317 printf(
"%u:%u ", 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;
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--;
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;
491 return (node !=
nullptr) ? node->value :
nullptr;