OpenTTD Source  12.0-beta2
pool_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 POOL_TYPE_HPP
11 #define POOL_TYPE_HPP
12 
13 #include "smallvec_type.hpp"
14 #include "enum_type.hpp"
15 
17 enum PoolType {
18  PT_NONE = 0x00,
19  PT_NORMAL = 0x01,
20  PT_NCLIENT = 0x02,
21  PT_NADMIN = 0x04,
22  PT_DATA = 0x08,
23  PT_ALL = 0x0F,
24 };
26 
27 typedef std::vector<struct PoolBase *> PoolVector;
28 
30 struct PoolBase {
31  const PoolType type;
32 
37  static PoolVector *GetPools()
38  {
39  static PoolVector *pools = new PoolVector();
40  return pools;
41  }
42 
43  static void Clean(PoolType);
44 
49  PoolBase(PoolType pt) : type(pt)
50  {
51  PoolBase::GetPools()->push_back(this);
52  }
53 
54  virtual ~PoolBase();
55 
59  virtual void CleanPool() = 0;
60 
61 private:
66  PoolBase(const PoolBase &other);
67 };
68 
80 template <class Titem, typename Tindex, size_t Tgrowth_step, size_t Tmax_size, PoolType Tpool_type = PT_NORMAL, bool Tcache = false, bool Tzero = true>
81 struct Pool : PoolBase {
82  /* Ensure Tmax_size is within the bounds of Tindex. */
83  static_assert((uint64)(Tmax_size - 1) >> 8 * sizeof(Tindex) == 0);
84 
85  static constexpr size_t MAX_SIZE = Tmax_size;
86 
87  const char * const name;
88 
89  size_t size;
90  size_t first_free;
91  size_t first_unused;
92  size_t items;
93 #ifdef WITH_ASSERT
94  size_t checked;
95 #endif /* WITH_ASSERT */
96  bool cleaning;
97 
98  Titem **data;
99 
100  Pool(const char *name);
101  virtual void CleanPool();
102 
109  inline Titem *Get(size_t index)
110  {
111  assert(index < this->first_unused);
112  return this->data[index];
113  }
114 
120  inline bool IsValidID(size_t index)
121  {
122  return index < this->first_unused && this->Get(index) != nullptr;
123  }
124 
130  inline bool CanAllocate(size_t n = 1)
131  {
132  bool ret = this->items <= Tmax_size - n;
133 #ifdef WITH_ASSERT
134  this->checked = ret ? n : 0;
135 #endif /* WITH_ASSERT */
136  return ret;
137  }
138 
143  template <class T>
144  struct PoolIterator {
145  typedef T value_type;
146  typedef T* pointer;
147  typedef T& reference;
148  typedef size_t difference_type;
149  typedef std::forward_iterator_tag iterator_category;
150 
151  explicit PoolIterator(size_t index) : index(index)
152  {
153  this->ValidateIndex();
154  };
155 
156  bool operator==(const PoolIterator &other) const { return this->index == other.index; }
157  bool operator!=(const PoolIterator &other) const { return !(*this == other); }
158  T * operator*() const { return T::Get(this->index); }
159  PoolIterator & operator++() { this->index++; this->ValidateIndex(); return *this; }
160 
161  private:
162  size_t index;
163  void ValidateIndex()
164  {
165  while (this->index < T::GetPoolSize() && !(T::IsValidID(this->index))) this->index++;
166  if (this->index >= T::GetPoolSize()) this->index = T::Pool::MAX_SIZE;
167  }
168  };
169 
170  /*
171  * Iterable ensemble of all valid T
172  * @tparam T Type of the class/struct that is going to be iterated
173  */
174  template <class T>
175  struct IterateWrapper {
176  size_t from;
177  IterateWrapper(size_t from = 0) : from(from) {}
178  PoolIterator<T> begin() { return PoolIterator<T>(this->from); }
179  PoolIterator<T> end() { return PoolIterator<T>(T::Pool::MAX_SIZE); }
180  bool empty() { return this->begin() == this->end(); }
181  };
182 
187  template <class T, class F>
189  typedef T value_type;
190  typedef T* pointer;
191  typedef T& reference;
192  typedef size_t difference_type;
193  typedef std::forward_iterator_tag iterator_category;
194 
195  explicit PoolIteratorFiltered(size_t index, F filter) : index(index), filter(filter)
196  {
197  this->ValidateIndex();
198  };
199 
200  bool operator==(const PoolIteratorFiltered &other) const { return this->index == other.index; }
201  bool operator!=(const PoolIteratorFiltered &other) const { return !(*this == other); }
202  T * operator*() const { return T::Get(this->index); }
203  PoolIteratorFiltered & operator++() { this->index++; this->ValidateIndex(); return *this; }
204 
205  private:
206  size_t index;
207  F filter;
208  void ValidateIndex()
209  {
210  while (this->index < T::GetPoolSize() && !(T::IsValidID(this->index) && this->filter(this->index))) this->index++;
211  if (this->index >= T::GetPoolSize()) this->index = T::Pool::MAX_SIZE;
212  }
213  };
214 
215  /*
216  * Iterable ensemble of all valid T
217  * @tparam T Type of the class/struct that is going to be iterated
218  */
219  template <class T, class F>
221  size_t from;
222  F filter;
223  IterateWrapperFiltered(size_t from, F filter) : from(from), filter(filter) {}
224  PoolIteratorFiltered<T, F> begin() { return PoolIteratorFiltered<T, F>(this->from, this->filter); }
225  PoolIteratorFiltered<T, F> end() { return PoolIteratorFiltered<T, F>(T::Pool::MAX_SIZE, this->filter); }
226  bool empty() { return this->begin() == this->end(); }
227  };
228 
233  template <struct Pool<Titem, Tindex, Tgrowth_step, Tmax_size, Tpool_type, Tcache, Tzero> *Tpool>
234  struct PoolItem {
235  Tindex index;
236 
238  typedef struct Pool<Titem, Tindex, Tgrowth_step, Tmax_size, Tpool_type, Tcache, Tzero> Pool;
239 
246  inline void *operator new(size_t size)
247  {
248  return Tpool->GetNew(size);
249  }
250 
256  inline void operator delete(void *p)
257  {
258  if (p == nullptr) return;
259  Titem *pn = (Titem *)p;
260  assert(pn == Tpool->Get(pn->index));
261  Tpool->FreeItem(pn->index);
262  }
263 
272  inline void *operator new(size_t size, size_t index)
273  {
274  return Tpool->GetNew(size, index);
275  }
276 
285  inline void *operator new(size_t size, void *ptr)
286  {
287  for (size_t i = 0; i < Tpool->first_unused; i++) {
288  /* Don't allow creating new objects over existing.
289  * Even if we called the destructor and reused this memory,
290  * we don't know whether 'size' and size of currently allocated
291  * memory are the same (because of possible inheritance).
292  * Use { size_t index = item->index; delete item; new (index) item; }
293  * instead to make sure destructor is called and no memory leaks. */
294  assert(ptr != Tpool->data[i]);
295  }
296  return ptr;
297  }
298 
299 
307  static inline bool CanAllocateItem(size_t n = 1)
308  {
309  return Tpool->CanAllocate(n);
310  }
311 
316  static inline bool CleaningPool()
317  {
318  return Tpool->cleaning;
319  }
320 
326  static inline bool IsValidID(size_t index)
327  {
328  return Tpool->IsValidID(index);
329  }
330 
337  static inline Titem *Get(size_t index)
338  {
339  return Tpool->Get(index);
340  }
341 
348  static inline Titem *GetIfValid(size_t index)
349  {
350  return index < Tpool->first_unused ? Tpool->Get(index) : nullptr;
351  }
352 
358  static inline size_t GetPoolSize()
359  {
360  return Tpool->first_unused;
361  }
362 
367  static inline size_t GetNumItems()
368  {
369  return Tpool->items;
370  }
371 
379  static inline void PostDestructor(size_t index) { }
380 
386  static Pool::IterateWrapper<Titem> Iterate(size_t from = 0) { return Pool::IterateWrapper<Titem>(from); }
387  };
388 
389 private:
390  static const size_t NO_FREE_ITEM = MAX_UVALUE(size_t);
391 
396  struct AllocCache {
399  };
400 
403 
404  void *AllocateItem(size_t size, size_t index);
405  void ResizeFor(size_t index);
406  size_t FindFirstFree();
407 
408  void *GetNew(size_t size);
409  void *GetNew(size_t size, size_t index);
410 
411  void FreeItem(size_t index);
412 };
413 
414 #endif /* POOL_TYPE_HPP */
Pool::IsValidID
bool IsValidID(size_t index)
Tests whether given index can be used to get valid (non-nullptr) Titem.
Definition: pool_type.hpp:120
PoolVector
std::vector< struct PoolBase * > PoolVector
Vector of pointers to PoolBase.
Definition: pool_type.hpp:27
Pool::PoolItem::Get
static Titem * Get(size_t index)
Returns Titem with given index.
Definition: pool_type.hpp:337
Pool::PoolItem::GetIfValid
static Titem * GetIfValid(size_t index)
Returns Titem with given index.
Definition: pool_type.hpp:348
Pool::CleanPool
virtual void CleanPool()
Virtual method that deletes all items in the pool.
Pool::AllocCache
Helper struct to cache 'freed' PoolItems so we do not need to allocate them again.
Definition: pool_type.hpp:396
smallvec_type.hpp
Pool::PoolItem::index
Tindex index
Index of this pool item.
Definition: pool_type.hpp:235
Pool::IterateWrapperFiltered
Definition: pool_type.hpp:220
Pool::PoolIterator
Iterator to iterate all valid T of a pool.
Definition: pool_type.hpp:144
Pool::PoolItem::PostDestructor
static void PostDestructor(size_t index)
Dummy function called after destructor of each member.
Definition: pool_type.hpp:379
Pool::MAX_SIZE
static constexpr size_t MAX_SIZE
Make template parameter accessible from outside.
Definition: pool_type.hpp:85
PoolBase
Base class for base of all pools.
Definition: pool_type.hpp:30
Pool::PoolItem::GetPoolSize
static size_t GetPoolSize()
Returns first unused index.
Definition: pool_type.hpp:358
Pool::alloc_cache
AllocCache * alloc_cache
Cache of freed pointers.
Definition: pool_type.hpp:402
Pool::items
size_t items
Number of used indexes (non-nullptr)
Definition: pool_type.hpp:92
Pool::data
Titem ** data
Pointer to array of pointers to Titem.
Definition: pool_type.hpp:98
PoolType
PoolType
Various types of a pool.
Definition: pool_type.hpp:17
Pool::IterateWrapper
Definition: pool_type.hpp:175
Pool::cleaning
bool cleaning
True if cleaning pool (deleting all items)
Definition: pool_type.hpp:96
PT_NADMIN
@ PT_NADMIN
Network admin pool.
Definition: pool_type.hpp:21
PT_NONE
@ PT_NONE
No pool is selected.
Definition: pool_type.hpp:18
Pool::PoolIteratorFiltered
Iterator to iterate all valid T of a pool.
Definition: pool_type.hpp:188
Pool::NO_FREE_ITEM
static const size_t NO_FREE_ITEM
Constant to indicate we can't allocate any more items.
Definition: pool_type.hpp:390
Pool::Get
Titem * Get(size_t index)
Returns Titem with given index.
Definition: pool_type.hpp:109
PT_NCLIENT
@ PT_NCLIENT
Network client pools.
Definition: pool_type.hpp:20
Pool::first_free
size_t first_free
No item with index lower than this is free (doesn't say anything about this one!)
Definition: pool_type.hpp:90
PT_ALL
@ PT_ALL
All pool types.
Definition: pool_type.hpp:23
Pool::PoolItem::Iterate
static Pool::IterateWrapper< Titem > Iterate(size_t from=0)
Returns an iterable ensemble of all valid Titem.
Definition: pool_type.hpp:386
PT_NORMAL
@ PT_NORMAL
Normal pool containing game objects.
Definition: pool_type.hpp:19
Pool
Base class for all pools.
Definition: pool_type.hpp:81
Pool::size
size_t size
Current allocated size.
Definition: pool_type.hpp:89
PT_DATA
@ PT_DATA
NewGRF or other data, that is not reset together with normal pools.
Definition: pool_type.hpp:22
Pool::PoolItem::GetNumItems
static size_t GetNumItems()
Returns number of valid items in the pool.
Definition: pool_type.hpp:367
Pool::AllocCache::next
AllocCache * next
The next in our 'cache'.
Definition: pool_type.hpp:398
Pool::PoolItem::CleaningPool
static bool CleaningPool()
Returns current state of pool cleaning - yes or no.
Definition: pool_type.hpp:316
Pool::PoolItem::CanAllocateItem
static bool CanAllocateItem(size_t n=1)
Helper functions so we can use PoolItem::Function() instead of _poolitem_pool.Function()
Definition: pool_type.hpp:307
MAX_UVALUE
#define MAX_UVALUE(type)
The largest value that can be entered in a variable.
Definition: stdafx.h:469
enum_type.hpp
DECLARE_ENUM_AS_BIT_SET
DECLARE_ENUM_AS_BIT_SET(GenderEthnicity) enum CompanyManagerFaceVariable
Bitgroups of the CompanyManagerFace variable.
Definition: company_manager_face.h:29
PoolBase::PoolBase
PoolBase(PoolType pt)
Constructor registers this object in the pool vector.
Definition: pool_type.hpp:49
Pool::name
const char *const name
Name of this pool.
Definition: pool_type.hpp:87
Pool::first_unused
size_t first_unused
This and all higher indexes are free (doesn't say anything about first_unused-1 !)
Definition: pool_type.hpp:91
Pool::PoolItem::IsValidID
static bool IsValidID(size_t index)
Tests whether given index can be used to get valid (non-nullptr) Titem.
Definition: pool_type.hpp:326
PoolBase::type
const PoolType type
Type of this pool.
Definition: pool_type.hpp:31
Pool::PoolItem
Base class for all PoolItems.
Definition: pool_type.hpp:234
PoolBase::GetPools
static PoolVector * GetPools()
Function used to access the vector of all pools.
Definition: pool_type.hpp:37
Pool::CanAllocate
bool CanAllocate(size_t n=1)
Tests whether we can allocate 'n' items.
Definition: pool_type.hpp:130