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 8 #ifndef SkTLList_DEFINED 9 #define SkTLList_DEFINED 10 11 #include "include/core/SkTypes.h" 12 #include "include/private/SkMalloc.h" 13 #include "include/private/SkTemplates.h" 14 #include "src/core/SkTInternalLList.h" 15 #include <new> 16 #include <utility> 17 18 /** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the 19 the list creates the objects and they are deleted upon removal. This class block-allocates 20 space for entries based on a param passed to the constructor. 21 22 Elements of the list can be constructed in place using the following macros: 23 SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) 24 SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) 25 where list is a SkTLList<type_name>*, location is an iterator, and args is the paren-surrounded 26 constructor arguments for type_name. These macros behave like addBefore() and addAfter(). 27 28 allocCnt is the number of objects to allocate as a group. In the worst case fragmentation 29 each object is using the space required for allocCnt unfragmented objects. 30 */ 31 template <typename T, unsigned int N> class SkTLList { 32 private: 33 struct Block; 34 struct Node { 35 SkAlignedSTStorage<1, T> fObj; 36 SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node); 37 Block* fBlock; // owning block. 38 }; 39 typedef SkTInternalLList<Node> NodeList; 40 41 public: 42 class Iter; 43 44 // Having fCount initialized to -1 indicates that the first time we attempt to grab a free node 45 // all the nodes in the pre-allocated first block need to be inserted into the free list. This 46 // allows us to skip that loop in instances when the list is never populated. SkTLList()47 SkTLList() : fCount(-1) {} 48 ~SkTLList()49 ~SkTLList() { 50 this->validate(); 51 typename NodeList::Iter iter; 52 Node* node = iter.init(fList, Iter::kHead_IterStart); 53 while (node) { 54 reinterpret_cast<T*>(node->fObj.get())->~T(); 55 Block* block = node->fBlock; 56 node = iter.next(); 57 if (0 == --block->fNodesInUse) { 58 for (unsigned int i = 0; i < N; ++i) { 59 block->fNodes[i].~Node(); 60 } 61 if (block != &fFirstBlock) { 62 sk_free(block); 63 } 64 } 65 } 66 } 67 68 /** Adds a new element to the list at the head. */ addToHead(Args &&...args)69 template <typename... Args> T* addToHead(Args&&... args) { 70 this->validate(); 71 Node* node = this->createNode(); 72 fList.addToHead(node); 73 this->validate(); 74 return new (node->fObj.get()) T(std::forward<Args>(args)...); 75 } 76 77 /** Adds a new element to the list at the tail. */ addToTail(Args &&...args)78 template <typename... Args> T* addToTail(Args&&... args) { 79 this->validate(); 80 Node* node = this->createNode(); 81 fList.addToTail(node); 82 this->validate(); 83 return new (node->fObj.get()) T(std::forward<Args>(args)...); 84 } 85 86 /** Adds a new element to the list before the location indicated by the iterator. If the 87 iterator refers to a nullptr location then the new element is added at the tail */ addBefore(Iter location,Args &&...args)88 template <typename... Args> T* addBefore(Iter location, Args&&... args) { 89 this->validate(); 90 Node* node = this->createNode(); 91 fList.addBefore(node, location.getNode()); 92 this->validate(); 93 return new (node->fObj.get()) T(std::forward<Args>(args)...); 94 } 95 96 /** Adds a new element to the list after the location indicated by the iterator. If the 97 iterator refers to a nullptr location then the new element is added at the head */ addAfter(Iter location,Args &&...args)98 template <typename... Args> T* addAfter(Iter location, Args&&... args) { 99 this->validate(); 100 Node* node = this->createNode(); 101 fList.addAfter(node, location.getNode()); 102 this->validate(); 103 return new (node->fObj.get()) T(std::forward<Args>(args)...); 104 } 105 106 /** Convenience methods for getting an iterator initialized to the head/tail of the list. */ headIter()107 Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); } tailIter()108 Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); } 109 head()110 T* head() { return Iter(*this, Iter::kHead_IterStart).get(); } tail()111 T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); } head()112 const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); } tail()113 const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); } 114 popHead()115 void popHead() { 116 this->validate(); 117 Node* node = fList.head(); 118 if (node) { 119 this->removeNode(node); 120 } 121 this->validate(); 122 } 123 popTail()124 void popTail() { 125 this->validate(); 126 Node* node = fList.head(); 127 if (node) { 128 this->removeNode(node); 129 } 130 this->validate(); 131 } 132 remove(T * t)133 void remove(T* t) { 134 this->validate(); 135 Node* node = reinterpret_cast<Node*>(t); 136 SkASSERT(reinterpret_cast<T*>(node->fObj.get()) == t); 137 this->removeNode(node); 138 this->validate(); 139 } 140 reset()141 void reset() { 142 this->validate(); 143 Iter iter(*this, Iter::kHead_IterStart); 144 while (iter.get()) { 145 Iter next = iter; 146 next.next(); 147 this->remove(iter.get()); 148 iter = next; 149 } 150 SkASSERT(0 == fCount || -1 == fCount); 151 this->validate(); 152 } 153 count()154 int count() const { return SkTMax(fCount ,0); } isEmpty()155 bool isEmpty() const { this->validate(); return 0 == fCount || -1 == fCount; } 156 157 bool operator== (const SkTLList& list) const { 158 if (this == &list) { 159 return true; 160 } 161 // Call count() rather than use fCount because an empty list may have fCount = 0 or -1. 162 if (this->count() != list.count()) { 163 return false; 164 } 165 for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart); 166 a.get(); 167 a.next(), b.next()) { 168 SkASSERT(b.get()); // already checked that counts match. 169 if (!(*a.get() == *b.get())) { 170 return false; 171 } 172 } 173 return true; 174 } 175 bool operator!= (const SkTLList& list) const { return !(*this == list); } 176 177 /** The iterator becomes invalid if the element it refers to is removed from the list. */ 178 class Iter : private NodeList::Iter { 179 private: 180 typedef typename NodeList::Iter INHERITED; 181 182 public: 183 typedef typename INHERITED::IterStart IterStart; 184 //!< Start the iterator at the head of the list. 185 static const IterStart kHead_IterStart = INHERITED::kHead_IterStart; 186 //!< Start the iterator at the tail of the list. 187 static const IterStart kTail_IterStart = INHERITED::kTail_IterStart; 188 Iter()189 Iter() {} 190 191 Iter(const SkTLList& list, IterStart start = kHead_IterStart) { 192 INHERITED::init(list.fList, start); 193 } 194 195 T* init(const SkTLList& list, IterStart start = kHead_IterStart) { 196 return this->nodeToObj(INHERITED::init(list.fList, start)); 197 } 198 get()199 T* get() { return this->nodeToObj(INHERITED::get()); } 200 next()201 T* next() { return this->nodeToObj(INHERITED::next()); } 202 prev()203 T* prev() { return this->nodeToObj(INHERITED::prev()); } 204 205 Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; } 206 207 private: 208 friend class SkTLList; getNode()209 Node* getNode() { return INHERITED::get(); } 210 nodeToObj(Node * node)211 T* nodeToObj(Node* node) { 212 if (node) { 213 return reinterpret_cast<T*>(node->fObj.get()); 214 } else { 215 return nullptr; 216 } 217 } 218 }; 219 220 private: 221 struct Block { 222 int fNodesInUse; 223 Node fNodes[N]; 224 }; 225 delayedInit()226 void delayedInit() { 227 SkASSERT(-1 == fCount); 228 fFirstBlock.fNodesInUse = 0; 229 for (unsigned int i = 0; i < N; ++i) { 230 fFreeList.addToHead(fFirstBlock.fNodes + i); 231 fFirstBlock.fNodes[i].fBlock = &fFirstBlock; 232 } 233 fCount = 0; 234 this->validate(); 235 } 236 createNode()237 Node* createNode() { 238 if (-1 == fCount) { 239 this->delayedInit(); 240 } 241 Node* node = fFreeList.head(); 242 if (node) { 243 fFreeList.remove(node); 244 ++node->fBlock->fNodesInUse; 245 } else { 246 // Should not get here when count == 0 because we always have the preallocated first 247 // block. 248 SkASSERT(fCount > 0); 249 Block* block = reinterpret_cast<Block*>(sk_malloc_throw(sizeof(Block))); 250 node = &block->fNodes[0]; 251 new (node) Node; 252 node->fBlock = block; 253 block->fNodesInUse = 1; 254 for (unsigned int i = 1; i < N; ++i) { 255 new (block->fNodes + i) Node; 256 fFreeList.addToHead(block->fNodes + i); 257 block->fNodes[i].fBlock = block; 258 } 259 } 260 ++fCount; 261 return node; 262 } 263 removeNode(Node * node)264 void removeNode(Node* node) { 265 SkASSERT(node); 266 fList.remove(node); 267 reinterpret_cast<T*>(node->fObj.get())->~T(); 268 Block* block = node->fBlock; 269 // Don't ever elease the first block, just add its nodes to the free list 270 if (0 == --block->fNodesInUse && block != &fFirstBlock) { 271 for (unsigned int i = 0; i < N; ++i) { 272 if (block->fNodes + i != node) { 273 fFreeList.remove(block->fNodes + i); 274 } 275 block->fNodes[i].~Node(); 276 } 277 sk_free(block); 278 } else { 279 fFreeList.addToHead(node); 280 } 281 --fCount; 282 this->validate(); 283 } 284 validate()285 void validate() const { 286 #ifdef SK_DEBUG 287 bool isEmpty = false; 288 if (-1 == fCount) { 289 // We should not yet have initialized the free list. 290 SkASSERT(fFreeList.isEmpty()); 291 isEmpty = true; 292 } else if (0 == fCount) { 293 // Should only have the nodes from the first block in the free list. 294 SkASSERT(fFreeList.countEntries() == N); 295 isEmpty = true; 296 } 297 SkASSERT(isEmpty == fList.isEmpty()); 298 fList.validate(); 299 fFreeList.validate(); 300 typename NodeList::Iter iter; 301 Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart); 302 while (freeNode) { 303 SkASSERT(fFreeList.isInList(freeNode)); 304 Block* block = freeNode->fBlock; 305 // Only the first block is allowed to have all its nodes in the free list. 306 SkASSERT(block->fNodesInUse > 0 || block == &fFirstBlock); 307 SkASSERT((unsigned)block->fNodesInUse < N); 308 int activeCnt = 0; 309 int freeCnt = 0; 310 for (unsigned int i = 0; i < N; ++i) { 311 bool free = fFreeList.isInList(block->fNodes + i); 312 bool active = fList.isInList(block->fNodes + i); 313 SkASSERT(free != active); 314 activeCnt += active; 315 freeCnt += free; 316 } 317 SkASSERT(activeCnt == block->fNodesInUse); 318 freeNode = iter.next(); 319 } 320 321 int count = 0; 322 Node* activeNode = iter.init(fList, Iter::kHead_IterStart); 323 while (activeNode) { 324 ++count; 325 SkASSERT(fList.isInList(activeNode)); 326 Block* block = activeNode->fBlock; 327 SkASSERT(block->fNodesInUse > 0 && (unsigned)block->fNodesInUse <= N); 328 329 int activeCnt = 0; 330 int freeCnt = 0; 331 for (unsigned int i = 0; i < N; ++i) { 332 bool free = fFreeList.isInList(block->fNodes + i); 333 bool active = fList.isInList(block->fNodes + i); 334 SkASSERT(free != active); 335 activeCnt += active; 336 freeCnt += free; 337 } 338 SkASSERT(activeCnt == block->fNodesInUse); 339 activeNode = iter.next(); 340 } 341 SkASSERT(count == fCount || (0 == count && -1 == fCount)); 342 #endif 343 } 344 345 NodeList fList; 346 NodeList fFreeList; 347 Block fFirstBlock; 348 int fCount; 349 350 SkTLList(const SkTLList&) = delete; 351 SkTLList& operator=(const SkTLList&) = delete; 352 }; 353 354 #endif 355