/*
|
* 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 "SkMalloc.h"
|
#include "SkTInternalLList.h"
|
#include "SkTemplates.h"
|
#include "SkTypes.h"
|
#include <new>
|
#include <utility>
|
|
/** 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<type_name>*, 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 <typename T, unsigned int N> class SkTLList : SkNoncopyable {
|
private:
|
struct Block;
|
struct Node {
|
SkAlignedSTStorage<1, T> fObj;
|
SK_DECLARE_INTERNAL_LLIST_INTERFACE(Node);
|
Block* fBlock; // owning block.
|
};
|
typedef SkTInternalLList<Node> 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<T*>(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 <typename... Args> T* addToHead(Args&&... args) {
|
this->validate();
|
Node* node = this->createNode();
|
fList.addToHead(node);
|
this->validate();
|
return new (node->fObj.get()) T(std::forward<Args>(args)...);
|
}
|
|
/** Adds a new element to the list at the tail. */
|
template <typename... Args> T* addToTail(Args&&... args) {
|
this->validate();
|
Node* node = this->createNode();
|
fList.addToTail(node);
|
this->validate();
|
return new (node->fObj.get()) T(std::forward<Args>(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 <typename... Args> 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>(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 <typename... Args> 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>(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<Node*>(t);
|
SkASSERT(reinterpret_cast<T*>(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<T*>(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<Block*>(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<T*>(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;
|
};
|
|
#endif
|
