1//============================================================================
2//
3// SSSS tt lll lll
4// SS SS tt ll ll
5// SS tttttt eeee ll ll aaaa
6// SSSS tt ee ee ll ll aa
7// SS tt eeeeee ll ll aaaaa -- "An Atari 2600 VCS Emulator"
8// SS SS tt ee ll ll aa aa
9// SSSS ttt eeeee llll llll aaaaa
10//
11// Copyright (c) 1995-2019 by Bradford W. Mott, Stephen Anthony
12// and the Stella Team
13//
14// See the file "License.txt" for information on usage and redistribution of
15// this file, and for a DISCLAIMER OF ALL WARRANTIES.
16//============================================================================
17
18#ifndef LINKED_OBJECT_POOL_HXX
19#define LINKED_OBJECT_POOL_HXX
20
21#include <list>
22#include "bspf.hxx"
23
24/**
25 A fixed-size object-pool based doubly-linked list that makes use of
26 multiple STL lists, to reduce frequent (de)allocations.
27
28 This structure can be used as either a stack or queue, but also allows
29 for removal at any location in the list.
30
31 There are two internal lists; one stores active nodes, and the other
32 stores pool nodes that have been 'deleted' from the active list (note
33 that no actual deletion takes place; nodes are simply moved from one list
34 to another). Similarly, when a new node is added to the active list, it
35 is simply moved from the pool list to the active list.
36
37 In all cases, the variable 'myCurrent' is updated to point to the
38 current node.
39
40 NOTE: You must always call 'currentIsValid()' before calling 'current()',
41 to make sure that the return value is a valid reference.
42
43 In the case of methods which wrap the C++ 'splice()' method, the
44 semantics of splice are followed wrt invalid/out-of-range/etc
45 iterators. See the applicable C++ STL documentation for such
46 behaviour.
47
48 @author Stephen Anthony
49*/
50namespace Common {
51
52template <class T, uInt32 CAPACITY = 100>
53class LinkedObjectPool
54{
55 public:
56 using iter = typename std::list<T>::iterator;
57 using const_iter = typename std::list<T>::const_iterator;
58
59 /*
60 Create a pool of size CAPACITY; the active list starts out empty.
61 */
62 LinkedObjectPool<T, CAPACITY>() : myCurrent(myList.end()), myCapacity(0) {
63 resize(CAPACITY);
64 }
65
66 /**
67 Return node data that the 'current' iterator points to.
68 Note that this returns a valid value only in the case where the list
69 is non-empty (at least one node has been added to the active list).
70
71 Make sure to call 'currentIsValid()' before accessing this method.
72 */
73 T& current() const { return *myCurrent; }
74
75 /**
76 Returns current's position in the list
77
78 SLOW, but only required for messages
79 */
80 uInt32 currentIdx() const {
81 if(empty())
82 return 0;
83
84 iter it = myCurrent;
85 uInt32 idx = 1;
86
87 while(it-- != myList.begin()) ++idx;
88 return idx;
89 }
90
91 /**
92 Does the 'current' iterator point to a valid node in the active list?
93 This must be called before 'current()' is called.
94 */
95 bool currentIsValid() const { return myCurrent != myList.end(); }
96
97 /**
98 Advance 'current' iterator to previous position in the active list.
99 If we go past the beginning, it is reset to one past the end (indicates nullptr).
100 */
101 void moveToPrevious() {
102 if(currentIsValid())
103 myCurrent = myCurrent == myList.begin() ? myList.end() : std::prev(myCurrent, 1);
104 }
105
106 /**
107 Advance 'current' iterator to next position in the active list.
108 If we go past the last node, it will point to one past the end (indicates nullptr).
109 */
110 void moveToNext() {
111 if(currentIsValid())
112 myCurrent = std::next(myCurrent, 1);
113 }
114
115 /**
116 Advance 'current' iterator to first position in the active list.
117 */
118 void moveToFirst() {
119 if(currentIsValid())
120 myCurrent = myList.begin();
121 }
122
123 /**
124 Advance 'current' iterator to last position in the active list.
125 */
126 void moveToLast() {
127 if(currentIsValid())
128 myCurrent = std::prev(myList.end(), 1);
129 }
130
131 /**
132 Return an iterator to the first node in the active list.
133 */
134 const_iter first() const { return myList.begin(); }
135
136 /**
137 Return an iterator to the last node in the active list.
138 */
139 const_iter last() const { return std::prev(myList.end(), 1); }
140
141 /**
142 Return an iterator to the previous node of 'i' in the active list.
143 */
144 const_iter previous(const_iter i) const { return std::prev(i, 1); }
145
146 /**
147 Return an iterator to the next node to 'current' in the active list.
148 */
149 const_iter next(const_iter i) const { return std::next(i, 1); }
150
151 /**
152 Canonical iterators from C++ STL.
153 */
154 const_iter cbegin() const { return myList.cbegin(); }
155 const_iter cend() const { return myList.cend(); }
156
157 /**
158 Answer whether 'current' is at the specified iterator.
159 */
160 bool atFirst() const { return myCurrent == first(); }
161 bool atLast() const { return myCurrent == last(); }
162
163 /**
164 Add a new node at the beginning of the active list, and update 'current'
165 to point to that node.
166 */
167 void addFirst() {
168 myList.splice(myList.begin(), myPool, myPool.begin());
169 myCurrent = myList.begin();
170 }
171
172 /**
173 Add a new node at the end of the active list, and update 'current'
174 to point to that node.
175 */
176 void addLast() {
177 myList.splice(myList.end(), myPool, myPool.begin());
178 myCurrent = std::prev(myList.end(), 1);
179 }
180
181 /**
182 Remove the first node of the active list, updating 'current' if it
183 happens to be the one removed.
184 */
185 void removeFirst() {
186 const_iter i = myList.cbegin();
187 myPool.splice(myPool.end(), myList, i);
188 if(myCurrent == i) // did we just invalidate 'current'
189 moveToNext(); // if so, move to the next node
190 }
191
192 /**
193 Remove the last node of the active list, updating 'current' if it
194 happens to be the one removed.
195 */
196 void removeLast() {
197 const_iter i = std::prev(myList.end(), 1);
198 myPool.splice(myPool.end(), myList, i);
199 if(myCurrent == i) // did we just invalidate 'current'
200 moveToPrevious(); // if so, move to the previous node
201 }
202
203 /**
204 Remove a single element from the active list at position of the iterator.
205 */
206 void remove(const_iter i) {
207 myPool.splice(myPool.end(), myList, i);
208 }
209
210 /**
211 Remove a single element from the active list by index, offset from
212 the beginning of the list. (ie, '0' means first element, '1' is second,
213 and so on).
214 */
215 void remove(uInt32 index) {
216 myPool.splice(myPool.end(), myList, std::next(myList.begin(), index));
217 }
218
219 /**
220 Remove range of elements from the beginning of the active list to
221 the 'current' node.
222 */
223 void removeToFirst() {
224 myPool.splice(myPool.end(), myList, myList.begin(), myCurrent);
225 }
226
227 /**
228 Remove range of elements from the node after 'current' to the end of the
229 active list.
230 */
231 void removeToLast() {
232 myPool.splice(myPool.end(), myList, std::next(myCurrent, 1), myList.end());
233 }
234
235 /**
236 Resize the pool to specified size, invalidating the list in the process
237 (ie, the list essentially becomes empty again).
238 */
239 void resize(uInt32 capacity) {
240 if(myCapacity != capacity) // only resize when necessary
241 {
242 myList.clear(); myPool.clear();
243 myCurrent = myList.end();
244 myCapacity = capacity;
245
246 for(uInt32 i = 0; i < myCapacity; ++i)
247 myPool.emplace_back(T());
248 }
249 }
250
251 /**
252 Erase entire contents of active list.
253 */
254 void clear() {
255 myPool.splice(myPool.end(), myList, myList.begin(), myList.end());
256 myCurrent = myList.end();
257 }
258
259 uInt32 capacity() const { return myCapacity; }
260
261 uInt32 size() const { return uInt32(myList.size()); }
262 bool empty() const { return size() == 0; }
263 bool full() const { return size() >= capacity(); }
264
265 friend ostream& operator<<(ostream& os, const LinkedObjectPool<T>& p) {
266 for(const auto& i: p.myList)
267 os << i << (p.current() == i ? "* " : " ");
268 return os;
269 }
270
271 private:
272 std::list<T> myList, myPool;
273
274 // Current position in the active list (end() indicates an invalid position)
275 iter myCurrent;
276
277 // Total capacity of the pool
278 uInt32 myCapacity;
279
280 private:
281 // Following constructors and assignment operators not supported
282 LinkedObjectPool(const LinkedObjectPool&) = delete;
283 LinkedObjectPool(LinkedObjectPool&&) = delete;
284 LinkedObjectPool& operator=(const LinkedObjectPool&) = delete;
285 LinkedObjectPool& operator=(LinkedObjectPool&&) = delete;
286};
287
288} // Namespace Common
289
290#endif
291