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 "../thread/thread.h"
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), mutex(ThreadMutex::New()) {}
27  inline ~SimplePool() { delete this->mutex; }
28 
34  inline ThreadMutex *GetMutex() { return this->mutex; }
35 
40  inline Titem &Get(Tindex index) { return this->data[index]; }
41 
46  inline Tindex Create()
47  {
48  Tindex index = this->FindFirstFree();
49  if (index < Tmax_size) {
50  this->data[index].valid = true;
51  this->first_free = index + 1;
52  this->first_unused = max(this->first_unused, this->first_free);
53  }
54  return index;
55  }
56 
61  inline void Destroy(Tindex index)
62  {
63  this->data[index].valid = false;
64  this->first_free = min(this->first_free, index);
65  }
66 
67 private:
68 
69  inline Tindex FindFirstFree()
70  {
71  Tindex index = this->first_free;
72  for (; index < this->first_unused; index++) {
73  if (!this->data[index].valid) return index;
74  }
75 
76  if (index >= this->data.Length() && index < Tmax_size) {
77  this->data.Resize(index + 1);
78  }
79  return index;
80  }
81 
82  struct SimplePoolPoolItem : public Titem {
83  bool valid;
84  };
85 
86  Tindex first_unused;
87  Tindex first_free;
88 
89  ThreadMutex *mutex;
91 };
92 
97 template <typename Titem, typename Tindex>
99  Tindex next;
100  Titem value;
101 
107  inline SmallStackItem(const Titem &value, Tindex next) :
108  next(next), value(value) {}
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  ThreadMutexLocker lock(_pool.GetMutex());
199  Tindex new_item = _pool.Create();
200  if (new_item != Tmax_size) {
201  PooledSmallStack &pushed = _pool.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  ThreadMutexLocker lock(_pool.GetMutex());
222  PooledSmallStack &popped = _pool.Get(this->next);
223  this->value = popped.value;
224  if (popped.branch_count == 0) {
225  _pool.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  ++(_pool.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  ThreadMutexLocker lock(_pool.GetMutex());
261  const SmallStack *in_list = this;
262  do {
263  in_list = static_cast<const SmallStack *>(
264  static_cast<const Item *>(&_pool.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 _pool;
273 
277  inline void Branch()
278  {
279  if (this->next != Tmax_size) {
280  ThreadMutexLocker lock(_pool.GetMutex());
281  ++(_pool.Get(this->next).branch_count);
282  }
283  }
284 };
285 
286 #endif
Simple mutex locker to keep a mutex locked until the locker goes out of scope.
Definition: thread.h:101
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...
Cross-platform Mutex.
Definition: thread.h:56
Simple vector template class.
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.
A simplified pool which stores values instead of pointers and doesn&#39;t redefine operator new/delete...
static ThreadMutex * New()
Create a new mutex.
Definition: thread_none.cpp:32
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.
Tindex branch_count
Number of branches in the tree structure this item is parent of.
ThreadMutex * GetMutex()
Get the mutex.
SmallStack(const Titem &value=Tinvalid)
Constructor for a stack with one or two items in it.