OpenTTD
smallstack_type.hpp
Go to the documentation of this file.
1 /* $Id$ */
2 
3 /*
4  * This file is part of OpenTTD.
5  * 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.
6  * 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.
7  * 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/>.
8  */
9 
12 #ifndef SMALLSTACK_TYPE_HPP
13 #define SMALLSTACK_TYPE_HPP
14 
15 #include "smallvec_type.hpp"
16 #include <mutex>
17 
23 template<typename Titem, typename Tindex, Tindex Tgrowth_step, Tindex Tmax_size>
24 class SimplePool {
25 public:
26  inline SimplePool() : first_unused(0), first_free(0) {}
27 
33  inline std::mutex &GetMutex() { return this->mutex; }
34 
39  inline Titem &Get(Tindex index) { return this->data[index]; }
40 
45  inline Tindex Create()
46  {
47  Tindex index = this->FindFirstFree();
48  if (index < Tmax_size) {
49  this->data[index].valid = true;
50  this->first_free = index + 1;
51  this->first_unused = max(this->first_unused, this->first_free);
52  }
53  return index;
54  }
55 
60  inline void Destroy(Tindex index)
61  {
62  this->data[index].valid = false;
63  this->first_free = min(this->first_free, index);
64  }
65 
66 private:
67 
68  inline Tindex FindFirstFree()
69  {
70  Tindex index = this->first_free;
71  for (; index < this->first_unused; index++) {
72  if (!this->data[index].valid) return index;
73  }
74 
75  if (index >= this->data.size() && index < Tmax_size) {
76  this->data.resize(index + 1);
77  }
78  return index;
79  }
80 
81  struct SimplePoolPoolItem : public Titem {
82  bool valid;
83  };
84 
85  Tindex first_unused;
86  Tindex first_free;
87 
88  std::mutex mutex;
89  std::vector<SimplePoolPoolItem> data;
90 };
91 
96 template <typename Titem, typename Tindex>
98  Tindex next;
99  Titem value;
100 
106  inline SmallStackItem(const Titem &value, Tindex next) :
107  next(next), value(value) {}
108  SmallStackItem() = default;
109 };
110 
137 template <typename Titem, typename Tindex, Titem Tinvalid, Tindex Tgrowth_step, Tindex Tmax_size>
138 class SmallStack : public SmallStackItem<Titem, Tindex> {
139 public:
140 
142 
146  struct PooledSmallStack : public Item {
147  Tindex branch_count;
148  };
149 
151 
156  inline SmallStack(const Titem &value = Tinvalid) : Item(value, Tmax_size) {}
157 
161  inline ~SmallStack()
162  {
163  /* Pop() locks the mutex and after each pop the pool is consistent.*/
164  while (this->next != Tmax_size) this->Pop();
165  }
166 
171  inline SmallStack(const SmallStack &other) : Item(other) { this->Branch(); }
172 
178  inline SmallStack &operator=(const SmallStack &other)
179  {
180  if (this == &other) return *this;
181  while (this->next != Tmax_size) this->Pop();
182  this->next = other.next;
183  this->value = other.value;
184  /* Deleting and branching are independent operations, so it's fine to
185  * acquire separate locks for them. */
186  this->Branch();
187  return *this;
188  }
189 
195  inline void Push(const Titem &item)
196  {
197  if (this->value != Tinvalid) {
198  std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
199  Tindex new_item = SmallStack::GetPool().Create();
200  if (new_item != Tmax_size) {
201  PooledSmallStack &pushed = SmallStack::GetPool().Get(new_item);
202  pushed.value = this->value;
203  pushed.next = this->next;
204  pushed.branch_count = 0;
205  this->next = new_item;
206  }
207  }
208  this->value = item;
209  }
210 
215  inline Titem Pop()
216  {
217  Titem ret = this->value;
218  if (this->next == Tmax_size) {
219  this->value = Tinvalid;
220  } else {
221  std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
222  PooledSmallStack &popped = SmallStack::GetPool().Get(this->next);
223  this->value = popped.value;
224  if (popped.branch_count == 0) {
225  SmallStack::GetPool().Destroy(this->next);
226  } else {
227  --popped.branch_count;
228  /* We can't use Branch() here as we already have the mutex.*/
229  if (popped.next != Tmax_size) {
230  ++(SmallStack::GetPool().Get(popped.next).branch_count);
231  }
232  }
233  /* Accessing popped here is no problem as the pool will only set
234  * the validity flag, not actually delete the item, on Destroy().
235  * It's impossible for another thread to acquire the same item in
236  * the mean time because of the mutex. */
237  this->next = popped.next;
238  }
239  return ret;
240  }
241 
246  inline bool IsEmpty() const
247  {
248  return this->value == Tinvalid && this->next == Tmax_size;
249  }
250 
256  inline bool Contains(const Titem &item) const
257  {
258  if (item == Tinvalid || item == this->value) return true;
259  if (this->next != Tmax_size) {
260  std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
261  const SmallStack *in_list = this;
262  do {
263  in_list = static_cast<const SmallStack *>(
264  static_cast<const Item *>(&SmallStack::GetPool().Get(in_list->next)));
265  if (in_list->value == item) return true;
266  } while (in_list->next != Tmax_size);
267  }
268  return false;
269  }
270 
271 protected:
272  static SmallStackPool &GetPool()
273  {
274  static SmallStackPool pool;
275  return pool;
276  }
277 
281  inline void Branch()
282  {
283  if (this->next != Tmax_size) {
284  std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
285  ++(SmallStack::GetPool().Get(this->next).branch_count);
286  }
287  }
288 };
289 
290 #endif
Minimal stack that uses a pool to avoid pointers.
Simple vector class that allows allocating an item without the need to copy this->data needlessly...
static T max(const T a, const T b)
Returns the maximum of two values.
Definition: math_func.hpp:26
Tindex next
Pool index of next item.
bool IsEmpty() const
Check if the stack is empty.
~SmallStack()
Remove the head of stack and all other items members that are unique to it.
uint8 valid
Bits indicating what variable is valid (for each bit, 0 is invalid, 1 is valid).
void Destroy(Tindex index)
Destroy (or rather invalidate) the item at the given index.
Titem & Get(Tindex index)
Get the item at position index.
std::mutex lock
synchronization for playback status fields
Definition: win32_m.cpp:36
A simplified pool which stores values instead of pointers and doesn&#39;t redefine operator new/delete...
Titem Pop()
Pop an item from the stack.
bool Contains(const Titem &item) const
Check if the given item is contained in the stack.
Tindex Create()
Create a new item and return its index.
Titem value
Value of current item.
void Push(const Titem &item)
Pushes a new item onto the stack if there is still space in the underlying pool.
static T min(const T a, const T b)
Returns the minimum of two values.
Definition: math_func.hpp:42
SmallStack & operator=(const SmallStack &other)
Shallow copy the stack, marking the first item as branched.
SmallStack item that can be kept in a pool.
Base class for SmallStack.
SmallStackItem(const Titem &value, Tindex next)
Create a new item.
SmallStack(const SmallStack &other)
Shallow copy the stack, marking the first item as branched.
void Branch()
Create a branch in the pool if necessary.
std::mutex & GetMutex()
Get the mutex.
Tindex branch_count
Number of branches in the tree structure this item is parent of.
SmallStack(const Titem &value=Tinvalid)
Constructor for a stack with one or two items in it.