Line data Source code
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:
18 0 : SkPtrWrapper() : fPtr(NULL) {}
19 0 : SkPtrWrapper& operator =(T* ptr) { fPtr = ptr; return *this; }
20 0 : operator T*() const { return fPtr; }
21 0 : 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:
43 0 : SkTInternalLList()
44 : : fHead(NULL)
45 0 : , fTail(NULL) {
46 0 : }
47 :
48 0 : void remove(T* entry) {
49 0 : SkASSERT(fHead && fTail);
50 0 : SkASSERT(this->isInList(entry));
51 :
52 0 : T* prev = entry->fPrev;
53 0 : T* next = entry->fNext;
54 :
55 0 : if (prev) {
56 0 : prev->fNext = next;
57 : } else {
58 0 : fHead = next;
59 : }
60 0 : if (next) {
61 0 : next->fPrev = prev;
62 : } else {
63 0 : fTail = prev;
64 : }
65 :
66 0 : entry->fPrev = NULL;
67 0 : entry->fNext = NULL;
68 :
69 : #ifdef SK_DEBUG
70 0 : entry->fList = NULL;
71 : #endif
72 0 : }
73 :
74 0 : void addToHead(T* entry) {
75 0 : SkASSERT(NULL == entry->fPrev && NULL == entry->fNext);
76 0 : SkASSERT(NULL == entry->fList);
77 :
78 0 : entry->fPrev = NULL;
79 0 : entry->fNext = fHead;
80 0 : if (fHead) {
81 0 : fHead->fPrev = entry;
82 : }
83 0 : fHead = entry;
84 0 : if (NULL == fTail) {
85 0 : fTail = entry;
86 : }
87 :
88 : #ifdef SK_DEBUG
89 0 : entry->fList = this;
90 : #endif
91 0 : }
92 :
93 0 : void addToTail(T* entry) {
94 0 : SkASSERT(NULL == entry->fPrev && NULL == entry->fNext);
95 0 : SkASSERT(NULL == entry->fList);
96 :
97 0 : entry->fPrev = fTail;
98 0 : entry->fNext = NULL;
99 0 : if (fTail) {
100 0 : fTail->fNext = entry;
101 : }
102 0 : fTail = entry;
103 0 : if (NULL == fHead) {
104 0 : fHead = entry;
105 : }
106 :
107 : #ifdef SK_DEBUG
108 0 : entry->fList = this;
109 : #endif
110 0 : }
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 : */
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 : */
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 :
170 0 : bool isEmpty() const {
171 0 : return NULL == fHead && NULL == fTail;
172 : }
173 :
174 0 : T* head() { return fHead; }
175 0 : T* tail() { return fTail; }
176 :
177 : class Iter {
178 : public:
179 : enum IterStart {
180 : kHead_IterStart,
181 : kTail_IterStart
182 : };
183 :
184 0 : Iter() : fCurr(NULL) {}
185 0 : Iter(const Iter& iter) : fCurr(iter.fCurr) {}
186 0 : Iter& operator= (const Iter& iter) { fCurr = iter.fCurr; return *this; }
187 :
188 0 : T* init(const SkTInternalLList& list, IterStart startLoc) {
189 0 : if (kHead_IterStart == startLoc) {
190 0 : fCurr = list.fHead;
191 : } else {
192 0 : SkASSERT(kTail_IterStart == startLoc);
193 0 : fCurr = list.fTail;
194 : }
195 :
196 0 : return fCurr;
197 : }
198 :
199 0 : T* get() { return fCurr; }
200 :
201 : /**
202 : * Return the next/previous element in the list or NULL if at the end.
203 : */
204 0 : T* next() {
205 0 : if (NULL == fCurr) {
206 0 : return NULL;
207 : }
208 :
209 0 : fCurr = fCurr->fNext;
210 0 : return fCurr;
211 : }
212 :
213 0 : T* prev() {
214 0 : if (NULL == fCurr) {
215 0 : return NULL;
216 : }
217 :
218 0 : fCurr = fCurr->fPrev;
219 0 : return fCurr;
220 : }
221 :
222 : private:
223 : T* fCurr;
224 : };
225 :
226 : #ifdef SK_DEBUG
227 0 : void validate() const {
228 0 : SkASSERT(!fHead == !fTail);
229 0 : Iter iter;
230 0 : for (T* item = iter.init(*this, Iter::kHead_IterStart); item; item = iter.next()) {
231 0 : SkASSERT(this->isInList(item));
232 0 : if (NULL == item->fPrev) {
233 0 : SkASSERT(fHead == item);
234 : } else {
235 0 : SkASSERT(item->fPrev->fNext == item);
236 : }
237 0 : if (NULL == item->fNext) {
238 0 : SkASSERT(fTail == item);
239 : } else {
240 0 : SkASSERT(item->fNext->fPrev == item);
241 : }
242 : }
243 0 : }
244 :
245 : /**
246 : * Debugging-only method that uses the list back pointer to check if 'entry' is indeed in 'this'
247 : * list.
248 : */
249 0 : bool isInList(const T* entry) const {
250 0 : return entry->fList == this;
251 : }
252 :
253 : /**
254 : * Debugging-only method that laboriously counts the list entries.
255 : */
256 0 : int countEntries() const {
257 0 : int count = 0;
258 0 : for (T* entry = fHead; entry; entry = entry->fNext) {
259 0 : ++count;
260 : }
261 0 : 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
|
