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 SkTInternalLList_DEFINED
9 #define SkTInternalLList_DEFINED
10 
11 #include "SkTypes.h"
12 
13 /**
14  * Helper class to automatically initialize the doubly linked list created pointers.
15  */
16 template <typename T> class SkPtrWrapper {
17   public:
SkPtrWrapper()18       SkPtrWrapper() : fPtr(NULL) {}
19       SkPtrWrapper& operator =(T* ptr) { fPtr = ptr; return *this; }
20       operator T*() const { return fPtr; }
21       T* operator->() { return fPtr; }
22   private:
23       T* fPtr;
24 };
25 
26 
27 /**
28  * This macro creates the member variables required by the SkTInternalLList class. It should be
29  * placed in the private section of any class that will be stored in a double linked list.
30  */
31 #define SK_DECLARE_INTERNAL_LLIST_INTERFACE(ClassName)              \
32     friend class SkTInternalLList<ClassName>;                       \
33     /* back pointer to the owning list - for debugging */           \
34     SkDEBUGCODE(SkPtrWrapper<SkTInternalLList<ClassName> > fList;)  \
35     SkPtrWrapper<ClassName> fPrev;                                  \
36     SkPtrWrapper<ClassName> fNext
37 
38 /**
39  * This class implements a templated internal doubly linked list data structure.
40  */
41 template <class T> class SkTInternalLList : SkNoncopyable {
42 public:
SkTInternalLList()43     SkTInternalLList()
44         : fHead(NULL)
45         , fTail(NULL) {
46     }
47 
remove(T * entry)48     void remove(T* entry) {
49         SkASSERT(fHead && fTail);
50         SkASSERT(this->isInList(entry));
51 
52         T* prev = entry->fPrev;
53         T* next = entry->fNext;
54 
55         if (prev) {
56             prev->fNext = next;
57         } else {
58             fHead = next;
59         }
60         if (next) {
61             next->fPrev = prev;
62         } else {
63             fTail = prev;
64         }
65 
66         entry->fPrev = NULL;
67         entry->fNext = NULL;
68 
69 #ifdef SK_DEBUG
70         entry->fList = NULL;
71 #endif
72     }
73 
addToHead(T * entry)74     void addToHead(T* entry) {
75         SkASSERT(NULL == entry->fPrev && NULL == entry->fNext);
76         SkASSERT(NULL == entry->fList);
77 
78         entry->fPrev = NULL;
79         entry->fNext = fHead;
80         if (fHead) {
81             fHead->fPrev = entry;
82         }
83         fHead = entry;
84         if (NULL == fTail) {
85             fTail = entry;
86         }
87 
88 #ifdef SK_DEBUG
89         entry->fList = this;
90 #endif
91     }
92 
addToTail(T * entry)93     void addToTail(T* entry) {
94         SkASSERT(NULL == entry->fPrev && NULL == entry->fNext);
95         SkASSERT(NULL == entry->fList);
96 
97         entry->fPrev = fTail;
98         entry->fNext = NULL;
99         if (fTail) {
100             fTail->fNext = entry;
101         }
102         fTail = entry;
103         if (NULL == fHead) {
104             fHead = entry;
105         }
106 
107 #ifdef SK_DEBUG
108         entry->fList = this;
109 #endif
110     }
111 
112     /**
113      * Inserts a new list entry before an existing list entry. The new entry must not already be
114      * a member of this or any other list. If existingEntry is NULL then the new entry is added
115      * at the tail.
116      */
addBefore(T * newEntry,T * existingEntry)117     void addBefore(T* newEntry, T* existingEntry) {
118         SkASSERT(newEntry);
119 
120         if (NULL == existingEntry) {
121             this->addToTail(newEntry);
122             return;
123         }
124 
125         SkASSERT(this->isInList(existingEntry));
126         newEntry->fNext = existingEntry;
127         T* prev = existingEntry->fPrev;
128         existingEntry->fPrev = newEntry;
129         newEntry->fPrev = prev;
130         if (NULL == prev) {
131             SkASSERT(fHead == existingEntry);
132             fHead = newEntry;
133         } else {
134             prev->fNext = newEntry;
135         }
136 #ifdef SK_DEBUG
137         newEntry->fList = this;
138 #endif
139     }
140 
141     /**
142      * Inserts a new list entry after an existing list entry. The new entry must not already be
143      * a member of this or any other list. If existingEntry is NULL then the new entry is added
144      * at the head.
145      */
addAfter(T * newEntry,T * existingEntry)146     void addAfter(T* newEntry, T* existingEntry) {
147         SkASSERT(newEntry);
148 
149         if (NULL == existingEntry) {
150             this->addToHead(newEntry);
151             return;
152         }
153 
154         SkASSERT(this->isInList(existingEntry));
155         newEntry->fPrev = existingEntry;
156         T* next = existingEntry->fNext;
157         existingEntry->fNext = newEntry;
158         newEntry->fNext = next;
159         if (NULL == next) {
160             SkASSERT(fTail == existingEntry);
161             fTail = newEntry;
162         } else {
163             next->fPrev = newEntry;
164         }
165 #ifdef SK_DEBUG
166         newEntry->fList = this;
167 #endif
168     }
169 
isEmpty()170     bool isEmpty() const {
171         return NULL == fHead && NULL == fTail;
172     }
173 
head()174     T* head() { return fHead; }
tail()175     T* tail() { return fTail; }
176 
177     class Iter {
178     public:
179         enum IterStart {
180             kHead_IterStart,
181             kTail_IterStart
182         };
183 
Iter()184         Iter() : fCurr(NULL) {}
Iter(const Iter & iter)185         Iter(const Iter& iter) : fCurr(iter.fCurr) {}
186         Iter& operator= (const Iter& iter) { fCurr = iter.fCurr; return *this; }
187 
init(const SkTInternalLList & list,IterStart startLoc)188         T* init(const SkTInternalLList& list, IterStart startLoc) {
189             if (kHead_IterStart == startLoc) {
190                 fCurr = list.fHead;
191             } else {
192                 SkASSERT(kTail_IterStart == startLoc);
193                 fCurr = list.fTail;
194             }
195 
196             return fCurr;
197         }
198 
get()199         T* get() { return fCurr; }
200 
201         /**
202          * Return the next/previous element in the list or NULL if at the end.
203          */
next()204         T* next() {
205             if (NULL == fCurr) {
206                 return NULL;
207             }
208 
209             fCurr = fCurr->fNext;
210             return fCurr;
211         }
212 
prev()213         T* prev() {
214             if (NULL == fCurr) {
215                 return NULL;
216             }
217 
218             fCurr = fCurr->fPrev;
219             return fCurr;
220         }
221 
222     private:
223         T* fCurr;
224     };
225 
226 #ifdef SK_DEBUG
validate()227     void validate() const {
228         SkASSERT(!fHead == !fTail);
229         Iter iter;
230         for (T* item = iter.init(*this, Iter::kHead_IterStart); item; item = iter.next()) {
231             SkASSERT(this->isInList(item));
232             if (NULL == item->fPrev) {
233                 SkASSERT(fHead == item);
234             } else {
235                 SkASSERT(item->fPrev->fNext == item);
236             }
237             if (NULL == item->fNext) {
238                 SkASSERT(fTail == item);
239             } else {
240                 SkASSERT(item->fNext->fPrev == item);
241             }
242         }
243     }
244 
245     /**
246      * Debugging-only method that uses the list back pointer to check if 'entry' is indeed in 'this'
247      * list.
248      */
isInList(const T * entry)249     bool isInList(const T* entry) const {
250         return entry->fList == this;
251     }
252 
253     /**
254      * Debugging-only method that laboriously counts the list entries.
255      */
countEntries()256     int countEntries() const {
257         int count = 0;
258         for (T* entry = fHead; entry; entry = entry->fNext) {
259             ++count;
260         }
261         return count;
262     }
263 #endif // SK_DEBUG
264 
265 private:
266     T* fHead;
267     T* fTail;
268 
269     typedef SkNoncopyable INHERITED;
270 };
271 
272 #endif
273