/* * Copyright 2012 Google Inc. * * Use of this source code is governed by a BSD-style license that can be * found in the LICENSE file. */ #ifndef SkTLList_DEFINED #define SkTLList_DEFINED #include "include/core/SkTypes.h" #include "include/private/SkMalloc.h" #include "include/private/SkTemplates.h" #include "src/core/SkTInternalLList.h" #include #include /** Doubly-linked list of objects. The objects' lifetimes are controlled by the list. I.e. the the list creates the objects and they are deleted upon removal. This class block-allocates space for entries based on a param passed to the constructor. Elements of the list can be constructed in place using the following macros: SkNEW_INSERT_IN_LLIST_BEFORE(list, location, type_name, args) SkNEW_INSERT_IN_LLIST_AFTER(list, location, type_name, args) where list is a SkTLList*, location is an iterator, and args is the paren-surrounded constructor arguments for type_name. These macros behave like addBefore() and addAfter(). allocCnt is the number of objects to allocate as a group. In the worst case fragmentation each object is using the space required for allocCnt unfragmented objects. */ template class SkTLList { private: struct Block; struct Node { SkAlignedSTStorage<1, T> fObj; SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node); Block* fBlock; // owning block. }; typedef SkTInternalLList NodeList; public: class Iter; // Having fCount initialized to -1 indicates that the first time we attempt to grab a free node // all the nodes in the pre-allocated first block need to be inserted into the free list. This // allows us to skip that loop in instances when the list is never populated. SkTLList() : fCount(-1) {} ~SkTLList() { this->validate(); typename NodeList::Iter iter; Node* node = iter.init(fList, Iter::kHead_IterStart); while (node) { reinterpret_cast(node->fObj.get())->~T(); Block* block = node->fBlock; node = iter.next(); if (0 == --block->fNodesInUse) { for (unsigned int i = 0; i < N; ++i) { block->fNodes[i].~Node(); } if (block != &fFirstBlock) { sk_free(block); } } } } /** Adds a new element to the list at the head. */ template T* addToHead(Args&&... args) { this->validate(); Node* node = this->createNode(); fList.addToHead(node); this->validate(); return new (node->fObj.get()) T(std::forward(args)...); } /** Adds a new element to the list at the tail. */ template T* addToTail(Args&&... args) { this->validate(); Node* node = this->createNode(); fList.addToTail(node); this->validate(); return new (node->fObj.get()) T(std::forward(args)...); } /** Adds a new element to the list before the location indicated by the iterator. If the iterator refers to a nullptr location then the new element is added at the tail */ template T* addBefore(Iter location, Args&&... args) { this->validate(); Node* node = this->createNode(); fList.addBefore(node, location.getNode()); this->validate(); return new (node->fObj.get()) T(std::forward(args)...); } /** Adds a new element to the list after the location indicated by the iterator. If the iterator refers to a nullptr location then the new element is added at the head */ template T* addAfter(Iter location, Args&&... args) { this->validate(); Node* node = this->createNode(); fList.addAfter(node, location.getNode()); this->validate(); return new (node->fObj.get()) T(std::forward(args)...); } /** Convenience methods for getting an iterator initialized to the head/tail of the list. */ Iter headIter() const { return Iter(*this, Iter::kHead_IterStart); } Iter tailIter() const { return Iter(*this, Iter::kTail_IterStart); } T* head() { return Iter(*this, Iter::kHead_IterStart).get(); } T* tail() { return Iter(*this, Iter::kTail_IterStart).get(); } const T* head() const { return Iter(*this, Iter::kHead_IterStart).get(); } const T* tail() const { return Iter(*this, Iter::kTail_IterStart).get(); } void popHead() { this->validate(); Node* node = fList.head(); if (node) { this->removeNode(node); } this->validate(); } void popTail() { this->validate(); Node* node = fList.head(); if (node) { this->removeNode(node); } this->validate(); } void remove(T* t) { this->validate(); Node* node = reinterpret_cast(t); SkASSERT(reinterpret_cast(node->fObj.get()) == t); this->removeNode(node); this->validate(); } void reset() { this->validate(); Iter iter(*this, Iter::kHead_IterStart); while (iter.get()) { Iter next = iter; next.next(); this->remove(iter.get()); iter = next; } SkASSERT(0 == fCount || -1 == fCount); this->validate(); } int count() const { return SkTMax(fCount ,0); } bool isEmpty() const { this->validate(); return 0 == fCount || -1 == fCount; } bool operator== (const SkTLList& list) const { if (this == &list) { return true; } // Call count() rather than use fCount because an empty list may have fCount = 0 or -1. if (this->count() != list.count()) { return false; } for (Iter a(*this, Iter::kHead_IterStart), b(list, Iter::kHead_IterStart); a.get(); a.next(), b.next()) { SkASSERT(b.get()); // already checked that counts match. if (!(*a.get() == *b.get())) { return false; } } return true; } bool operator!= (const SkTLList& list) const { return !(*this == list); } /** The iterator becomes invalid if the element it refers to is removed from the list. */ class Iter : private NodeList::Iter { private: typedef typename NodeList::Iter INHERITED; public: typedef typename INHERITED::IterStart IterStart; //!< Start the iterator at the head of the list. static const IterStart kHead_IterStart = INHERITED::kHead_IterStart; //!< Start the iterator at the tail of the list. static const IterStart kTail_IterStart = INHERITED::kTail_IterStart; Iter() {} Iter(const SkTLList& list, IterStart start = kHead_IterStart) { INHERITED::init(list.fList, start); } T* init(const SkTLList& list, IterStart start = kHead_IterStart) { return this->nodeToObj(INHERITED::init(list.fList, start)); } T* get() { return this->nodeToObj(INHERITED::get()); } T* next() { return this->nodeToObj(INHERITED::next()); } T* prev() { return this->nodeToObj(INHERITED::prev()); } Iter& operator= (const Iter& iter) { INHERITED::operator=(iter); return *this; } private: friend class SkTLList; Node* getNode() { return INHERITED::get(); } T* nodeToObj(Node* node) { if (node) { return reinterpret_cast(node->fObj.get()); } else { return nullptr; } } }; private: struct Block { int fNodesInUse; Node fNodes[N]; }; void delayedInit() { SkASSERT(-1 == fCount); fFirstBlock.fNodesInUse = 0; for (unsigned int i = 0; i < N; ++i) { fFreeList.addToHead(fFirstBlock.fNodes + i); fFirstBlock.fNodes[i].fBlock = &fFirstBlock; } fCount = 0; this->validate(); } Node* createNode() { if (-1 == fCount) { this->delayedInit(); } Node* node = fFreeList.head(); if (node) { fFreeList.remove(node); ++node->fBlock->fNodesInUse; } else { // Should not get here when count == 0 because we always have the preallocated first // block. SkASSERT(fCount > 0); Block* block = reinterpret_cast(sk_malloc_throw(sizeof(Block))); node = &block->fNodes[0]; new (node) Node; node->fBlock = block; block->fNodesInUse = 1; for (unsigned int i = 1; i < N; ++i) { new (block->fNodes + i) Node; fFreeList.addToHead(block->fNodes + i); block->fNodes[i].fBlock = block; } } ++fCount; return node; } void removeNode(Node* node) { SkASSERT(node); fList.remove(node); reinterpret_cast(node->fObj.get())->~T(); Block* block = node->fBlock; // Don't ever elease the first block, just add its nodes to the free list if (0 == --block->fNodesInUse && block != &fFirstBlock) { for (unsigned int i = 0; i < N; ++i) { if (block->fNodes + i != node) { fFreeList.remove(block->fNodes + i); } block->fNodes[i].~Node(); } sk_free(block); } else { fFreeList.addToHead(node); } --fCount; this->validate(); } void validate() const { #ifdef SK_DEBUG bool isEmpty = false; if (-1 == fCount) { // We should not yet have initialized the free list. SkASSERT(fFreeList.isEmpty()); isEmpty = true; } else if (0 == fCount) { // Should only have the nodes from the first block in the free list. SkASSERT(fFreeList.countEntries() == N); isEmpty = true; } SkASSERT(isEmpty == fList.isEmpty()); fList.validate(); fFreeList.validate(); typename NodeList::Iter iter; Node* freeNode = iter.init(fFreeList, Iter::kHead_IterStart); while (freeNode) { SkASSERT(fFreeList.isInList(freeNode)); Block* block = freeNode->fBlock; // Only the first block is allowed to have all its nodes in the free list. SkASSERT(block->fNodesInUse > 0 || block == &fFirstBlock); SkASSERT((unsigned)block->fNodesInUse < N); int activeCnt = 0; int freeCnt = 0; for (unsigned int i = 0; i < N; ++i) { bool free = fFreeList.isInList(block->fNodes + i); bool active = fList.isInList(block->fNodes + i); SkASSERT(free != active); activeCnt += active; freeCnt += free; } SkASSERT(activeCnt == block->fNodesInUse); freeNode = iter.next(); } int count = 0; Node* activeNode = iter.init(fList, Iter::kHead_IterStart); while (activeNode) { ++count; SkASSERT(fList.isInList(activeNode)); Block* block = activeNode->fBlock; SkASSERT(block->fNodesInUse > 0 && (unsigned)block->fNodesInUse <= N); int activeCnt = 0; int freeCnt = 0; for (unsigned int i = 0; i < N; ++i) { bool free = fFreeList.isInList(block->fNodes + i); bool active = fList.isInList(block->fNodes + i); SkASSERT(free != active); activeCnt += active; freeCnt += free; } SkASSERT(activeCnt == block->fNodesInUse); activeNode = iter.next(); } SkASSERT(count == fCount || (0 == count && -1 == fCount)); #endif } NodeList fList; NodeList fFreeList; Block fFirstBlock; int fCount; SkTLList(const SkTLList&) = delete; SkTLList& operator=(const SkTLList&) = delete; }; #endif