123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302 |
- /*
- * 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 "include/core/SkTypes.h"
- /**
- * 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(SkTInternalLList<ClassName>* fList = nullptr;) \
- ClassName* fPrev = nullptr; \
- ClassName* fNext = nullptr
- /**
- * This class implements a templated internal doubly linked list data structure.
- */
- template <class T> class SkTInternalLList {
- public:
- SkTInternalLList() {}
- 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 = nullptr;
- T* fTail = nullptr;
- SkTInternalLList(const SkTInternalLList&) = delete;
- SkTInternalLList& operator=(const SkTInternalLList&) = delete;
- };
- #endif
|