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 "SkTInternalLList.h" 12 #include "SkTypes.h" 13 #include <utility> 14 15 /** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the 16 the list creates the objects and they are deleted upon removal. This class block-allocates 17 space for entries based on a param passed to the constructor. 18 19 Elements of the list can be constructed in place using the following macros: 20 SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) 21 SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) 22 where list is a SkTLList<type_name>*, location is an iterator, and args is the paren-surrounded 23 constructor arguments for type_name. These macros behave like addBefore() and addAfter(). 24 25 allocCnt is the number of objects to allocate as a group. In the worst case fragmentation 26 each object is using the space required for allocCnt unfragmented objects. 27 */ 28 template <typename T, unsigned int N> class SkTLList : SkNoncopyable { 29 private: 30 struct Block; 31 struct Node { 32 char fObj[sizeof(T)]; 33 SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node); 34 Block* fBlock; // owning block. 35 }; 36 typedef SkTInternalLList<Node> NodeList; 37 38 public: 39 class Iter; 40 41 SkTLList() : fCount(0) { 42 fFirstBlock.fNodesInUse = 0; 43 for (unsigned int i = 0; i < N; ++i) { 44 fFreeList.addToHead(fFirstBlock.fNodes + i); 45 fFirstBlock.fNodes[i].fBlock = &fFirstBlock; 46 } 47 this->validate(); 48 } 49 50 ~SkTLList() { 51 this->validate(); 52 typename NodeList::Iter iter; 53 Node* node = iter.init(fList, Iter::kHead_IterStart); 54 while (node) { 55 SkTCast<T*>(node->fObj)->~T(); 56 Block* block = node->fBlock; 57 node = iter.next(); 58 if (0 == --block->fNodesInUse) { 59 for (unsigned int i = 0; i < N; ++i) { 60 block->fNodes[i].~Node(); 61 } 62 if (block != &fFirstBlock) { 63 sk_free(block); 64 } 65 } 66 } 67 } 68 69 /** Adds a new element to the list at the head. */ 70 template <typename... Args> T* addToHead(Args&&... args) { 71 this->validate(); 72 Node* node = this->createNode(); 73 fList.addToHead(node); 74 this->validate(); 75 return new (node->fObj) T(std::forward<Args>(args)...); 76 } 77 78 /** Adds a new element to the list at the tail. */ 79 template <typename... Args> T* addToTail(Args&&... args) { 80 this->validate(); 81 Node* node = this->createNode(); 82 fList.addToTail(node); 83 this->validate(); 84 return new (node->fObj) T(std::forward<Args>(args)...); 85 } 86 87 /** Adds a new element to the list before the location indicated by the iterator. If the 88 iterator refers to a nullptr location then the new element is added at the tail */ 89 template <typename... Args> T* addBefore(Iter location, Args&&... args) { 90 this->validate(); 91 Node* node = this->createNode(); 92 fList.addBefore(node, location.getNode()); 93 this->validate(); 94 return new (node->fObj) T(std::forward<Args>(args)...); 95 } 96 97 /** Adds a new element to the list after the location indicated by the iterator. If the 98 iterator refers to a nullptr location then the new element is added at the head */ 99 template <typename... Args> T* addAfter(Iter location, Args&&... args) { 100 this->validate(); 101 Node* node = this->createNode(); 102 fList.addAfter(node, location.getNode()); 103 this->validate(); 104 return new (node->fObj) T(std::forward<Args>(args)...); 105 } 106 107 /** Convenience methods for getting an iterator initialized to the head/tail of the list. */ 108 Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); } 109 Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); } 110 111 T* head() { return Iter(*this, Iter::kHead_IterStart).get(); } 112 T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); } 113 const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); } 114 const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); } 115 116 void popHead() { 117 this->validate(); 118 Node* node = fList.head(); 119 if (node) { 120 this->removeNode(node); 121 } 122 this->validate(); 123 } 124 125 void popTail() { 126 this->validate(); 127 Node* node = fList.head(); 128 if (node) { 129 this->removeNode(node); 130 } 131 this->validate(); 132 } 133 134 void remove(T* t) { 135 this->validate(); 136 Node* node = reinterpret_cast<Node*>(t); 137 SkASSERT(reinterpret_cast<T*>(node->fObj) == t); 138 this->removeNode(node); 139 this->validate(); 140 } 141 142 void reset() { 143 this->validate(); 144 Iter iter(*this, Iter::kHead_IterStart); 145 while (iter.get()) { 146 Iter next = iter; 147 next.next(); 148 this->remove(iter.get()); 149 iter = next; 150 } 151 SkASSERT(0 == fCount); 152 this->validate(); 153 } 154 155 int count() const { return fCount; } 156 bool isEmpty() const { this->validate(); return 0 == fCount; } 157 158 bool operator== (const SkTLList& list) const { 159 if (this == &list) { 160 return true; 161 } 162 if (fCount != list.fCount) { 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 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 199 T* get() { return this->nodeToObj(INHERITED::get()); } 200 201 T* next() { return this->nodeToObj(INHERITED::next()); } 202 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; 209 Node* getNode() { return INHERITED::get(); } 210 211 T* nodeToObj(Node* node) { 212 if (node) { 213 return reinterpret_cast<T*>(node->fObj); 214 } else { 215 return nullptr; 216 } 217 } 218 }; 219 220 private: 221 struct Block { 222 int fNodesInUse; 223 Node fNodes[N]; 224 }; 225 226 Node* createNode() { 227 Node* node = fFreeList.head(); 228 if (node) { 229 fFreeList.remove(node); 230 ++node->fBlock->fNodesInUse; 231 } else { 232 // Should not get here when count == 0 because we always have the preallocated first 233 // block. 234 SkASSERT(fCount > 0); 235 Block* block = reinterpret_cast<Block*>(sk_malloc_throw(sizeof(Block))); 236 node = &block->fNodes[0]; 237 new (node) Node; 238 node->fBlock = block; 239 block->fNodesInUse = 1; 240 for (unsigned int i = 1; i < N; ++i) { 241 new (block->fNodes + i) Node; 242 fFreeList.addToHead(block->fNodes + i); 243 block->fNodes[i].fBlock = block; 244 } 245 } 246 ++fCount; 247 return node; 248 } 249 250 void removeNode(Node* node) { 251 SkASSERT(node); 252 fList.remove(node); 253 SkTCast<T*>(node->fObj)->~T(); 254 Block* block = node->fBlock; 255 // Don't ever elease the first block, just add its nodes to the free list 256 if (0 == --block->fNodesInUse && block != &fFirstBlock) { 257 for (unsigned int i = 0; i < N; ++i) { 258 if (block->fNodes + i != node) { 259 fFreeList.remove(block->fNodes + i); 260 } 261 block->fNodes[i].~Node(); 262 } 263 sk_free(block); 264 } else { 265 fFreeList.addToHead(node); 266 } 267 --fCount; 268 this->validate(); 269 } 270 271 void validate() const { 272 #ifdef SK_DEBUG 273 SkASSERT((0 == fCount) == fList.isEmpty()); 274 if (0 == fCount) { 275 // Should only have the nodes from the first block in the free list. 276 SkASSERT(fFreeList.countEntries() == N); 277 } 278 fList.validate(); 279 fFreeList.validate(); 280 typename NodeList::Iter iter; 281 Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart); 282 while (freeNode) { 283 SkASSERT(fFreeList.isInList(freeNode)); 284 Block* block = freeNode->fBlock; 285 // Only the first block is allowed to have all its nodes in the free list. 286 SkASSERT(block->fNodesInUse > 0 || block == &fFirstBlock); 287 SkASSERT((unsigned)block->fNodesInUse < N); 288 int activeCnt = 0; 289 int freeCnt = 0; 290 for (unsigned int i = 0; i < N; ++i) { 291 bool free = fFreeList.isInList(block->fNodes + i); 292 bool active = fList.isInList(block->fNodes + i); 293 SkASSERT(free != active); 294 activeCnt += active; 295 freeCnt += free; 296 } 297 SkASSERT(activeCnt == block->fNodesInUse); 298 freeNode = iter.next(); 299 } 300 301 int count = 0; 302 Node* activeNode = iter.init(fList, Iter::kHead_IterStart); 303 while (activeNode) { 304 ++count; 305 SkASSERT(fList.isInList(activeNode)); 306 Block* block = activeNode->fBlock; 307 SkASSERT(block->fNodesInUse > 0 && (unsigned)block->fNodesInUse <= N); 308 309 int activeCnt = 0; 310 int freeCnt = 0; 311 for (unsigned int i = 0; i < N; ++i) { 312 bool free = fFreeList.isInList(block->fNodes + i); 313 bool active = fList.isInList(block->fNodes + i); 314 SkASSERT(free != active); 315 activeCnt += active; 316 freeCnt += free; 317 } 318 SkASSERT(activeCnt == block->fNodesInUse); 319 activeNode = iter.next(); 320 } 321 SkASSERT(count == fCount); 322 #endif 323 } 324 325 NodeList fList; 326 NodeList fFreeList; 327 Block fFirstBlock; 328 int fCount; 329 }; 330 331 #endif 332
