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
52template<typename T>
54{
55public:
56 using Index = uint32_t;
57
60 T* ptr;
61 };
62
63private:
64 union Element {
65 Element() {}
66 ~Element() {}
67
68 Index next;
69 T t;
70 };
71 using Element256 = std::array<Element, 256>;
72
73public:
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 }
116 }
117
118 // for unittest
119 [[nodiscard]] Index capacity() const {
120 return 256 * pool.size();
121 }
122
123private:
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
127private:
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
void remove(Index idx)
Definition: ObjectPool.hh:95
T & operator[](Index idx)
Definition: ObjectPool.hh:93
const T & operator[](Index idx) const
Definition: ObjectPool.hh:92
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:133
constexpr auto begin(const zstring_view &x)
constexpr auto end(const zstring_view &x)