OpenTTD Source  1.11.0-beta2
queue.cpp
Go to the documentation of this file.
1 /*
2  * This file is part of OpenTTD.
3  * 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.
4  * 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.
5  * 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 <http://www.gnu.org/licenses/>.
6  */
7 
10 #include "../../stdafx.h"
11 #include "../../core/alloc_func.hpp"
12 #include "queue.h"
13 
14 #include "../../safeguards.h"
15 
16 
17 /*
18  * Binary Heap
19  * For information, see: http://www.policyalmanac.org/games/binaryHeaps.htm
20  */
21 
23 const int BinaryHeap::BINARY_HEAP_BLOCKSIZE = 1 << BinaryHeap::BINARY_HEAP_BLOCKSIZE_BITS;
24 const int BinaryHeap::BINARY_HEAP_BLOCKSIZE_MASK = BinaryHeap::BINARY_HEAP_BLOCKSIZE - 1;
25 
31 void BinaryHeap::Clear(bool free_values)
32 {
33  /* Free all items if needed and free all but the first blocks of memory */
34  uint i;
35  uint j;
36 
37  for (i = 0; i < this->blocks; i++) {
38  if (this->elements[i] == nullptr) {
39  /* No more allocated blocks */
40  break;
41  }
42  /* For every allocated block */
43  if (free_values) {
44  for (j = 0; j < (1 << BINARY_HEAP_BLOCKSIZE_BITS); j++) {
45  /* For every element in the block */
46  if ((this->size >> BINARY_HEAP_BLOCKSIZE_BITS) == i &&
47  (this->size & BINARY_HEAP_BLOCKSIZE_MASK) == j) {
48  break; // We're past the last element
49  }
50  free(this->elements[i][j].item);
51  }
52  }
53  if (i != 0) {
54  /* Leave the first block of memory alone */
55  free(this->elements[i]);
56  this->elements[i] = nullptr;
57  }
58  }
59  this->size = 0;
60  this->blocks = 1;
61 }
62 
68 void BinaryHeap::Free(bool free_values)
69 {
70  uint i;
71 
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]);
76  }
77  free(this->elements);
78 }
79 
84 bool BinaryHeap::Push(void *item, int priority)
85 {
86  if (this->size == this->max_size) return false;
87  assert(this->size < this->max_size);
88 
89  if (this->elements[this->size >> BINARY_HEAP_BLOCKSIZE_BITS] == nullptr) {
90  /* The currently allocated blocks are full, allocate a new one */
91  assert((this->size & BINARY_HEAP_BLOCKSIZE_MASK) == 0);
92  this->elements[this->size >> BINARY_HEAP_BLOCKSIZE_BITS] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
93  this->blocks++;
94  }
95 
96  /* Add the item at the end of the array */
97  this->GetElement(this->size + 1).priority = priority;
98  this->GetElement(this->size + 1).item = item;
99  this->size++;
100 
101  /* Now we are going to check where it belongs. As long as the parent is
102  * bigger, we switch with the parent */
103  {
104  BinaryHeapNode temp;
105  int i;
106  int j;
107 
108  i = this->size;
109  while (i > 1) {
110  /* Get the parent of this object (divide by 2) */
111  j = i / 2;
112  /* Is the parent bigger than the current, switch them */
113  if (this->GetElement(i).priority <= this->GetElement(j).priority) {
114  temp = this->GetElement(j);
115  this->GetElement(j) = this->GetElement(i);
116  this->GetElement(i) = temp;
117  i = j;
118  } else {
119  /* It is not, we're done! */
120  break;
121  }
122  }
123  }
124 
125  return true;
126 }
127 
133 bool BinaryHeap::Delete(void *item, int priority)
134 {
135  uint i = 0;
136 
137  /* First, we try to find the item.. */
138  do {
139  if (this->GetElement(i + 1).item == item) break;
140  i++;
141  } while (i < this->size);
142  /* We did not find the item, so we return false */
143  if (i == this->size) return false;
144 
145  /* Now we put the last item over the current item while decreasing the size of the elements */
146  this->size--;
147  this->GetElement(i + 1) = this->GetElement(this->size + 1);
148 
149  /* Now the only thing we have to do, is resort it..
150  * On place i there is the item to be sorted.. let's start there */
151  {
152  uint j;
153  BinaryHeapNode temp;
154  /* Because of the fact that Binary Heap uses array from 1 to n, we need to
155  * increase i by 1
156  */
157  i++;
158 
159  for (;;) {
160  j = i;
161  /* Check if we have 2 children */
162  if (2 * j + 1 <= this->size) {
163  /* Is this child smaller than the parent? */
164  if (this->GetElement(j).priority >= this->GetElement(2 * j).priority) i = 2 * j;
165  /* Yes, we _need_ to use i here, not j, because we want to have the smallest child
166  * This way we get that straight away! */
167  if (this->GetElement(i).priority >= this->GetElement(2 * j + 1).priority) i = 2 * j + 1;
168  /* Do we have one child? */
169  } else if (2 * j <= this->size) {
170  if (this->GetElement(j).priority >= this->GetElement(2 * j).priority) i = 2 * j;
171  }
172 
173  /* One of our children is smaller than we are, switch */
174  if (i != j) {
175  temp = this->GetElement(j);
176  this->GetElement(j) = this->GetElement(i);
177  this->GetElement(i) = temp;
178  } else {
179  /* None of our children is smaller, so we stay here.. stop :) */
180  break;
181  }
182  }
183  }
184 
185  return true;
186 }
187 
193 {
194  void *result;
195 
196  if (this->size == 0) return nullptr;
197 
198  /* The best item is always on top, so give that as result */
199  result = this->GetElement(1).item;
200  /* And now we should get rid of this item... */
201  this->Delete(this->GetElement(1).item, this->GetElement(1).priority);
202 
203  return result;
204 }
205 
210 void BinaryHeap::Init(uint max_size)
211 {
212  this->max_size = max_size;
213  this->size = 0;
214  /* We malloc memory in block of BINARY_HEAP_BLOCKSIZE
215  * It autosizes when it runs out of memory */
216  this->elements = CallocT<BinaryHeapNode*>((max_size - 1) / BINARY_HEAP_BLOCKSIZE + 1);
217  this->elements[0] = MallocT<BinaryHeapNode>(BINARY_HEAP_BLOCKSIZE);
218  this->blocks = 1;
219 }
220 
221 /* Because we don't want anyone else to bother with our defines */
222 #undef BIN_HEAP_ARR
223 
224 /*
225  * Hash
226  */
227 
232 void Hash::Init(Hash_HashProc *hash, uint num_buckets)
233 {
234  /* Allocate space for the Hash, the buckets and the bucket flags */
235  uint i;
236 
237  /* Ensure the size won't overflow. */
238  CheckAllocationConstraints(sizeof(*this->buckets) + sizeof(*this->buckets_in_use), num_buckets);
239 
240  this->hash = hash;
241  this->size = 0;
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;
246 }
247 
253 void Hash::Delete(bool free_values)
254 {
255  uint i;
256 
257  /* Iterate all buckets */
258  for (i = 0; i < this->num_buckets; i++) {
259  if (this->buckets_in_use[i]) {
260  HashNode *node;
261 
262  /* Free the first value */
263  if (free_values) free(this->buckets[i].value);
264  node = this->buckets[i].next;
265  while (node != nullptr) {
266  HashNode *prev = node;
267 
268  node = node->next;
269  /* Free the value */
270  if (free_values) free(prev->value);
271  /* Free the node */
272  free(prev);
273  }
274  }
275  }
276  free(this->buckets);
277  /* No need to free buckets_in_use, it is always allocated in one
278  * malloc with buckets */
279 }
280 
281 #ifdef HASH_STATS
282 void Hash::PrintStatistics() const
283 {
284  uint used_buckets = 0;
285  uint max_collision = 0;
286  uint max_usage = 0;
287  uint usage[200];
288  uint i;
289 
290  for (i = 0; i < lengthof(usage); i++) usage[i] = 0;
291  for (i = 0; i < this->num_buckets; i++) {
292  uint collision = 0;
293  if (this->buckets_in_use[i]) {
294  const HashNode *node;
295 
296  used_buckets++;
297  for (node = &this->buckets[i]; node != nullptr; node = node->next) collision++;
298  if (collision > max_collision) max_collision = collision;
299  }
300  if (collision >= lengthof(usage)) collision = lengthof(usage) - 1;
301  usage[collision]++;
302  if (collision > 0 && usage[collision] >= max_usage) {
303  max_usage = usage[collision];
304  }
305  }
306  printf(
307  "---\n"
308  "Hash size: %u\n"
309  "Nodes used: %u\n"
310  "Non empty buckets: %u\n"
311  "Max collision: %u\n",
312  this->num_buckets, this->size, used_buckets, max_collision
313  );
314  printf("{ ");
315  for (i = 0; i <= max_collision; i++) {
316  if (usage[i] > 0) {
317  printf("%u:%u ", i, usage[i]);
318 #if 0
319  if (i > 0) {
320  uint j;
321 
322  for (j = 0; j < usage[i] * 160 / 800; j++) putchar('#');
323  }
324  printf("\n");
325 #endif
326  }
327  }
328  printf ("}\n");
329 }
330 #endif
331 
335 void Hash::Clear(bool free_values)
336 {
337  uint i;
338 
339 #ifdef HASH_STATS
340  if (this->size > 2000) this->PrintStatistics();
341 #endif
342 
343  /* Iterate all buckets */
344  for (i = 0; i < this->num_buckets; i++) {
345  if (this->buckets_in_use[i]) {
346  HashNode *node;
347 
348  this->buckets_in_use[i] = false;
349  /* Free the first value */
350  if (free_values) free(this->buckets[i].value);
351  node = this->buckets[i].next;
352  while (node != nullptr) {
353  HashNode *prev = node;
354 
355  node = node->next;
356  if (free_values) free(prev->value);
357  free(prev);
358  }
359  }
360  }
361  this->size = 0;
362 }
363 
372 HashNode *Hash::FindNode(uint key1, uint key2, HashNode** prev_out) const
373 {
374  uint hash = this->hash(key1, key2);
375  HashNode *result = nullptr;
376 
377  /* Check if the bucket is empty */
378  if (!this->buckets_in_use[hash]) {
379  if (prev_out != nullptr) *prev_out = nullptr;
380  result = nullptr;
381  /* Check the first node specially */
382  } else if (this->buckets[hash].key1 == key1 && this->buckets[hash].key2 == key2) {
383  /* Save the value */
384  result = this->buckets + hash;
385  if (prev_out != nullptr) *prev_out = nullptr;
386  /* Check all other nodes */
387  } else {
388  HashNode *prev = this->buckets + hash;
389  HashNode *node;
390 
391  for (node = prev->next; node != nullptr; node = node->next) {
392  if (node->key1 == key1 && node->key2 == key2) {
393  /* Found it */
394  result = node;
395  break;
396  }
397  prev = node;
398  }
399  if (prev_out != nullptr) *prev_out = prev;
400  }
401  return result;
402 }
403 
409 void *Hash::DeleteValue(uint key1, uint key2)
410 {
411  void *result;
412  HashNode *prev; // Used as output var for below function call
413  HashNode *node = this->FindNode(key1, key2, &prev);
414 
415  if (node == nullptr) {
416  /* not found */
417  result = nullptr;
418  } else if (prev == nullptr) {
419  /* It is in the first node, we can't free that one, so we free
420  * the next one instead (if there is any)*/
421  /* Save the value */
422  result = node->value;
423  if (node->next != nullptr) {
424  HashNode *next = node->next;
425  /* Copy the second to the first */
426  *node = *next;
427  /* Free the second */
428  free(next);
429  } else {
430  /* This was the last in this bucket
431  * Mark it as empty */
432  uint hash = this->hash(key1, key2);
433  this->buckets_in_use[hash] = false;
434  }
435  } else {
436  /* It is in another node
437  * Save the value */
438  result = node->value;
439  /* Link previous and next nodes */
440  prev->next = node->next;
441  /* Free the node */
442  free(node);
443  }
444  if (result != nullptr) this->size--;
445  return result;
446 }
447 
452 void *Hash::Set(uint key1, uint key2, void *value)
453 {
454  HashNode *prev;
455  HashNode *node = this->FindNode(key1, key2, &prev);
456 
457  if (node != nullptr) {
458  /* Found it */
459  void *result = node->value;
460 
461  node->value = value;
462  return result;
463  }
464  /* It is not yet present, let's add it */
465  if (prev == nullptr) {
466  /* The bucket is still empty */
467  uint hash = this->hash(key1, key2);
468  this->buckets_in_use[hash] = true;
469  node = this->buckets + hash;
470  } else {
471  /* Add it after prev */
472  node = MallocT<HashNode>(1);
473  prev->next = node;
474  }
475  node->next = nullptr;
476  node->key1 = key1;
477  node->key2 = key2;
478  node->value = value;
479  this->size++;
480  return nullptr;
481 }
482 
487 void *Hash::Get(uint key1, uint key2) const
488 {
489  HashNode *node = this->FindNode(key1, key2, nullptr);
490 
491  return (node != nullptr) ? node->value : nullptr;
492 }
CheckAllocationConstraints
static void CheckAllocationConstraints(size_t element_size, size_t num_elements)
Checks whether allocating memory would overflow size_t.
Definition: alloc_func.hpp:29
BinaryHeap::Clear
void Clear(bool free_values)
Clears the queue, by removing all values from it.
Definition: queue.cpp:31
Hash::Delete
void Delete(bool free_values)
Deletes the hash and cleans up.
Definition: queue.cpp:253
BinaryHeap::Delete
bool Delete(void *item, int priority)
Deletes the item from the queue.
Definition: queue.cpp:133
HashNode
Definition: queue.h:60
BinaryHeapNode
Definition: queue.h:16
BinaryHeap::GetElement
BinaryHeapNode & GetElement(uint i)
Get an element from the #elements.
Definition: queue.h:44
BinaryHeap::blocks
uint blocks
The amount of blocks for which space is reserved in elements.
Definition: queue.h:52
Hash::Init
void Init(Hash_HashProc *hash, uint num_buckets)
Builds a new hash in an existing struct.
Definition: queue.cpp:232
Hash::Set
void * Set(uint key1, uint key2, void *value)
Sets the value associated with the given key pair to the given value.
Definition: queue.cpp:452
Hash::DeleteValue
void * DeleteValue(uint key1, uint key2)
Deletes the value with the specified key pair from the hash and returns that value.
Definition: queue.cpp:409
queue.h
Hash::Get
void * Get(uint key1, uint key2) const
Gets the value associated with the given key pair, or nullptr when it is not present.
Definition: queue.cpp:487
BinaryHeap::Pop
void * Pop()
Pops the first element from the queue.
Definition: queue.cpp:192
Hash::FindNode
HashNode * FindNode(uint key1, uint key2, HashNode **prev_out) const
Finds the node that that saves this key pair.
Definition: queue.cpp:372
lengthof
#define lengthof(x)
Return the length of an fixed size array.
Definition: stdafx.h:367
BinaryHeap::BINARY_HEAP_BLOCKSIZE_BITS
static const int BINARY_HEAP_BLOCKSIZE_BITS
The number of elements that will be malloc'd at a time.
Definition: queue.h:28
BinaryHeap::Free
void Free(bool free_values)
Frees the queue, by reclaiming all memory allocated by it.
Definition: queue.cpp:68
BinaryHeap::Push
bool Push(void *item, int priority)
Pushes an element into the queue, at the appropriate place for the queue.
Definition: queue.cpp:84
free
static void free(const void *ptr)
Version of the standard free that accepts const pointers.
Definition: stdafx.h:454
BinaryHeap::Init
void Init(uint max_size)
Initializes a binary heap and allocates internal memory for maximum of max_size elements.
Definition: queue.cpp:210
Hash::Clear
void Clear(bool free_values)
Cleans the hash, but keeps the memory allocated.
Definition: queue.cpp:335
Hash_HashProc
uint Hash_HashProc(uint key1, uint key2)
Generates a hash code from the given key pair.
Definition: queue.h:70