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