openMSX
ObjectPool.hh
Go to the documentation of this file.
1 #ifndef OBJECTPOOL_HH
2 #define OBJECTPOOL_HH
3 
4 #include <array>
5 #include <cstdint>
6 #include <memory>
7 #include <vector>
8 #include "unreachable.hh"
9 #include "xrange.hh"
10 
11 // ObjectPool
12 //
13 // This is a bit like a traditional pool-allocator, but with these differences:
14 // - Instead of only allocating and deallocating memory, this class also
15 // constructs/destructs the objects contained in the pool. (But see the
16 // remark below about destroying the ObjectPool itself).
17 // - The objects in this pool are not accessed via a pointer but instead via an
18 // index. That is inserting a object into this pool returns an index. And that
19 // index can later be used to retrieve the actual object or to remove the
20 // object again. (As an optimization the insert operation additionally also
21 // returns a pointer to the object).
22 //
23 // The choice of identifying objects via a (32-bit) index rather than via a
24 // pointer involves some trade-offs:
25 // - On a 64-bit system, storing (many) indices only takes half as much space
26 // as storing pointers.
27 // - Accessing an object via an index is a bit slower than via a pointer.
28 // - Removing an object (via an index) is about the same speed as accessing the
29 // object. Removing via pointer is not possible.
30 //
31 // Objects in this pool have stable addresses. IOW once you retrieve a pointer
32 // to an object that pointer remains valid. Also when more elements are inserted
33 // later. Even if (internally) the pool needs to allocate more memory.
34 //
35 // Memory is allocated in chunks (in the current implementation a chunk has
36 // room for 256 objects). Typically two objects that are inserted one after the
37 // other will be next to each other in memory (good for cache-locality). Though
38 // this is not a guarantee. When objects are removed, those free locations are
39 // re-filled first before allocating new memory.
40 //
41 // Inserting an object is done via the emplace() function. This will in-place
42 // constructs the object in the pool. So you cannot request uninitialized
43 // memory from the pool. Removing an object from the pool will call the
44 // destructor on that object. However when the ObjectPool itself is destructed
45 // it will NOT destruct all objects that are still present in the pool.
46 // Depending on the type of object and the state of your program this may or
47 // may not be a problem. E.g. maybe the object has a trivial destructor, or
48 // maybe it's fine to leak memory on exit.
49 //
50 // It's not possible to loop over all the objects that are present in the pool.
51 
52 template<typename T>
54 {
55 public:
56  using Index = uint32_t;
57 
58  struct EmplaceResult {
60  T* ptr;
61  };
62 
63 private:
64  union Element {
65  Element() {}
66  ~Element() {}
67 
68  Index next;
69  T t;
70  };
71  using Element256 = std::array<Element, 256>;
72 
73 public:
74  template<typename... Args>
75  [[nodiscard]] EmplaceResult emplace(Args&& ...args) {
76  Index idx;
77  if (free != Index(-1)) {
78  idx = free;
79  free = get(idx).next;
80  } else {
81  if (cntr == 0) {
82  pool.push_back(std::make_unique<Element256>());
83  }
84  idx = Index(((pool.size() - 1) << 8) + cntr);
85  ++cntr;
86  }
87  T* ptr = &get(idx).t;
88  new(ptr) T(std::forward<Args>(args)...);
89  return {idx, ptr};
90  }
91 
92  [[nodiscard]] const T& operator[](Index idx) const { return get(idx).t; }
93  [[nodiscard]] T& operator[](Index idx) { return get(idx).t; }
94 
95  void remove(Index idx) {
96  auto& elem = get(idx);
97  elem.t.~T();
98  elem.next = free;
99  free = idx;
100  }
101 
102  void remove(const T* ptr) {
103  remove(ptr2Index(ptr));
104  }
105 
106  Index ptr2Index(const T* ptr) const {
107  for (auto i : xrange(pool.size())) {
108  const auto& elem256 = *pool[i];
109  const T* begin = &elem256[0].t;
110  const T* end = begin + 256;
111  if ((begin <= ptr) && (ptr < end)) {
112  return Index((i << 8) + (ptr - begin));
113  }
114  }
115  UNREACHABLE;
116  }
117 
118  // for unittest
119  [[nodiscard]] Index capacity() const {
120  return 256 * pool.size();
121  }
122 
123 private:
124  [[nodiscard]] const Element& get(Index idx) const { return (*pool[idx >> 8])[idx & 255]; }
125  [[nodiscard]] Element& get(Index idx) { return (*pool[idx >> 8])[idx & 255]; }
126 
127 private:
128  std::vector<std::unique_ptr<Element256>> pool;
129  Index free = Index(-1);
130  uint8_t cntr = 0;
131 };
132 
133 #endif
TclObject t
void remove(const T *ptr)
Definition: ObjectPool.hh:102
uint32_t Index
Definition: ObjectPool.hh:56
Index capacity() const
Definition: ObjectPool.hh:119
Index ptr2Index(const T *ptr) const
Definition: ObjectPool.hh:106
const T & operator[](Index idx) const
Definition: ObjectPool.hh:92
void remove(Index idx)
Definition: ObjectPool.hh:95
T & operator[](Index idx)
Definition: ObjectPool.hh:93
EmplaceResult emplace(Args &&...args)
Definition: ObjectPool.hh:75
uint32_t next(octet_iterator &it, octet_iterator end)
#define UNREACHABLE
Definition: unreachable.hh:38
constexpr auto xrange(T e)
Definition: xrange.hh:155
constexpr auto begin(const zstring_view &x)
Definition: zstring_view.hh:83
constexpr auto end(const zstring_view &x)
Definition: zstring_view.hh:84