blob: 547befe6943e8b6034dc81bced8d2d1d24c047bb [file] [log] [blame]
/*
* 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 SkTInternalLList_DEFINED
#define SkTInternalLList_DEFINED
#include "../private/SkNoncopyable.h"
#include "SkTypes.h"
/**
* Helper class to automatically initialize the doubly linked list created pointers.
*/
template <typename T> class SkPtrWrapper {
public:
SkPtrWrapper() : fPtr(nullptr) {}
SkPtrWrapper& operator =(T* ptr) { fPtr = ptr; return *this; }
operator T*() const { return fPtr; }
T* operator->() { return fPtr; }
private:
T* fPtr;
};
/**
* This macro creates the member variables required by the SkTInternalLList class. It should be
* placed in the private section of any class that will be stored in a double linked list.
*/
#define SK_DECLARE_INTERNAL_LLIST_INTERFACE(ClassName) \
friend class SkTInternalLList<ClassName>; \
/* back pointer to the owning list - for debugging */ \
SkDEBUGCODE(SkPtrWrapper<SkTInternalLList<ClassName> > fList;) \
SkPtrWrapper<ClassName> fPrev; \
SkPtrWrapper<ClassName> fNext
/**
* This class implements a templated internal doubly linked list data structure.
*/
template <class T> class SkTInternalLList : SkNoncopyable {
public:
SkTInternalLList()
: fHead(nullptr)
, fTail(nullptr) {
}
void reset() {
fHead = nullptr;
fTail = nullptr;
}
void remove(T* entry) {
SkASSERT(fHead && fTail);
SkASSERT(this->isInList(entry));
T* prev = entry->fPrev;
T* next = entry->fNext;
if (prev) {
prev->fNext = next;
} else {
fHead = next;
}
if (next) {
next->fPrev = prev;
} else {
fTail = prev;
}
entry->fPrev = nullptr;
entry->fNext = nullptr;
#ifdef SK_DEBUG
entry->fList = nullptr;
#endif
}
void addToHead(T* entry) {
SkASSERT(nullptr == entry->fPrev && nullptr == entry->fNext);
SkASSERT(nullptr == entry->fList);
entry->fPrev = nullptr;
entry->fNext = fHead;
if (fHead) {
fHead->fPrev = entry;
}
fHead = entry;
if (nullptr == fTail) {
fTail = entry;
}
#ifdef SK_DEBUG
entry->fList = this;
#endif
}
void addToTail(T* entry) {
SkASSERT(nullptr == entry->fPrev && nullptr == entry->fNext);
SkASSERT(nullptr == entry->fList);
entry->fPrev = fTail;
entry->fNext = nullptr;
if (fTail) {
fTail->fNext = entry;
}
fTail = entry;
if (nullptr == fHead) {
fHead = entry;
}
#ifdef SK_DEBUG
entry->fList = this;
#endif
}
/**
* Inserts a new list entry before an existing list entry. The new entry must not already be
* a member of this or any other list. If existingEntry is NULL then the new entry is added
* at the tail.
*/
void addBefore(T* newEntry, T* existingEntry) {
SkASSERT(newEntry);
if (nullptr == existingEntry) {
this->addToTail(newEntry);
return;
}
SkASSERT(this->isInList(existingEntry));
newEntry->fNext = existingEntry;
T* prev = existingEntry->fPrev;
existingEntry->fPrev = newEntry;
newEntry->fPrev = prev;
if (nullptr == prev) {
SkASSERT(fHead == existingEntry);
fHead = newEntry;
} else {
prev->fNext = newEntry;
}
#ifdef SK_DEBUG
newEntry->fList = this;
#endif
}
/**
* Inserts a new list entry after an existing list entry. The new entry must not already be
* a member of this or any other list. If existingEntry is NULL then the new entry is added
* at the head.
*/
void addAfter(T* newEntry, T* existingEntry) {
SkASSERT(newEntry);
if (nullptr == existingEntry) {
this->addToHead(newEntry);
return;
}
SkASSERT(this->isInList(existingEntry));
newEntry->fPrev = existingEntry;
T* next = existingEntry->fNext;
existingEntry->fNext = newEntry;
newEntry->fNext = next;
if (nullptr == next) {
SkASSERT(fTail == existingEntry);
fTail = newEntry;
} else {
next->fPrev = newEntry;
}
#ifdef SK_DEBUG
newEntry->fList = this;
#endif
}
void concat(SkTInternalLList&& list) {
if (list.isEmpty()) {
return;
}
list.fHead->fPrev = fTail;
if (!fHead) {
SkASSERT(!list.fHead->fPrev);
fHead = list.fHead;
} else {
SkASSERT(fTail);
fTail->fNext = list.fHead;
}
fTail = list.fTail;
#ifdef SK_DEBUG
for (T* node = list.fHead; node; node = node->fNext) {
SkASSERT(node->fList == &list);
node->fList = this;
}
#endif
list.fHead = list.fTail = nullptr;
}
bool isEmpty() const {
SkASSERT(SkToBool(fHead) == SkToBool(fTail));
return !fHead;
}
T* head() { return fHead; }
T* tail() { return fTail; }
class Iter {
public:
enum IterStart {
kHead_IterStart,
kTail_IterStart
};
Iter() : fCurr(nullptr) {}
Iter(const Iter& iter) : fCurr(iter.fCurr) {}
Iter& operator= (const Iter& iter) { fCurr = iter.fCurr; return *this; }
T* init(const SkTInternalLList& list, IterStart startLoc) {
if (kHead_IterStart == startLoc) {
fCurr = list.fHead;
} else {
SkASSERT(kTail_IterStart == startLoc);
fCurr = list.fTail;
}
return fCurr;
}
T* get() { return fCurr; }
/**
* Return the next/previous element in the list or NULL if at the end.
*/
T* next() {
if (nullptr == fCurr) {
return nullptr;
}
fCurr = fCurr->fNext;
return fCurr;
}
T* prev() {
if (nullptr == fCurr) {
return nullptr;
}
fCurr = fCurr->fPrev;
return fCurr;
}
/**
* C++11 range-for interface.
*/
bool operator!=(const Iter& that) { return fCurr != that.fCurr; }
T* operator*() { return this->get(); }
void operator++() { this->next(); }
private:
T* fCurr;
};
Iter begin() const {
Iter iter;
iter.init(*this, Iter::kHead_IterStart);
return iter;
}
Iter end() const { return Iter(); }
#ifdef SK_DEBUG
void validate() const {
SkASSERT(!fHead == !fTail);
Iter iter;
for (T* item = iter.init(*this, Iter::kHead_IterStart); item; item = iter.next()) {
SkASSERT(this->isInList(item));
if (nullptr == item->fPrev) {
SkASSERT(fHead == item);
} else {
SkASSERT(item->fPrev->fNext == item);
}
if (nullptr == item->fNext) {
SkASSERT(fTail == item);
} else {
SkASSERT(item->fNext->fPrev == item);
}
}
}
/**
* Debugging-only method that uses the list back pointer to check if 'entry' is indeed in 'this'
* list.
*/
bool isInList(const T* entry) const {
return entry->fList == this;
}
/**
* Debugging-only method that laboriously counts the list entries.
*/
int countEntries() const {
int count = 0;
for (T* entry = fHead; entry; entry = entry->fNext) {
++count;
}
return count;
}
#endif // SK_DEBUG
private:
T* fHead;
T* fTail;
typedef SkNoncopyable INHERITED;
};
#endif