• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 "SkMalloc.h"
12 #include "SkTInternalLList.h"
13 #include "SkTemplates.h"
14 #include "SkTypes.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 */
31 template <typename T, unsigned int N> class SkTLList : SkNoncopyable {
32 private:
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 
41 public:
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.
SkTLList()47     SkTLList() : fCount(-1) {}
48 
~SkTLList()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. */
addToHead(Args &&...args)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. */
addToTail(Args &&...args)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 */
addBefore(Iter location,Args &&...args)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 */
addAfter(Iter location,Args &&...args)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. */
headIter()107     Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); }
tailIter()108     Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); }
109 
head()110     T* head() { return Iter(*this, Iter::kHead_IterStart).get(); }
tail()111     T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); }
head()112     const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); }
tail()113     const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); }
114 
popHead()115     void popHead() {
116         this->validate();
117         Node* node = fList.head();
118         if (node) {
119             this->removeNode(node);
120         }
121         this->validate();
122     }
123 
popTail()124     void popTail() {
125         this->validate();
126         Node* node = fList.head();
127         if (node) {
128             this->removeNode(node);
129         }
130         this->validate();
131     }
132 
remove(T * t)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 
reset()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 
count()154     int count() const { return SkTMax(fCount ,0); }
isEmpty()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 
Iter()189         Iter() {}
190 
191         Iter(const SkTLList& list, IterStart start = kHead_IterStart) {
192             INHERITED::init(list.fList, start);
193         }
194 
195         T* init(const SkTLList& list, IterStart start = kHead_IterStart) {
196             return this->nodeToObj(INHERITED::init(list.fList, start));
197         }
198 
get()199         T* get() { return this->nodeToObj(INHERITED::get()); }
200 
next()201         T* next() { return this->nodeToObj(INHERITED::next()); }
202 
prev()203         T* prev() { return this->nodeToObj(INHERITED::prev()); }
204 
205         Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; }
206 
207     private:
208         friend class SkTLList;
getNode()209         Node* getNode() { return INHERITED::get(); }
210 
nodeToObj(Node * node)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 
220 private:
221     struct Block {
222         int fNodesInUse;
223         Node fNodes[N];
224     };
225 
delayedInit()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 
createNode()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 
removeNode(Node * node)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 
validate()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 
351 #endif
352