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