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#include "SkTemplates.h"
13
14template <typename T> class SkTLList;
15template <typename T>
16inline void* operator new(size_t, SkTLList<T>* list,
17                          typename SkTLList<T>::Placement placement,
18                          const typename SkTLList<T>::Iter& location);
19
20/** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the
21    the list creates the objects and they are deleted upon removal. This class block-allocates
22    space for entries based on a param passed to the constructor.
23
24    Elements of the list can be constructed in place using the following macros:
25        SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args)
26        SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args)
27    where list is a SkTLList<type_name>*, location is an iterator, and args is the paren-surrounded
28    constructor arguments for type_name. These macros behave like addBefore() and addAfter().
29*/
30template <typename T>
31class SkTLList : SkNoncopyable {
32private:
33    struct Block;
34    struct Node {
35        char fObj[sizeof(T)];
36        SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node);
37        Block* fBlock; // owning block.
38    };
39    typedef SkTInternalLList<Node> NodeList;
40
41public:
42
43    class Iter;
44
45    /** allocCnt is the number of objects to allocate as a group. In the worst case fragmentation
46        each object is using the space required for allocCnt unfragmented objects. */
47    SkTLList(int allocCnt = 1) : fCount(0), fAllocCnt(allocCnt) {
48        SkASSERT(allocCnt > 0);
49        this->validate();
50    }
51
52    ~SkTLList() {
53        this->validate();
54        typename NodeList::Iter iter;
55        Node* node = iter.init(fList, Iter::kHead_IterStart);
56        while (NULL != node) {
57            SkTCast<T*>(node->fObj)->~T();
58            Block* block = node->fBlock;
59            node = iter.next();
60            if (0 == --block->fNodesInUse) {
61                for (int i = 0; i < fAllocCnt; ++i) {
62                    block->fNodes[i].~Node();
63                }
64                sk_free(block);
65            }
66        }
67    }
68
69    T* addToHead(const T& t) {
70        this->validate();
71        Node* node = this->createNode();
72        fList.addToHead(node);
73        SkNEW_PLACEMENT_ARGS(node->fObj, T, (t));
74        this->validate();
75        return reinterpret_cast<T*>(node->fObj);
76    }
77
78    T* addToHead() {
79        this->validate();
80        Node* node = this->createNode();
81        fList.addToHead(node);
82        SkNEW_PLACEMENT(node->fObj, T);
83        this->validate();
84        return reinterpret_cast<T*>(node->fObj);
85    }
86
87    T* addToTail(const T& t) {
88        this->validate();
89        Node* node = this->createNode();
90        fList.addToTail(node);
91        SkNEW_PLACEMENT_ARGS(node->fObj, T, (t));
92        this->validate();
93        return reinterpret_cast<T*>(node->fObj);
94    }
95
96    T* addToTail() {
97        this->validate();
98        Node* node = this->createNode();
99        fList.addToTail(node);
100        SkNEW_PLACEMENT(node->fObj, T);
101        this->validate();
102        return reinterpret_cast<T*>(node->fObj);
103    }
104
105    /** Adds a new element to the list before the location indicated by the iterator. If the
106        iterator refers to a NULL location then the new element is added at the tail */
107    T* addBefore(const T& t, const Iter& location) {
108        return SkNEW_PLACEMENT_ARGS(this->internalAddBefore(location), T, (t));
109    }
110
111    /** Adds a new element to the list after the location indicated by the iterator. If the
112        iterator refers to a NULL location then the new element is added at the head */
113    T* addAfter(const T& t, const Iter& location) {
114        return SkNEW_PLACEMENT_ARGS(this->internalAddAfter(location), T, (t));
115    }
116
117    /** Convenience methods for getting an iterator initialized to the head/tail of the list. */
118    Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); }
119    Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); }
120
121    T* head() { return Iter(*this, Iter::kHead_IterStart).get(); }
122    T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); }
123    const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); }
124    const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); }
125
126    void popHead() {
127        this->validate();
128        Node* node = fList.head();
129        if (NULL != node) {
130            this->removeNode(node);
131        }
132        this->validate();
133    }
134
135    void popTail() {
136        this->validate();
137        Node* node = fList.head();
138        if (NULL != node) {
139            this->removeNode(node);
140        }
141        this->validate();
142    }
143
144    void remove(T* t) {
145        this->validate();
146        Node* node = reinterpret_cast<Node*>(t);
147        SkASSERT(reinterpret_cast<T*>(node->fObj) == t);
148        this->removeNode(node);
149        this->validate();
150    }
151
152    void reset() {
153        this->validate();
154        Iter iter(*this, Iter::kHead_IterStart);
155        while (iter.get()) {
156            Iter next = iter;
157            next.next();
158            this->remove(iter.get());
159            iter = next;
160        }
161        SkASSERT(0 == fCount);
162        this->validate();
163    }
164
165    int count() const { return fCount; }
166    bool isEmpty() const { this->validate(); return 0 == fCount; }
167
168    bool operator== (const SkTLList& list) const {
169        if (this == &list) {
170            return true;
171        }
172        if (fCount != list.fCount) {
173            return false;
174        }
175        for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart);
176             a.get();
177             a.next(), b.next()) {
178            SkASSERT(NULL != b.get()); // already checked that counts match.
179            if (!(*a.get() == *b.get())) {
180                return false;
181            }
182        }
183        return true;
184    }
185    bool operator!= (const SkTLList& list) const { return !(*this == list); }
186
187    /** The iterator becomes invalid if the element it refers to is removed from the list. */
188    class Iter : private NodeList::Iter {
189    private:
190        typedef typename NodeList::Iter INHERITED;
191
192    public:
193        typedef typename INHERITED::IterStart IterStart;
194        //!< Start the iterator at the head of the list.
195        static const IterStart kHead_IterStart = INHERITED::kHead_IterStart;
196        //!< Start the iterator at the tail of the list.
197        static const IterStart kTail_IterStart = INHERITED::kTail_IterStart;
198
199        Iter() {}
200
201        Iter(const SkTLList& list, IterStart start = kHead_IterStart) {
202            INHERITED::init(list.fList, start);
203        }
204
205        T* init(const SkTLList& list, IterStart start = kHead_IterStart) {
206            return this->nodeToObj(INHERITED::init(list.fList, start));
207        }
208
209        T* get() { return this->nodeToObj(INHERITED::get()); }
210
211        T* next() { return this->nodeToObj(INHERITED::next()); }
212
213        T* prev() { return this->nodeToObj(INHERITED::prev()); }
214
215        Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; }
216
217    private:
218        friend class SkTLList;
219        Node* getNode() { return INHERITED::get(); }
220
221        T* nodeToObj(Node* node) {
222            if (NULL != node) {
223                return reinterpret_cast<T*>(node->fObj);
224            } else {
225                return NULL;
226            }
227        }
228    };
229
230    // For use with operator new
231    enum Placement {
232        kBefore_Placement,
233        kAfter_Placement,
234    };
235
236private:
237    struct Block {
238        int fNodesInUse;
239        Node fNodes[1];
240    };
241
242    size_t blockSize() const { return sizeof(Block) + sizeof(Node) * (fAllocCnt-1); }
243
244    Node* createNode() {
245        Node* node = fFreeList.head();
246        if (NULL != node) {
247            fFreeList.remove(node);
248            ++node->fBlock->fNodesInUse;
249        } else {
250            Block* block = reinterpret_cast<Block*>(sk_malloc_flags(this->blockSize(), 0));
251            node = &block->fNodes[0];
252            SkNEW_PLACEMENT(node, Node);
253            node->fBlock = block;
254            block->fNodesInUse = 1;
255            for (int i = 1; i < fAllocCnt; ++i) {
256                SkNEW_PLACEMENT(block->fNodes + i, Node);
257                fFreeList.addToHead(block->fNodes + i);
258                block->fNodes[i].fBlock = block;
259            }
260        }
261        ++fCount;
262        return node;
263    }
264
265    void removeNode(Node* node) {
266        SkASSERT(NULL != node);
267        fList.remove(node);
268        SkTCast<T*>(node->fObj)->~T();
269        if (0 == --node->fBlock->fNodesInUse) {
270            Block* block = node->fBlock;
271            for (int i = 0; i < fAllocCnt; ++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        SkASSERT((0 == fCount) == fList.isEmpty());
288        SkASSERT((0 != fCount) || fFreeList.isEmpty());
289
290        fList.validate();
291        fFreeList.validate();
292        typename NodeList::Iter iter;
293        Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart);
294        while (freeNode) {
295            SkASSERT(fFreeList.isInList(freeNode));
296            Block* block = freeNode->fBlock;
297            SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse < fAllocCnt);
298
299            int activeCnt = 0;
300            int freeCnt = 0;
301            for (int i = 0; i < fAllocCnt; ++i) {
302                bool free = fFreeList.isInList(block->fNodes + i);
303                bool active = fList.isInList(block->fNodes + i);
304                SkASSERT(free != active);
305                activeCnt += active;
306                freeCnt += free;
307            }
308            SkASSERT(activeCnt == block->fNodesInUse);
309            freeNode = iter.next();
310        }
311
312        int count = 0;
313        Node* activeNode = iter.init(fList, Iter::kHead_IterStart);
314        while (activeNode) {
315            ++count;
316            SkASSERT(fList.isInList(activeNode));
317            Block* block = activeNode->fBlock;
318            SkASSERT(block->fNodesInUse > 0 && block->fNodesInUse <= fAllocCnt);
319
320            int activeCnt = 0;
321            int freeCnt = 0;
322            for (int i = 0; i < fAllocCnt; ++i) {
323                bool free = fFreeList.isInList(block->fNodes + i);
324                bool active = fList.isInList(block->fNodes + i);
325                SkASSERT(free != active);
326                activeCnt += active;
327                freeCnt += free;
328            }
329            SkASSERT(activeCnt == block->fNodesInUse);
330            activeNode = iter.next();
331        }
332        SkASSERT(count == fCount);
333#endif
334    }
335
336    // Support in-place initializing of objects inserted into the list via operator new.
337    friend void* operator new<T>(size_t,
338                                 SkTLList* list,
339                                 Placement placement,
340                                 const Iter& location);
341
342
343    // Helpers that insert the node and returns a pointer to where the new object should be init'ed.
344    void* internalAddBefore(Iter location) {
345        this->validate();
346        Node* node = this->createNode();
347        fList.addBefore(node, location.getNode());
348        this->validate();
349        return node->fObj;
350    }
351
352    void* internalAddAfter(Iter location) {
353        this->validate();
354        Node* node = this->createNode();
355        fList.addAfter(node, location.getNode());
356        this->validate();
357        return node->fObj;
358    }
359
360    NodeList fList;
361    NodeList fFreeList;
362    int fCount;
363    int fAllocCnt;
364
365};
366
367// Use the below macros rather than calling this directly
368template <typename T>
369void *operator new(size_t, SkTLList<T>* list,
370                   typename SkTLList<T>::Placement placement,
371                   const typename SkTLList<T>::Iter& location) {
372    SkASSERT(NULL != list);
373    if (SkTLList<T>::kBefore_Placement == placement) {
374        return list->internalAddBefore(location);
375    } else {
376        return list->internalAddAfter(location);
377    }
378}
379
380// Skia doesn't use C++ exceptions but it may be compiled with them enabled. Having an op delete
381// to match the op new silences warnings about missing op delete when a constructor throws an
382// exception.
383template <typename T>
384void operator delete(void*,
385                     SkTLList<T>*,
386                     typename SkTLList<T>::Placement,
387                     const typename SkTLList<T>::Iter&) {
388    SK_CRASH();
389}
390
391#define SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) \
392    (new ((list), SkTLList< type_name >::kBefore_Placement, (location)) type_name args)
393
394#define SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) \
395    (new ((list), SkTLList< type_name >::kAfter_Placement, (location)) type_name args)
396
397#define SkNEW_INSERT_AT_LLIST_HEAD(list, type_name, args) \
398    SkNEW_INSERT_IN_LLIST_BEFORE((list), (list)->headIter(), type_name, args)
399
400#define SkNEW_INSERT_AT_LLIST_TAIL(list, type_name, args) \
401    SkNEW_INSERT_IN_LLIST_AFTER((list), (list)->tailIter(), type_name, args)
402
403#endif
404