robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 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 | |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 8 | #ifndef SkTInternalLList_DEFINED |
| 9 | #define SkTInternalLList_DEFINED |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 10 | |
| 11 | #include "SkTypes.h" |
| 12 | |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 13 | /** |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 14 | * Helper class to automatically initialize the doubly linked list created pointers. |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 15 | */ |
| 16 | template <typename T> class SkPtrWrapper { |
| 17 | public: |
| 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 | /** |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 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. |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 30 | */ |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 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 |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 37 | |
| 38 | /** |
| 39 | * This class implements a templated internal doubly linked list data structure. |
| 40 | */ |
commit-bot@chromium.org | e3beb6b | 2014-04-07 19:34:38 +0000 | [diff] [blame^] | 41 | template <class T> class SkTInternalLList : SkNoncopyable { |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 42 | public: |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 43 | SkTInternalLList() |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 44 | : fHead(NULL) |
| 45 | , fTail(NULL) { |
| 46 | } |
| 47 | |
| 48 | void remove(T* entry) { |
robertphillips@google.com | 9474ed0 | 2012-09-04 13:34:32 +0000 | [diff] [blame] | 49 | SkASSERT(NULL != fHead && NULL != fTail); |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 50 | SkASSERT(this->isInList(entry)); |
| 51 | |
| 52 | T* prev = entry->fPrev; |
| 53 | T* next = entry->fNext; |
| 54 | |
| 55 | if (NULL != prev) { |
| 56 | prev->fNext = next; |
| 57 | } else { |
| 58 | fHead = next; |
| 59 | } |
| 60 | if (NULL != next) { |
| 61 | next->fPrev = prev; |
| 62 | } else { |
| 63 | fTail = prev; |
| 64 | } |
| 65 | |
| 66 | entry->fPrev = NULL; |
| 67 | entry->fNext = NULL; |
| 68 | |
bsalomon@google.com | 39ac1ae | 2012-08-23 13:24:31 +0000 | [diff] [blame] | 69 | #ifdef SK_DEBUG |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 70 | entry->fList = NULL; |
| 71 | #endif |
| 72 | } |
| 73 | |
| 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 (NULL != fHead) { |
| 81 | fHead->fPrev = entry; |
| 82 | } |
| 83 | fHead = entry; |
| 84 | if (NULL == fTail) { |
| 85 | fTail = entry; |
| 86 | } |
| 87 | |
bsalomon@google.com | 39ac1ae | 2012-08-23 13:24:31 +0000 | [diff] [blame] | 88 | #ifdef SK_DEBUG |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 89 | entry->fList = this; |
| 90 | #endif |
| 91 | } |
| 92 | |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 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 (NULL != 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 | |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 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(NULL != 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 | } |
robertphillips@google.com | b8b8ba0 | 2012-12-03 23:34:32 +0000 | [diff] [blame] | 136 | #ifdef SK_DEBUG |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 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(NULL != 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 | } |
robertphillips@google.com | b8b8ba0 | 2012-12-03 23:34:32 +0000 | [diff] [blame] | 165 | #ifdef SK_DEBUG |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 166 | newEntry->fList = this; |
| 167 | #endif |
| 168 | } |
| 169 | |
rmistry@google.com | fbfcd56 | 2012-08-23 18:09:54 +0000 | [diff] [blame] | 170 | bool isEmpty() const { |
| 171 | return NULL == fHead && NULL == fTail; |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 172 | } |
| 173 | |
bsalomon@google.com | a292112 | 2012-08-28 12:34:17 +0000 | [diff] [blame] | 174 | T* head() { return fHead; } |
| 175 | T* tail() { return fTail; } |
| 176 | |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 177 | class Iter { |
| 178 | public: |
| 179 | enum IterStart { |
| 180 | kHead_IterStart, |
| 181 | kTail_IterStart |
| 182 | }; |
| 183 | |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 184 | Iter() : fCurr(NULL) {} |
| 185 | Iter(const Iter& iter) : fCurr(iter.fCurr) {} |
| 186 | Iter& operator= (const Iter& iter) { fCurr = iter.fCurr; return *this; } |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 187 | |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 188 | T* init(const SkTInternalLList& list, IterStart startLoc) { |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 189 | if (kHead_IterStart == startLoc) { |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 190 | fCurr = list.fHead; |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 191 | } else { |
| 192 | SkASSERT(kTail_IterStart == startLoc); |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 193 | fCurr = list.fTail; |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 194 | } |
| 195 | |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 196 | return fCurr; |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 197 | } |
| 198 | |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 199 | T* get() { return fCurr; } |
| 200 | |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 201 | /** |
| 202 | * Return the next/previous element in the list or NULL if at the end. |
| 203 | */ |
| 204 | T* next() { |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 205 | if (NULL == fCurr) { |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 206 | return NULL; |
| 207 | } |
| 208 | |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 209 | fCurr = fCurr->fNext; |
| 210 | return fCurr; |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 211 | } |
| 212 | |
| 213 | T* prev() { |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 214 | if (NULL == fCurr) { |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 215 | return NULL; |
| 216 | } |
| 217 | |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 218 | fCurr = fCurr->fPrev; |
| 219 | return fCurr; |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 220 | } |
| 221 | |
| 222 | private: |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 223 | T* fCurr; |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 224 | }; |
| 225 | |
bsalomon@google.com | 39ac1ae | 2012-08-23 13:24:31 +0000 | [diff] [blame] | 226 | #ifdef SK_DEBUG |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 227 | void validate() const { |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 228 | SkASSERT(!fHead == !fTail); |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 229 | Iter iter; |
commit-bot@chromium.org | 7cc93bc | 2013-12-04 14:51:31 +0000 | [diff] [blame] | 230 | for (T* item = iter.init(*this, Iter::kHead_IterStart); NULL != item; item = iter.next()) { |
bsalomon@google.com | dd3f7a9 | 2012-12-03 19:47:41 +0000 | [diff] [blame] | 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 | } |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 243 | } |
| 244 | |
| 245 | /** |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 246 | * Debugging-only method that uses the list back pointer to check if 'entry' is indeed in 'this' |
| 247 | * list. |
robertphillips@google.com | 2ea0a23 | 2012-08-23 11:13:48 +0000 | [diff] [blame] | 248 | */ |
| 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 | */ |
| 256 | int countEntries() const { |
| 257 | int count = 0; |
| 258 | for (T* entry = fHead; NULL != 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 | |
bsalomon@google.com | 42619d8 | 2012-12-03 14:54:59 +0000 | [diff] [blame] | 272 | #endif |