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 |