OpenTTD
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 */
Binary Heap.
Definition: queue.h:26
Definition: queue.h:71
BinaryHeapNode & GetElement(uint i)
Get an element from the #elements.
Definition: queue.h:44
uint GetSize() const
Gets the current size of the hash.
Definition: queue.h:97
Definition: queue.h:60
uint blocks
The amount of blocks for which space is reserved in elements.
Definition: queue.h:52
uint Hash_HashProc(uint key1, uint key2)
Generates a hash code from the given key pair.
Definition: queue.h:70
static const int BINARY_HEAP_BLOCKSIZE_BITS
The number of elements that will be malloc&#39;d at a time.
Definition: queue.h:28