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