OpenTTD Source  1.11.0-beta2
smallstack_type.hpp
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 SMALLSTACK_TYPE_HPP
11 #define SMALLSTACK_TYPE_HPP
12 
13 #include "smallvec_type.hpp"
14 #include <mutex>
15 
21 template<typename Titem, typename Tindex, Tindex Tgrowth_step, Tindex Tmax_size>
22 class SimplePool {
23 public:
24  inline SimplePool() : first_unused(0), first_free(0) {}
25 
31  inline std::mutex &GetMutex() { return this->mutex; }
32 
37  inline Titem &Get(Tindex index) { return this->data[index]; }
38 
43  inline Tindex Create()
44  {
45  Tindex index = this->FindFirstFree();
46  if (index < Tmax_size) {
47  this->data[index].valid = true;
48  this->first_free = index + 1;
49  this->first_unused = std::max(this->first_unused, this->first_free);
50  }
51  return index;
52  }
53 
58  inline void Destroy(Tindex index)
59  {
60  this->data[index].valid = false;
61  this->first_free = std::min(this->first_free, index);
62  }
63 
64 private:
65 
66  inline Tindex FindFirstFree()
67  {
68  Tindex index = this->first_free;
69  for (; index < this->first_unused; index++) {
70  if (!this->data[index].valid) return index;
71  }
72 
73  if (index >= this->data.size() && index < Tmax_size) {
74  this->data.resize(index + 1);
75  }
76  return index;
77  }
78 
79  struct SimplePoolPoolItem : public Titem {
80  bool valid;
81  };
82 
83  Tindex first_unused;
84  Tindex first_free;
85 
86  std::mutex mutex;
87  std::vector<SimplePoolPoolItem> data;
88 };
89 
94 template <typename Titem, typename Tindex>
96  Tindex next;
97  Titem value;
98 
104  inline SmallStackItem(const Titem &value, Tindex next) :
105  next(next), value(value) {}
106  SmallStackItem() = default;
107 };
108 
135 template <typename Titem, typename Tindex, Titem Tinvalid, Tindex Tgrowth_step, Tindex Tmax_size>
136 class SmallStack : public SmallStackItem<Titem, Tindex> {
137 public:
138 
140 
144  struct PooledSmallStack : public Item {
145  Tindex branch_count;
146  };
147 
149 
154  inline SmallStack(const Titem &value = Tinvalid) : Item(value, Tmax_size) {}
155 
159  inline ~SmallStack()
160  {
161  /* Pop() locks the mutex and after each pop the pool is consistent.*/
162  while (this->next != Tmax_size) this->Pop();
163  }
164 
169  inline SmallStack(const SmallStack &other) : Item(other) { this->Branch(); }
170 
176  inline SmallStack &operator=(const SmallStack &other)
177  {
178  if (this == &other) return *this;
179  while (this->next != Tmax_size) this->Pop();
180  this->next = other.next;
181  this->value = other.value;
182  /* Deleting and branching are independent operations, so it's fine to
183  * acquire separate locks for them. */
184  this->Branch();
185  return *this;
186  }
187 
193  inline void Push(const Titem &item)
194  {
195  if (this->value != Tinvalid) {
196  std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
197  Tindex new_item = SmallStack::GetPool().Create();
198  if (new_item != Tmax_size) {
199  PooledSmallStack &pushed = SmallStack::GetPool().Get(new_item);
200  pushed.value = this->value;
201  pushed.next = this->next;
202  pushed.branch_count = 0;
203  this->next = new_item;
204  }
205  }
206  this->value = item;
207  }
208 
213  inline Titem Pop()
214  {
215  Titem ret = this->value;
216  if (this->next == Tmax_size) {
217  this->value = Tinvalid;
218  } else {
219  std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
220  PooledSmallStack &popped = SmallStack::GetPool().Get(this->next);
221  this->value = popped.value;
222  if (popped.branch_count == 0) {
223  SmallStack::GetPool().Destroy(this->next);
224  } else {
225  --popped.branch_count;
226  /* We can't use Branch() here as we already have the mutex.*/
227  if (popped.next != Tmax_size) {
228  ++(SmallStack::GetPool().Get(popped.next).branch_count);
229  }
230  }
231  /* Accessing popped here is no problem as the pool will only set
232  * the validity flag, not actually delete the item, on Destroy().
233  * It's impossible for another thread to acquire the same item in
234  * the mean time because of the mutex. */
235  this->next = popped.next;
236  }
237  return ret;
238  }
239 
244  inline bool IsEmpty() const
245  {
246  return this->value == Tinvalid && this->next == Tmax_size;
247  }
248 
254  inline bool Contains(const Titem &item) const
255  {
256  if (item == Tinvalid || item == this->value) return true;
257  if (this->next != Tmax_size) {
258  std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
259  const SmallStack *in_list = this;
260  do {
261  in_list = static_cast<const SmallStack *>(
262  static_cast<const Item *>(&SmallStack::GetPool().Get(in_list->next)));
263  if (in_list->value == item) return true;
264  } while (in_list->next != Tmax_size);
265  }
266  return false;
267  }
268 
269 protected:
270  static SmallStackPool &GetPool()
271  {
272  static SmallStackPool pool;
273  return pool;
274  }
275 
279  inline void Branch()
280  {
281  if (this->next != Tmax_size) {
282  std::lock_guard<std::mutex> lock(SmallStack::GetPool().GetMutex());
283  ++(SmallStack::GetPool().Get(this->next).branch_count);
284  }
285  }
286 };
287 
288 #endif
SmallStack
Minimal stack that uses a pool to avoid pointers.
Definition: smallstack_type.hpp:136
SmallStack::Pop
Titem Pop()
Pop an item from the stack.
Definition: smallstack_type.hpp:213
SmallStack::Push
void Push(const Titem &item)
Pushes a new item onto the stack if there is still space in the underlying pool.
Definition: smallstack_type.hpp:193
lock
std::mutex lock
synchronization for playback status fields
Definition: win32_m.cpp:34
SmallStack::PooledSmallStack::branch_count
Tindex branch_count
Number of branches in the tree structure this item is parent of.
Definition: smallstack_type.hpp:145
SmallStack::operator=
SmallStack & operator=(const SmallStack &other)
Shallow copy the stack, marking the first item as branched.
Definition: smallstack_type.hpp:176
smallvec_type.hpp
SmallStackItem::SmallStackItem
SmallStackItem(const Titem &value, Tindex next)
Create a new item.
Definition: smallstack_type.hpp:104
SimplePool::GetMutex
std::mutex & GetMutex()
Get the mutex.
Definition: smallstack_type.hpp:31
valid
uint8 valid
Bits indicating what variable is valid (for each bit, 0 is invalid, 1 is valid).
Definition: newgrf_station.cpp:248
SimplePool::Create
Tindex Create()
Create a new item and return its index.
Definition: smallstack_type.hpp:43
SmallStack::PooledSmallStack
SmallStack item that can be kept in a pool.
Definition: smallstack_type.hpp:144
SmallStackItem::next
Tindex next
Pool index of next item.
Definition: smallstack_type.hpp:96
SmallStack::SmallStack
SmallStack(const SmallStack &other)
Shallow copy the stack, marking the first item as branched.
Definition: smallstack_type.hpp:169
SmallStack::Branch
void Branch()
Create a branch in the pool if necessary.
Definition: smallstack_type.hpp:279
SmallStack::SmallStack
SmallStack(const Titem &value=Tinvalid)
Constructor for a stack with one or two items in it.
Definition: smallstack_type.hpp:154
SmallStackItem::value
Titem value
Value of current item.
Definition: smallstack_type.hpp:97
SimplePool::Destroy
void Destroy(Tindex index)
Destroy (or rather invalidate) the item at the given index.
Definition: smallstack_type.hpp:58
SimplePool::Get
Titem & Get(Tindex index)
Get the item at position index.
Definition: smallstack_type.hpp:37
SimplePool
A simplified pool which stores values instead of pointers and doesn't redefine operator new/delete.
Definition: smallstack_type.hpp:22
SmallStackItem
Base class for SmallStack.
Definition: smallstack_type.hpp:95
SmallStack::IsEmpty
bool IsEmpty() const
Check if the stack is empty.
Definition: smallstack_type.hpp:244
SmallStack::~SmallStack
~SmallStack()
Remove the head of stack and all other items members that are unique to it.
Definition: smallstack_type.hpp:159
SimplePool::SimplePoolPoolItem
Definition: smallstack_type.hpp:79
SmallStack::Contains
bool Contains(const Titem &item) const
Check if the given item is contained in the stack.
Definition: smallstack_type.hpp:254