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