OpenTTD Source  1.11.2
queue.h
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 #ifndef QUEUE_H
11 #define QUEUE_H
12 
13 //#define HASH_STATS
14 
15 
17  void *item;
18  int priority;
19 };
20 
21 
26 struct BinaryHeap {
27  static const int BINARY_HEAP_BLOCKSIZE;
28  static const int BINARY_HEAP_BLOCKSIZE_BITS;
29  static const int BINARY_HEAP_BLOCKSIZE_MASK;
30 
31  void Init(uint max_size);
32 
33  bool Push(void *item, int priority);
34  void *Pop();
35  bool Delete(void *item, int priority);
36  void Clear(bool free_values);
37  void Free(bool free_values);
38 
44  inline BinaryHeapNode &GetElement(uint i)
45  {
46  assert(i > 0);
47  return this->elements[(i - 1) >> BINARY_HEAP_BLOCKSIZE_BITS][(i - 1) & BINARY_HEAP_BLOCKSIZE_MASK];
48  }
49 
50  uint max_size;
51  uint size;
52  uint blocks;
53  BinaryHeapNode **elements;
54 };
55 
56 
57 /*
58  * Hash
59  */
60 struct HashNode {
61  uint key1;
62  uint key2;
63  void *value;
64  HashNode *next;
65 };
70 typedef uint Hash_HashProc(uint key1, uint key2);
71 struct Hash {
72  /* The hash function used */
73  Hash_HashProc *hash;
74  /* The amount of items in the hash */
75  uint size;
76  /* The number of buckets allocated */
77  uint num_buckets;
78  /* A pointer to an array of num_buckets buckets. */
79  HashNode *buckets;
80  /* A pointer to an array of numbuckets booleans, which will be true if
81  * there are any Nodes in the bucket */
82  bool *buckets_in_use;
83 
84  void Init(Hash_HashProc *hash, uint num_buckets);
85 
86  void *Get(uint key1, uint key2) const;
87  void *Set(uint key1, uint key2, void *value);
88 
89  void *DeleteValue(uint key1, uint key2);
90 
91  void Clear(bool free_values);
92  void Delete(bool free_values);
93 
97  inline uint GetSize() const
98  {
99  return this->size;
100  }
101 
102 protected:
103 #ifdef HASH_STATS
104  void PrintStatistics() const;
105 #endif
106  HashNode *FindNode(uint key1, uint key2, HashNode** prev_out) const;
107 };
108 
109 #endif /* QUEUE_H */
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
BinaryHeap
Binary Heap.
Definition: queue.h:26
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::GetSize
uint GetSize() const
Gets the current size of the hash.
Definition: queue.h:97
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
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
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
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
Definition: queue.h:71
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