| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2012 Google Inc. | 2 * Copyright 2012 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 | 7 |
| 8 #ifndef SkTInternalLList_DEFINED | 8 #ifndef SkTInternalLList_DEFINED |
| 9 #define SkTInternalLList_DEFINED | 9 #define SkTInternalLList_DEFINED |
| 10 | 10 |
| (...skipping 28 matching lines...) Expand all Loading... |
| 39 * This class implements a templated internal doubly linked list data structure. | 39 * This class implements a templated internal doubly linked list data structure. |
| 40 */ | 40 */ |
| 41 template <class T> class SkTInternalLList : SkNoncopyable { | 41 template <class T> class SkTInternalLList : SkNoncopyable { |
| 42 public: | 42 public: |
| 43 SkTInternalLList() | 43 SkTInternalLList() |
| 44 : fHead(NULL) | 44 : fHead(NULL) |
| 45 , fTail(NULL) { | 45 , fTail(NULL) { |
| 46 } | 46 } |
| 47 | 47 |
| 48 void remove(T* entry) { | 48 void remove(T* entry) { |
| 49 SkASSERT(NULL != fHead && NULL != fTail); | 49 SkASSERT(fHead && fTail); |
| 50 SkASSERT(this->isInList(entry)); | 50 SkASSERT(this->isInList(entry)); |
| 51 | 51 |
| 52 T* prev = entry->fPrev; | 52 T* prev = entry->fPrev; |
| 53 T* next = entry->fNext; | 53 T* next = entry->fNext; |
| 54 | 54 |
| 55 if (NULL != prev) { | 55 if (prev) { |
| 56 prev->fNext = next; | 56 prev->fNext = next; |
| 57 } else { | 57 } else { |
| 58 fHead = next; | 58 fHead = next; |
| 59 } | 59 } |
| 60 if (NULL != next) { | 60 if (next) { |
| 61 next->fPrev = prev; | 61 next->fPrev = prev; |
| 62 } else { | 62 } else { |
| 63 fTail = prev; | 63 fTail = prev; |
| 64 } | 64 } |
| 65 | 65 |
| 66 entry->fPrev = NULL; | 66 entry->fPrev = NULL; |
| 67 entry->fNext = NULL; | 67 entry->fNext = NULL; |
| 68 | 68 |
| 69 #ifdef SK_DEBUG | 69 #ifdef SK_DEBUG |
| 70 entry->fList = NULL; | 70 entry->fList = NULL; |
| 71 #endif | 71 #endif |
| 72 } | 72 } |
| 73 | 73 |
| 74 void addToHead(T* entry) { | 74 void addToHead(T* entry) { |
| 75 SkASSERT(NULL == entry->fPrev && NULL == entry->fNext); | 75 SkASSERT(NULL == entry->fPrev && NULL == entry->fNext); |
| 76 SkASSERT(NULL == entry->fList); | 76 SkASSERT(NULL == entry->fList); |
| 77 | 77 |
| 78 entry->fPrev = NULL; | 78 entry->fPrev = NULL; |
| 79 entry->fNext = fHead; | 79 entry->fNext = fHead; |
| 80 if (NULL != fHead) { | 80 if (fHead) { |
| 81 fHead->fPrev = entry; | 81 fHead->fPrev = entry; |
| 82 } | 82 } |
| 83 fHead = entry; | 83 fHead = entry; |
| 84 if (NULL == fTail) { | 84 if (NULL == fTail) { |
| 85 fTail = entry; | 85 fTail = entry; |
| 86 } | 86 } |
| 87 | 87 |
| 88 #ifdef SK_DEBUG | 88 #ifdef SK_DEBUG |
| 89 entry->fList = this; | 89 entry->fList = this; |
| 90 #endif | 90 #endif |
| 91 } | 91 } |
| 92 | 92 |
| 93 void addToTail(T* entry) { | 93 void addToTail(T* entry) { |
| 94 SkASSERT(NULL == entry->fPrev && NULL == entry->fNext); | 94 SkASSERT(NULL == entry->fPrev && NULL == entry->fNext); |
| 95 SkASSERT(NULL == entry->fList); | 95 SkASSERT(NULL == entry->fList); |
| 96 | 96 |
| 97 entry->fPrev = fTail; | 97 entry->fPrev = fTail; |
| 98 entry->fNext = NULL; | 98 entry->fNext = NULL; |
| 99 if (NULL != fTail) { | 99 if (fTail) { |
| 100 fTail->fNext = entry; | 100 fTail->fNext = entry; |
| 101 } | 101 } |
| 102 fTail = entry; | 102 fTail = entry; |
| 103 if (NULL == fHead) { | 103 if (NULL == fHead) { |
| 104 fHead = entry; | 104 fHead = entry; |
| 105 } | 105 } |
| 106 | 106 |
| 107 #ifdef SK_DEBUG | 107 #ifdef SK_DEBUG |
| 108 entry->fList = this; | 108 entry->fList = this; |
| 109 #endif | 109 #endif |
| 110 } | 110 } |
| 111 | 111 |
| 112 /** | 112 /** |
| 113 * Inserts a new list entry before an existing list entry. The new entry mus
t not already be | 113 * Inserts a new list entry before an existing list entry. The new entry mus
t not already be |
| 114 * a member of this or any other list. If existingEntry is NULL then the new
entry is added | 114 * a member of this or any other list. If existingEntry is NULL then the new
entry is added |
| 115 * at the tail. | 115 * at the tail. |
| 116 */ | 116 */ |
| 117 void addBefore(T* newEntry, T* existingEntry) { | 117 void addBefore(T* newEntry, T* existingEntry) { |
| 118 SkASSERT(NULL != newEntry); | 118 SkASSERT(newEntry); |
| 119 | 119 |
| 120 if (NULL == existingEntry) { | 120 if (NULL == existingEntry) { |
| 121 this->addToTail(newEntry); | 121 this->addToTail(newEntry); |
| 122 return; | 122 return; |
| 123 } | 123 } |
| 124 | 124 |
| 125 SkASSERT(this->isInList(existingEntry)); | 125 SkASSERT(this->isInList(existingEntry)); |
| 126 newEntry->fNext = existingEntry; | 126 newEntry->fNext = existingEntry; |
| 127 T* prev = existingEntry->fPrev; | 127 T* prev = existingEntry->fPrev; |
| 128 existingEntry->fPrev = newEntry; | 128 existingEntry->fPrev = newEntry; |
| 129 newEntry->fPrev = prev; | 129 newEntry->fPrev = prev; |
| 130 if (NULL == prev) { | 130 if (NULL == prev) { |
| 131 SkASSERT(fHead == existingEntry); | 131 SkASSERT(fHead == existingEntry); |
| 132 fHead = newEntry; | 132 fHead = newEntry; |
| 133 } else { | 133 } else { |
| 134 prev->fNext = newEntry; | 134 prev->fNext = newEntry; |
| 135 } | 135 } |
| 136 #ifdef SK_DEBUG | 136 #ifdef SK_DEBUG |
| 137 newEntry->fList = this; | 137 newEntry->fList = this; |
| 138 #endif | 138 #endif |
| 139 } | 139 } |
| 140 | 140 |
| 141 /** | 141 /** |
| 142 * Inserts a new list entry after an existing list entry. The new entry must
not already be | 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 | 143 * a member of this or any other list. If existingEntry is NULL then the new
entry is added |
| 144 * at the head. | 144 * at the head. |
| 145 */ | 145 */ |
| 146 void addAfter(T* newEntry, T* existingEntry) { | 146 void addAfter(T* newEntry, T* existingEntry) { |
| 147 SkASSERT(NULL != newEntry); | 147 SkASSERT(newEntry); |
| 148 | 148 |
| 149 if (NULL == existingEntry) { | 149 if (NULL == existingEntry) { |
| 150 this->addToHead(newEntry); | 150 this->addToHead(newEntry); |
| 151 return; | 151 return; |
| 152 } | 152 } |
| 153 | 153 |
| 154 SkASSERT(this->isInList(existingEntry)); | 154 SkASSERT(this->isInList(existingEntry)); |
| 155 newEntry->fPrev = existingEntry; | 155 newEntry->fPrev = existingEntry; |
| 156 T* next = existingEntry->fNext; | 156 T* next = existingEntry->fNext; |
| 157 existingEntry->fNext = newEntry; | 157 existingEntry->fNext = newEntry; |
| (...skipping 62 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 220 } | 220 } |
| 221 | 221 |
| 222 private: | 222 private: |
| 223 T* fCurr; | 223 T* fCurr; |
| 224 }; | 224 }; |
| 225 | 225 |
| 226 #ifdef SK_DEBUG | 226 #ifdef SK_DEBUG |
| 227 void validate() const { | 227 void validate() const { |
| 228 SkASSERT(!fHead == !fTail); | 228 SkASSERT(!fHead == !fTail); |
| 229 Iter iter; | 229 Iter iter; |
| 230 for (T* item = iter.init(*this, Iter::kHead_IterStart); NULL != item; it
em = iter.next()) { | 230 for (T* item = iter.init(*this, Iter::kHead_IterStart); item; item = ite
r.next()) { |
| 231 SkASSERT(this->isInList(item)); | 231 SkASSERT(this->isInList(item)); |
| 232 if (NULL == item->fPrev) { | 232 if (NULL == item->fPrev) { |
| 233 SkASSERT(fHead == item); | 233 SkASSERT(fHead == item); |
| 234 } else { | 234 } else { |
| 235 SkASSERT(item->fPrev->fNext == item); | 235 SkASSERT(item->fPrev->fNext == item); |
| 236 } | 236 } |
| 237 if (NULL == item->fNext) { | 237 if (NULL == item->fNext) { |
| 238 SkASSERT(fTail == item); | 238 SkASSERT(fTail == item); |
| 239 } else { | 239 } else { |
| 240 SkASSERT(item->fNext->fPrev == item); | 240 SkASSERT(item->fNext->fPrev == item); |
| 241 } | 241 } |
| 242 } | 242 } |
| 243 } | 243 } |
| 244 | 244 |
| 245 /** | 245 /** |
| 246 * Debugging-only method that uses the list back pointer to check if 'entry'
is indeed in 'this' | 246 * Debugging-only method that uses the list back pointer to check if 'entry'
is indeed in 'this' |
| 247 * list. | 247 * list. |
| 248 */ | 248 */ |
| 249 bool isInList(const T* entry) const { | 249 bool isInList(const T* entry) const { |
| 250 return entry->fList == this; | 250 return entry->fList == this; |
| 251 } | 251 } |
| 252 | 252 |
| 253 /** | 253 /** |
| 254 * Debugging-only method that laboriously counts the list entries. | 254 * Debugging-only method that laboriously counts the list entries. |
| 255 */ | 255 */ |
| 256 int countEntries() const { | 256 int countEntries() const { |
| 257 int count = 0; | 257 int count = 0; |
| 258 for (T* entry = fHead; NULL != entry; entry = entry->fNext) { | 258 for (T* entry = fHead; entry; entry = entry->fNext) { |
| 259 ++count; | 259 ++count; |
| 260 } | 260 } |
| 261 return count; | 261 return count; |
| 262 } | 262 } |
| 263 #endif // SK_DEBUG | 263 #endif // SK_DEBUG |
| 264 | 264 |
| 265 private: | 265 private: |
| 266 T* fHead; | 266 T* fHead; |
| 267 T* fTail; | 267 T* fTail; |
| 268 | 268 |
| 269 typedef SkNoncopyable INHERITED; | 269 typedef SkNoncopyable INHERITED; |
| 270 }; | 270 }; |
| 271 | 271 |
| 272 #endif | 272 #endif |
| OLD | NEW |