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 SkTLList_DEFINED | 8 #ifndef SkTLList_DEFINED |
9 #define SkTLList_DEFINED | 9 #define SkTLList_DEFINED |
10 | 10 |
(...skipping 35 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
46 each object is using the space required for allocCnt unfragmented object
s. */ | 46 each object is using the space required for allocCnt unfragmented object
s. */ |
47 SkTLList(int allocCnt = 1) : fCount(0), fAllocCnt(allocCnt) { | 47 SkTLList(int allocCnt = 1) : fCount(0), fAllocCnt(allocCnt) { |
48 SkASSERT(allocCnt > 0); | 48 SkASSERT(allocCnt > 0); |
49 this->validate(); | 49 this->validate(); |
50 } | 50 } |
51 | 51 |
52 ~SkTLList() { | 52 ~SkTLList() { |
53 this->validate(); | 53 this->validate(); |
54 typename NodeList::Iter iter; | 54 typename NodeList::Iter iter; |
55 Node* node = iter.init(fList, Iter::kHead_IterStart); | 55 Node* node = iter.init(fList, Iter::kHead_IterStart); |
56 while (NULL != node) { | 56 while (node) { |
57 SkTCast<T*>(node->fObj)->~T(); | 57 SkTCast<T*>(node->fObj)->~T(); |
58 Block* block = node->fBlock; | 58 Block* block = node->fBlock; |
59 node = iter.next(); | 59 node = iter.next(); |
60 if (0 == --block->fNodesInUse) { | 60 if (0 == --block->fNodesInUse) { |
61 for (int i = 0; i < fAllocCnt; ++i) { | 61 for (int i = 0; i < fAllocCnt; ++i) { |
62 block->fNodes[i].~Node(); | 62 block->fNodes[i].~Node(); |
63 } | 63 } |
64 sk_free(block); | 64 sk_free(block); |
65 } | 65 } |
66 } | 66 } |
(...skipping 52 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
119 Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); } | 119 Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); } |
120 | 120 |
121 T* head() { return Iter(*this, Iter::kHead_IterStart).get(); } | 121 T* head() { return Iter(*this, Iter::kHead_IterStart).get(); } |
122 T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); } | 122 T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); } |
123 const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); } | 123 const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); } |
124 const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); } | 124 const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); } |
125 | 125 |
126 void popHead() { | 126 void popHead() { |
127 this->validate(); | 127 this->validate(); |
128 Node* node = fList.head(); | 128 Node* node = fList.head(); |
129 if (NULL != node) { | 129 if (node) { |
130 this->removeNode(node); | 130 this->removeNode(node); |
131 } | 131 } |
132 this->validate(); | 132 this->validate(); |
133 } | 133 } |
134 | 134 |
135 void popTail() { | 135 void popTail() { |
136 this->validate(); | 136 this->validate(); |
137 Node* node = fList.head(); | 137 Node* node = fList.head(); |
138 if (NULL != node) { | 138 if (node) { |
139 this->removeNode(node); | 139 this->removeNode(node); |
140 } | 140 } |
141 this->validate(); | 141 this->validate(); |
142 } | 142 } |
143 | 143 |
144 void remove(T* t) { | 144 void remove(T* t) { |
145 this->validate(); | 145 this->validate(); |
146 Node* node = reinterpret_cast<Node*>(t); | 146 Node* node = reinterpret_cast<Node*>(t); |
147 SkASSERT(reinterpret_cast<T*>(node->fObj) == t); | 147 SkASSERT(reinterpret_cast<T*>(node->fObj) == t); |
148 this->removeNode(node); | 148 this->removeNode(node); |
(...skipping 19 matching lines...) Expand all Loading... |
168 bool operator== (const SkTLList& list) const { | 168 bool operator== (const SkTLList& list) const { |
169 if (this == &list) { | 169 if (this == &list) { |
170 return true; | 170 return true; |
171 } | 171 } |
172 if (fCount != list.fCount) { | 172 if (fCount != list.fCount) { |
173 return false; | 173 return false; |
174 } | 174 } |
175 for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart
); | 175 for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart
); |
176 a.get(); | 176 a.get(); |
177 a.next(), b.next()) { | 177 a.next(), b.next()) { |
178 SkASSERT(NULL != b.get()); // already checked that counts match. | 178 SkASSERT(b.get()); // already checked that counts match. |
179 if (!(*a.get() == *b.get())) { | 179 if (!(*a.get() == *b.get())) { |
180 return false; | 180 return false; |
181 } | 181 } |
182 } | 182 } |
183 return true; | 183 return true; |
184 } | 184 } |
185 bool operator!= (const SkTLList& list) const { return !(*this == list); } | 185 bool operator!= (const SkTLList& list) const { return !(*this == list); } |
186 | 186 |
187 /** The iterator becomes invalid if the element it refers to is removed from
the list. */ | 187 /** The iterator becomes invalid if the element it refers to is removed from
the list. */ |
188 class Iter : private NodeList::Iter { | 188 class Iter : private NodeList::Iter { |
(...skipping 23 matching lines...) Expand all Loading... |
212 | 212 |
213 T* prev() { return this->nodeToObj(INHERITED::prev()); } | 213 T* prev() { return this->nodeToObj(INHERITED::prev()); } |
214 | 214 |
215 Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return
*this; } | 215 Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return
*this; } |
216 | 216 |
217 private: | 217 private: |
218 friend class SkTLList; | 218 friend class SkTLList; |
219 Node* getNode() { return INHERITED::get(); } | 219 Node* getNode() { return INHERITED::get(); } |
220 | 220 |
221 T* nodeToObj(Node* node) { | 221 T* nodeToObj(Node* node) { |
222 if (NULL != node) { | 222 if (node) { |
223 return reinterpret_cast<T*>(node->fObj); | 223 return reinterpret_cast<T*>(node->fObj); |
224 } else { | 224 } else { |
225 return NULL; | 225 return NULL; |
226 } | 226 } |
227 } | 227 } |
228 }; | 228 }; |
229 | 229 |
230 // For use with operator new | 230 // For use with operator new |
231 enum Placement { | 231 enum Placement { |
232 kBefore_Placement, | 232 kBefore_Placement, |
233 kAfter_Placement, | 233 kAfter_Placement, |
234 }; | 234 }; |
235 | 235 |
236 private: | 236 private: |
237 struct Block { | 237 struct Block { |
238 int fNodesInUse; | 238 int fNodesInUse; |
239 Node fNodes[1]; | 239 Node fNodes[1]; |
240 }; | 240 }; |
241 | 241 |
242 size_t blockSize() const { return sizeof(Block) + sizeof(Node) * (fAllocCnt-
1); } | 242 size_t blockSize() const { return sizeof(Block) + sizeof(Node) * (fAllocCnt-
1); } |
243 | 243 |
244 Node* createNode() { | 244 Node* createNode() { |
245 Node* node = fFreeList.head(); | 245 Node* node = fFreeList.head(); |
246 if (NULL != node) { | 246 if (node) { |
247 fFreeList.remove(node); | 247 fFreeList.remove(node); |
248 ++node->fBlock->fNodesInUse; | 248 ++node->fBlock->fNodesInUse; |
249 } else { | 249 } else { |
250 Block* block = reinterpret_cast<Block*>(sk_malloc_flags(this->blockS
ize(), 0)); | 250 Block* block = reinterpret_cast<Block*>(sk_malloc_flags(this->blockS
ize(), 0)); |
251 node = &block->fNodes[0]; | 251 node = &block->fNodes[0]; |
252 SkNEW_PLACEMENT(node, Node); | 252 SkNEW_PLACEMENT(node, Node); |
253 node->fBlock = block; | 253 node->fBlock = block; |
254 block->fNodesInUse = 1; | 254 block->fNodesInUse = 1; |
255 for (int i = 1; i < fAllocCnt; ++i) { | 255 for (int i = 1; i < fAllocCnt; ++i) { |
256 SkNEW_PLACEMENT(block->fNodes + i, Node); | 256 SkNEW_PLACEMENT(block->fNodes + i, Node); |
257 fFreeList.addToHead(block->fNodes + i); | 257 fFreeList.addToHead(block->fNodes + i); |
258 block->fNodes[i].fBlock = block; | 258 block->fNodes[i].fBlock = block; |
259 } | 259 } |
260 } | 260 } |
261 ++fCount; | 261 ++fCount; |
262 return node; | 262 return node; |
263 } | 263 } |
264 | 264 |
265 void removeNode(Node* node) { | 265 void removeNode(Node* node) { |
266 SkASSERT(NULL != node); | 266 SkASSERT(node); |
267 fList.remove(node); | 267 fList.remove(node); |
268 SkTCast<T*>(node->fObj)->~T(); | 268 SkTCast<T*>(node->fObj)->~T(); |
269 if (0 == --node->fBlock->fNodesInUse) { | 269 if (0 == --node->fBlock->fNodesInUse) { |
270 Block* block = node->fBlock; | 270 Block* block = node->fBlock; |
271 for (int i = 0; i < fAllocCnt; ++i) { | 271 for (int i = 0; i < fAllocCnt; ++i) { |
272 if (block->fNodes + i != node) { | 272 if (block->fNodes + i != node) { |
273 fFreeList.remove(block->fNodes + i); | 273 fFreeList.remove(block->fNodes + i); |
274 } | 274 } |
275 block->fNodes[i].~Node(); | 275 block->fNodes[i].~Node(); |
276 } | 276 } |
(...skipping 85 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
362 int fCount; | 362 int fCount; |
363 int fAllocCnt; | 363 int fAllocCnt; |
364 | 364 |
365 }; | 365 }; |
366 | 366 |
367 // Use the below macros rather than calling this directly | 367 // Use the below macros rather than calling this directly |
368 template <typename T> | 368 template <typename T> |
369 void *operator new(size_t, SkTLList<T>* list, | 369 void *operator new(size_t, SkTLList<T>* list, |
370 typename SkTLList<T>::Placement placement, | 370 typename SkTLList<T>::Placement placement, |
371 const typename SkTLList<T>::Iter& location) { | 371 const typename SkTLList<T>::Iter& location) { |
372 SkASSERT(NULL != list); | 372 SkASSERT(list); |
373 if (SkTLList<T>::kBefore_Placement == placement) { | 373 if (SkTLList<T>::kBefore_Placement == placement) { |
374 return list->internalAddBefore(location); | 374 return list->internalAddBefore(location); |
375 } else { | 375 } else { |
376 return list->internalAddAfter(location); | 376 return list->internalAddAfter(location); |
377 } | 377 } |
378 } | 378 } |
379 | 379 |
380 // Skia doesn't use C++ exceptions but it may be compiled with them enabled. Hav
ing an op delete | 380 // Skia doesn't use C++ exceptions but it may be compiled with them enabled. Hav
ing an op delete |
381 // to match the op new silences warnings about missing op delete when a construc
tor throws an | 381 // to match the op new silences warnings about missing op delete when a construc
tor throws an |
382 // exception. | 382 // exception. |
(...skipping 11 matching lines...) Expand all Loading... |
394 #define SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) \ | 394 #define SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) \ |
395 (new ((list), SkTLList< type_name >::kAfter_Placement, (location)) type_name
args) | 395 (new ((list), SkTLList< type_name >::kAfter_Placement, (location)) type_name
args) |
396 | 396 |
397 #define SkNEW_INSERT_AT_LLIST_HEAD(list, type_name, args) \ | 397 #define SkNEW_INSERT_AT_LLIST_HEAD(list, type_name, args) \ |
398 SkNEW_INSERT_IN_LLIST_BEFORE((list), (list)->headIter(), type_name, args) | 398 SkNEW_INSERT_IN_LLIST_BEFORE((list), (list)->headIter(), type_name, args) |
399 | 399 |
400 #define SkNEW_INSERT_AT_LLIST_TAIL(list, type_name, args) \ | 400 #define SkNEW_INSERT_AT_LLIST_TAIL(list, type_name, args) \ |
401 SkNEW_INSERT_IN_LLIST_AFTER((list), (list)->tailIter(), type_name, args) | 401 SkNEW_INSERT_IN_LLIST_AFTER((list), (list)->tailIter(), type_name, args) |
402 | 402 |
403 #endif | 403 #endif |
OLD | NEW |