• 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 "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     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.
SkTLList()46     SkTLList() : fCount(-1) {}
47 
~SkTLList()48     ~SkTLList() {
49         this->validate();
50         typename NodeList::Iter iter;
51         Node* node = iter.init(fList, Iter::kHead_IterStart);
52         while (node) {
53             SkTCast<T*>(node->fObj)->~T();
54             Block* block = node->fBlock;
55             node = iter.next();
56             if (0 == --block->fNodesInUse) {
57                 for (unsigned int i = 0; i < N; ++i) {
58                     block->fNodes[i].~Node();
59                 }
60                 if (block != &fFirstBlock) {
61                     sk_free(block);
62                 }
63             }
64         }
65     }
66 
67     /** Adds a new element to the list at the head. */
addToHead(Args &&...args)68     template <typename... Args> T* addToHead(Args&&... args) {
69         this->validate();
70         Node* node = this->createNode();
71         fList.addToHead(node);
72         this->validate();
73         return new (node->fObj)  T(std::forward<Args>(args)...);
74     }
75 
76     /** Adds a new element to the list at the tail. */
addToTail(Args &&...args)77     template <typename... Args> T* addToTail(Args&&... args) {
78         this->validate();
79         Node* node = this->createNode();
80         fList.addToTail(node);
81         this->validate();
82         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 */
addBefore(Iter location,Args &&...args)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 */
addAfter(Iter location,Args &&...args)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. */
headIter()106     Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); }
tailIter()107     Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); }
108 
head()109     T* head() { return Iter(*this, Iter::kHead_IterStart).get(); }
tail()110     T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); }
head()111     const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); }
tail()112     const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); }
113 
popHead()114     void popHead() {
115         this->validate();
116         Node* node = fList.head();
117         if (node) {
118             this->removeNode(node);
119         }
120         this->validate();
121     }
122 
popTail()123     void popTail() {
124         this->validate();
125         Node* node = fList.head();
126         if (node) {
127             this->removeNode(node);
128         }
129         this->validate();
130     }
131 
remove(T * t)132     void remove(T* t) {
133         this->validate();
134         Node* node = reinterpret_cast<Node*>(t);
135         SkASSERT(reinterpret_cast<T*>(node->fObj) == t);
136         this->removeNode(node);
137         this->validate();
138     }
139 
reset()140     void reset() {
141         this->validate();
142         Iter iter(*this, Iter::kHead_IterStart);
143         while (iter.get()) {
144             Iter next = iter;
145             next.next();
146             this->remove(iter.get());
147             iter = next;
148         }
149         SkASSERT(0 == fCount || -1 == fCount);
150         this->validate();
151     }
152 
count()153     int count() const { return SkTMax(fCount ,0); }
isEmpty()154     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     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 
Iter()188         Iter() {}
189 
190         Iter(const SkTLList& list, IterStart start = kHead_IterStart) {
191             INHERITED::init(list.fList, start);
192         }
193 
194         T* init(const SkTLList& list, IterStart start = kHead_IterStart) {
195             return this->nodeToObj(INHERITED::init(list.fList, start));
196         }
197 
get()198         T* get() { return this->nodeToObj(INHERITED::get()); }
199 
next()200         T* next() { return this->nodeToObj(INHERITED::next()); }
201 
prev()202         T* prev() { return this->nodeToObj(INHERITED::prev()); }
203 
204         Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; }
205 
206     private:
207         friend class SkTLList;
getNode()208         Node* getNode() { return INHERITED::get(); }
209 
nodeToObj(Node * node)210         T* nodeToObj(Node* node) {
211             if (node) {
212                 return reinterpret_cast<T*>(node->fObj);
213             } else {
214                 return nullptr;
215             }
216         }
217     };
218 
219 private:
220     struct Block {
221         int fNodesInUse;
222         Node fNodes[N];
223     };
224 
delayedInit()225     void delayedInit() {
226         SkASSERT(-1 == fCount);
227         fFirstBlock.fNodesInUse = 0;
228         for (unsigned int i = 0; i < N; ++i) {
229             fFreeList.addToHead(fFirstBlock.fNodes + i);
230             fFirstBlock.fNodes[i].fBlock = &fFirstBlock;
231         }
232         fCount = 0;
233         this->validate();
234     }
235 
createNode()236     Node* createNode() {
237         if (-1 == fCount) {
238             this->delayedInit();
239         }
240         Node* node = fFreeList.head();
241         if (node) {
242             fFreeList.remove(node);
243             ++node->fBlock->fNodesInUse;
244         } else {
245             // Should not get here when count == 0 because we always have the preallocated first
246             // block.
247             SkASSERT(fCount > 0);
248             Block* block = reinterpret_cast<Block*>(sk_malloc_throw(sizeof(Block)));
249             node = &block->fNodes[0];
250             new (node) Node;
251             node->fBlock = block;
252             block->fNodesInUse = 1;
253             for (unsigned int i = 1; i < N; ++i) {
254                 new (block->fNodes + i) Node;
255                 fFreeList.addToHead(block->fNodes + i);
256                 block->fNodes[i].fBlock = block;
257             }
258         }
259         ++fCount;
260         return node;
261     }
262 
removeNode(Node * node)263     void removeNode(Node* node) {
264         SkASSERT(node);
265         fList.remove(node);
266         SkTCast<T*>(node->fObj)->~T();
267         Block* block = node->fBlock;
268         // Don't ever elease the first block, just add its nodes to the free list
269         if (0 == --block->fNodesInUse && block != &fFirstBlock) {
270             for (unsigned int i = 0; i < N; ++i) {
271                 if (block->fNodes + i != node) {
272                     fFreeList.remove(block->fNodes + i);
273                 }
274                 block->fNodes[i].~Node();
275             }
276             sk_free(block);
277         } else {
278             fFreeList.addToHead(node);
279         }
280         --fCount;
281         this->validate();
282     }
283 
validate()284     void validate() const {
285 #ifdef SK_DEBUG
286         bool isEmpty = false;
287         if (-1 == fCount) {
288             // We should not yet have initialized the free list.
289             SkASSERT(fFreeList.isEmpty());
290             isEmpty = true;
291         } else if (0 == fCount) {
292             // Should only have the nodes from the first block in the free list.
293             SkASSERT(fFreeList.countEntries() == N);
294             isEmpty = true;
295         }
296         SkASSERT(isEmpty == fList.isEmpty());
297         fList.validate();
298         fFreeList.validate();
299         typename NodeList::Iter iter;
300         Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart);
301         while (freeNode) {
302             SkASSERT(fFreeList.isInList(freeNode));
303             Block* block = freeNode->fBlock;
304             // Only the first block is allowed to have all its nodes in the free list.
305             SkASSERT(block->fNodesInUse > 0 || block == &fFirstBlock);
306             SkASSERT((unsigned)block->fNodesInUse < N);
307             int activeCnt = 0;
308             int freeCnt = 0;
309             for (unsigned int i = 0; i < N; ++i) {
310                 bool free = fFreeList.isInList(block->fNodes + i);
311                 bool active = fList.isInList(block->fNodes + i);
312                 SkASSERT(free != active);
313                 activeCnt += active;
314                 freeCnt += free;
315             }
316             SkASSERT(activeCnt == block->fNodesInUse);
317             freeNode = iter.next();
318         }
319 
320         int count = 0;
321         Node* activeNode = iter.init(fList, Iter::kHead_IterStart);
322         while (activeNode) {
323             ++count;
324             SkASSERT(fList.isInList(activeNode));
325             Block* block = activeNode->fBlock;
326             SkASSERT(block->fNodesInUse > 0 && (unsigned)block->fNodesInUse <= N);
327 
328             int activeCnt = 0;
329             int freeCnt = 0;
330             for (unsigned int i = 0; i < N; ++i) {
331                 bool free = fFreeList.isInList(block->fNodes + i);
332                 bool active = fList.isInList(block->fNodes + i);
333                 SkASSERT(free != active);
334                 activeCnt += active;
335                 freeCnt += free;
336             }
337             SkASSERT(activeCnt == block->fNodesInUse);
338             activeNode = iter.next();
339         }
340         SkASSERT(count == fCount || (0 == count && -1 == fCount));
341 #endif
342     }
343 
344     NodeList fList;
345     NodeList fFreeList;
346     Block    fFirstBlock;
347     int fCount;
348 };
349 
350 #endif
351