| 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 |