Line data Source code
1 : /*
2 : * Copyright 2012 Google Inc.
3 : *
4 : * Use of this source code is governed by a BSD-style license that can be
5 : * found in the LICENSE file.
6 : */
7 :
8 : #ifndef SkTLList_DEFINED
9 : #define SkTLList_DEFINED
10 :
11 : #include "SkTInternalLList.h"
12 :
13 : #include "SkMalloc.h"
14 : #include "SkTypes.h"
15 : #include <utility>
16 :
17 : /** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the
18 : the list creates the objects and they are deleted upon removal. This class block-allocates
19 : space for entries based on a param passed to the constructor.
20 :
21 : Elements of the list can be constructed in place using the following macros:
22 : SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args)
23 : SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args)
24 : where list is a SkTLList<type_name>*, location is an iterator, and args is the paren-surrounded
25 : constructor arguments for type_name. These macros behave like addBefore() and addAfter().
26 :
27 : allocCnt is the number of objects to allocate as a group. In the worst case fragmentation
28 : each object is using the space required for allocCnt unfragmented objects.
29 : */
30 : template <typename T, unsigned int N> class SkTLList : SkNoncopyable {
31 : private:
32 : struct Block;
33 0 : struct Node {
34 : char fObj[sizeof(T)];
35 : SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node);
36 : Block* fBlock; // owning block.
37 : };
38 : typedef SkTInternalLList<Node> NodeList;
39 :
40 : public:
41 : class Iter;
42 :
43 : // Having fCount initialized to -1 indicates that the first time we attempt to grab a free node
44 : // all the nodes in the pre-allocated first block need to be inserted into the free list. This
45 : // allows us to skip that loop in instances when the list is never populated.
46 0 : SkTLList() : fCount(-1) {}
47 :
48 0 : ~SkTLList() {
49 0 : this->validate();
50 0 : typename NodeList::Iter iter;
51 0 : Node* node = iter.init(fList, Iter::kHead_IterStart);
52 0 : while (node) {
53 0 : SkTCast<T*>(node->fObj)->~T();
54 0 : Block* block = node->fBlock;
55 0 : node = iter.next();
56 0 : if (0 == --block->fNodesInUse) {
57 0 : for (unsigned int i = 0; i < N; ++i) {
58 : block->fNodes[i].~Node();
59 : }
60 0 : if (block != &fFirstBlock) {
61 0 : sk_free(block);
62 : }
63 : }
64 : }
65 0 : }
66 :
67 : /** Adds a new element to the list at the head. */
68 0 : template <typename... Args> T* addToHead(Args&&... args) {
69 0 : this->validate();
70 0 : Node* node = this->createNode();
71 0 : fList.addToHead(node);
72 0 : this->validate();
73 0 : return new (node->fObj) T(std::forward<Args>(args)...);
74 : }
75 :
76 : /** Adds a new element to the list at the tail. */
77 0 : template <typename... Args> T* addToTail(Args&&... args) {
78 0 : this->validate();
79 0 : Node* node = this->createNode();
80 0 : fList.addToTail(node);
81 0 : this->validate();
82 0 : return new (node->fObj) T(std::forward<Args>(args)...);
83 : }
84 :
85 : /** Adds a new element to the list before the location indicated by the iterator. If the
86 : iterator refers to a nullptr location then the new element is added at the tail */
87 : template <typename... Args> T* addBefore(Iter location, Args&&... args) {
88 : this->validate();
89 : Node* node = this->createNode();
90 : fList.addBefore(node, location.getNode());
91 : this->validate();
92 : return new (node->fObj) T(std::forward<Args>(args)...);
93 : }
94 :
95 : /** Adds a new element to the list after the location indicated by the iterator. If the
96 : iterator refers to a nullptr location then the new element is added at the head */
97 : template <typename... Args> T* addAfter(Iter location, Args&&... args) {
98 : this->validate();
99 : Node* node = this->createNode();
100 : fList.addAfter(node, location.getNode());
101 : this->validate();
102 : return new (node->fObj) T(std::forward<Args>(args)...);
103 : }
104 :
105 : /** Convenience methods for getting an iterator initialized to the head/tail of the list. */
106 0 : Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); }
107 : Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); }
108 :
109 0 : T* head() { return Iter(*this, Iter::kHead_IterStart).get(); }
110 : T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); }
111 0 : const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); }
112 : const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); }
113 :
114 0 : void popHead() {
115 0 : this->validate();
116 0 : Node* node = fList.head();
117 0 : if (node) {
118 0 : this->removeNode(node);
119 : }
120 0 : this->validate();
121 0 : }
122 :
123 : void popTail() {
124 : this->validate();
125 : Node* node = fList.head();
126 : if (node) {
127 : this->removeNode(node);
128 : }
129 : this->validate();
130 : }
131 :
132 0 : void remove(T* t) {
133 0 : this->validate();
134 0 : Node* node = reinterpret_cast<Node*>(t);
135 0 : SkASSERT(reinterpret_cast<T*>(node->fObj) == t);
136 0 : this->removeNode(node);
137 0 : this->validate();
138 0 : }
139 :
140 0 : void reset() {
141 0 : this->validate();
142 0 : Iter iter(*this, Iter::kHead_IterStart);
143 0 : while (iter.get()) {
144 0 : Iter next = iter;
145 0 : next.next();
146 0 : this->remove(iter.get());
147 0 : iter = next;
148 : }
149 0 : SkASSERT(0 == fCount || -1 == fCount);
150 0 : this->validate();
151 0 : }
152 :
153 0 : int count() const { return SkTMax(fCount ,0); }
154 0 : bool isEmpty() const { this->validate(); return 0 == fCount || -1 == fCount; }
155 :
156 : bool operator== (const SkTLList& list) const {
157 : if (this == &list) {
158 : return true;
159 : }
160 : // Call count() rather than use fCount because an empty list may have fCount = 0 or -1.
161 : if (this->count() != list.count()) {
162 : return false;
163 : }
164 : for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart);
165 : a.get();
166 : a.next(), b.next()) {
167 : SkASSERT(b.get()); // already checked that counts match.
168 : if (!(*a.get() == *b.get())) {
169 : return false;
170 : }
171 : }
172 : return true;
173 : }
174 : bool operator!= (const SkTLList& list) const { return !(*this == list); }
175 :
176 : /** The iterator becomes invalid if the element it refers to is removed from the list. */
177 0 : class Iter : private NodeList::Iter {
178 : private:
179 : typedef typename NodeList::Iter INHERITED;
180 :
181 : public:
182 : typedef typename INHERITED::IterStart IterStart;
183 : //!< Start the iterator at the head of the list.
184 : static const IterStart kHead_IterStart = INHERITED::kHead_IterStart;
185 : //!< Start the iterator at the tail of the list.
186 : static const IterStart kTail_IterStart = INHERITED::kTail_IterStart;
187 :
188 : Iter() {}
189 :
190 0 : Iter(const SkTLList& list, IterStart start = kHead_IterStart) {
191 0 : INHERITED::init(list.fList, start);
192 0 : }
193 :
194 : T* init(const SkTLList& list, IterStart start = kHead_IterStart) {
195 : return this->nodeToObj(INHERITED::init(list.fList, start));
196 : }
197 :
198 0 : T* get() { return this->nodeToObj(INHERITED::get()); }
199 :
200 0 : T* next() { return this->nodeToObj(INHERITED::next()); }
201 :
202 0 : T* prev() { return this->nodeToObj(INHERITED::prev()); }
203 :
204 0 : Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; }
205 :
206 : private:
207 : friend class SkTLList;
208 : Node* getNode() { return INHERITED::get(); }
209 :
210 0 : T* nodeToObj(Node* node) {
211 0 : if (node) {
212 0 : return reinterpret_cast<T*>(node->fObj);
213 : } else {
214 0 : return nullptr;
215 : }
216 : }
217 : };
218 :
219 : private:
220 0 : struct Block {
221 : int fNodesInUse;
222 : Node fNodes[N];
223 : };
224 :
225 0 : void delayedInit() {
226 0 : SkASSERT(-1 == fCount);
227 0 : fFirstBlock.fNodesInUse = 0;
228 0 : for (unsigned int i = 0; i < N; ++i) {
229 0 : fFreeList.addToHead(fFirstBlock.fNodes + i);
230 0 : fFirstBlock.fNodes[i].fBlock = &fFirstBlock;
231 : }
232 0 : fCount = 0;
233 0 : this->validate();
234 0 : }
235 :
236 0 : Node* createNode() {
237 0 : if (-1 == fCount) {
238 0 : this->delayedInit();
239 : }
240 0 : Node* node = fFreeList.head();
241 0 : if (node) {
242 0 : fFreeList.remove(node);
243 0 : ++node->fBlock->fNodesInUse;
244 : } else {
245 : // Should not get here when count == 0 because we always have the preallocated first
246 : // block.
247 0 : SkASSERT(fCount > 0);
248 0 : Block* block = reinterpret_cast<Block*>(sk_malloc_throw(sizeof(Block)));
249 0 : node = &block->fNodes[0];
250 0 : new (node) Node;
251 0 : node->fBlock = block;
252 0 : block->fNodesInUse = 1;
253 0 : for (unsigned int i = 1; i < N; ++i) {
254 0 : new (block->fNodes + i) Node;
255 0 : fFreeList.addToHead(block->fNodes + i);
256 0 : block->fNodes[i].fBlock = block;
257 : }
258 : }
259 0 : ++fCount;
260 0 : return node;
261 : }
262 :
263 0 : void removeNode(Node* node) {
264 0 : SkASSERT(node);
265 0 : fList.remove(node);
266 0 : SkTCast<T*>(node->fObj)->~T();
267 0 : Block* block = node->fBlock;
268 : // Don't ever elease the first block, just add its nodes to the free list
269 0 : if (0 == --block->fNodesInUse && block != &fFirstBlock) {
270 0 : for (unsigned int i = 0; i < N; ++i) {
271 0 : if (block->fNodes + i != node) {
272 0 : fFreeList.remove(block->fNodes + i);
273 : }
274 : block->fNodes[i].~Node();
275 : }
276 0 : sk_free(block);
277 : } else {
278 0 : fFreeList.addToHead(node);
279 : }
280 0 : --fCount;
281 0 : this->validate();
282 0 : }
283 :
284 0 : void validate() const {
285 : #ifdef SK_DEBUG
286 0 : bool isEmpty = false;
287 0 : if (-1 == fCount) {
288 : // We should not yet have initialized the free list.
289 0 : SkASSERT(fFreeList.isEmpty());
290 0 : isEmpty = true;
291 0 : } else if (0 == fCount) {
292 : // Should only have the nodes from the first block in the free list.
293 0 : SkASSERT(fFreeList.countEntries() == N);
294 0 : isEmpty = true;
295 : }
296 0 : SkASSERT(isEmpty == fList.isEmpty());
297 0 : fList.validate();
298 0 : fFreeList.validate();
299 0 : typename NodeList::Iter iter;
300 0 : Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart);
301 0 : while (freeNode) {
302 0 : SkASSERT(fFreeList.isInList(freeNode));
303 0 : Block* block = freeNode->fBlock;
304 : // Only the first block is allowed to have all its nodes in the free list.
305 0 : SkASSERT(block->fNodesInUse > 0 || block == &fFirstBlock);
306 0 : SkASSERT((unsigned)block->fNodesInUse < N);
307 0 : int activeCnt = 0;
308 0 : int freeCnt = 0;
309 0 : for (unsigned int i = 0; i < N; ++i) {
310 0 : bool free = fFreeList.isInList(block->fNodes + i);
311 0 : bool active = fList.isInList(block->fNodes + i);
312 0 : SkASSERT(free != active);
313 0 : activeCnt += active;
314 0 : freeCnt += free;
315 : }
316 0 : SkASSERT(activeCnt == block->fNodesInUse);
317 0 : freeNode = iter.next();
318 : }
319 :
320 0 : int count = 0;
321 0 : Node* activeNode = iter.init(fList, Iter::kHead_IterStart);
322 0 : while (activeNode) {
323 0 : ++count;
324 0 : SkASSERT(fList.isInList(activeNode));
325 0 : Block* block = activeNode->fBlock;
326 0 : SkASSERT(block->fNodesInUse > 0 && (unsigned)block->fNodesInUse <= N);
327 :
328 0 : int activeCnt = 0;
329 0 : int freeCnt = 0;
330 0 : for (unsigned int i = 0; i < N; ++i) {
331 0 : bool free = fFreeList.isInList(block->fNodes + i);
332 0 : bool active = fList.isInList(block->fNodes + i);
333 0 : SkASSERT(free != active);
334 0 : activeCnt += active;
335 0 : freeCnt += free;
336 : }
337 0 : SkASSERT(activeCnt == block->fNodesInUse);
338 0 : activeNode = iter.next();
339 : }
340 0 : SkASSERT(count == fCount || (0 == count && -1 == fCount));
341 : #endif
342 0 : }
343 :
344 : NodeList fList;
345 : NodeList fFreeList;
346 : Block fFirstBlock;
347 : int fCount;
348 : };
349 :
350 : #endif
|
