12be7e01382ee9c036de9c09585677dfd25d70253halcanary/* 22be7e01382ee9c036de9c09585677dfd25d70253halcanary * Copyright 2016 Google Inc. 32be7e01382ee9c036de9c09585677dfd25d70253halcanary * 42be7e01382ee9c036de9c09585677dfd25d70253halcanary * Use of this source code is governed by a BSD-style license that can be 52be7e01382ee9c036de9c09585677dfd25d70253halcanary * found in the LICENSE file. 62be7e01382ee9c036de9c09585677dfd25d70253halcanary */ 72be7e01382ee9c036de9c09585677dfd25d70253halcanary#ifndef SkSinglyLinkedList_DEFINED 82be7e01382ee9c036de9c09585677dfd25d70253halcanary#define SkSinglyLinkedList_DEFINED 92be7e01382ee9c036de9c09585677dfd25d70253halcanary 102be7e01382ee9c036de9c09585677dfd25d70253halcanary#include <utility> 112be7e01382ee9c036de9c09585677dfd25d70253halcanary 122be7e01382ee9c036de9c09585677dfd25d70253halcanary#include "SkTypes.h" 132be7e01382ee9c036de9c09585677dfd25d70253halcanary 142be7e01382ee9c036de9c09585677dfd25d70253halcanarytemplate <typename T> class SkSinglyLinkedList { 152be7e01382ee9c036de9c09585677dfd25d70253halcanary struct Node; 162be7e01382ee9c036de9c09585677dfd25d70253halcanarypublic: 172be7e01382ee9c036de9c09585677dfd25d70253halcanary SkSinglyLinkedList() : fHead(nullptr), fTail(nullptr) {} 182be7e01382ee9c036de9c09585677dfd25d70253halcanary ~SkSinglyLinkedList() { this->reset(); } 192be7e01382ee9c036de9c09585677dfd25d70253halcanary void reset() { 202be7e01382ee9c036de9c09585677dfd25d70253halcanary SkASSERT(fHead != nullptr || nullptr == fTail); 21ebbdfe63a9643faa403f33282da9921427ca91ebhalcanary // Use a while loop rather than recursion to avoid stack overflow. 222be7e01382ee9c036de9c09585677dfd25d70253halcanary Node* node = fHead; 232be7e01382ee9c036de9c09585677dfd25d70253halcanary while (node) { 242be7e01382ee9c036de9c09585677dfd25d70253halcanary Node* next = node->fNext; 252be7e01382ee9c036de9c09585677dfd25d70253halcanary SkASSERT(next != nullptr || node == fTail); 262be7e01382ee9c036de9c09585677dfd25d70253halcanary delete node; 272be7e01382ee9c036de9c09585677dfd25d70253halcanary node = next; 282be7e01382ee9c036de9c09585677dfd25d70253halcanary } 292be7e01382ee9c036de9c09585677dfd25d70253halcanary fHead = nullptr; 302be7e01382ee9c036de9c09585677dfd25d70253halcanary fTail = nullptr; 312be7e01382ee9c036de9c09585677dfd25d70253halcanary } 322be7e01382ee9c036de9c09585677dfd25d70253halcanary T* back() { return fTail ? &fTail->fData : nullptr; } 332be7e01382ee9c036de9c09585677dfd25d70253halcanary T* front() { return fHead ? &fHead->fData : nullptr; } 34e20a87517043ec4a30dcc7e711ca49087e8942ffhalcanary bool empty() const { return fHead == nullptr; } 352be7e01382ee9c036de9c09585677dfd25d70253halcanary #ifdef SK_DEBUG 362be7e01382ee9c036de9c09585677dfd25d70253halcanary int count() { // O(n), debug only. 372be7e01382ee9c036de9c09585677dfd25d70253halcanary int count = 0; 382be7e01382ee9c036de9c09585677dfd25d70253halcanary for (Node* node = fHead; node; node = node->fNext) { 392be7e01382ee9c036de9c09585677dfd25d70253halcanary ++count; 402be7e01382ee9c036de9c09585677dfd25d70253halcanary } 412be7e01382ee9c036de9c09585677dfd25d70253halcanary return count; 422be7e01382ee9c036de9c09585677dfd25d70253halcanary } 432be7e01382ee9c036de9c09585677dfd25d70253halcanary #endif 442be7e01382ee9c036de9c09585677dfd25d70253halcanary void pop_front() { 452be7e01382ee9c036de9c09585677dfd25d70253halcanary if (Node* node = fHead) { 462be7e01382ee9c036de9c09585677dfd25d70253halcanary fHead = node->fNext; 472be7e01382ee9c036de9c09585677dfd25d70253halcanary delete node; 482be7e01382ee9c036de9c09585677dfd25d70253halcanary if (fHead == nullptr) { 492be7e01382ee9c036de9c09585677dfd25d70253halcanary fTail = nullptr; 502be7e01382ee9c036de9c09585677dfd25d70253halcanary } 512be7e01382ee9c036de9c09585677dfd25d70253halcanary } 522be7e01382ee9c036de9c09585677dfd25d70253halcanary } 532be7e01382ee9c036de9c09585677dfd25d70253halcanary template <class... Args> T* emplace_front(Args&&... args) { 542be7e01382ee9c036de9c09585677dfd25d70253halcanary Node* n = new Node(std::forward<Args>(args)...); 552be7e01382ee9c036de9c09585677dfd25d70253halcanary n->fNext = fHead; 562be7e01382ee9c036de9c09585677dfd25d70253halcanary if (!fTail) { 572be7e01382ee9c036de9c09585677dfd25d70253halcanary fTail = n; 582be7e01382ee9c036de9c09585677dfd25d70253halcanary SkASSERT(!fHead); 592be7e01382ee9c036de9c09585677dfd25d70253halcanary } 602be7e01382ee9c036de9c09585677dfd25d70253halcanary fHead = n; 612be7e01382ee9c036de9c09585677dfd25d70253halcanary return &n->fData; 622be7e01382ee9c036de9c09585677dfd25d70253halcanary } 632be7e01382ee9c036de9c09585677dfd25d70253halcanary template <class... Args> T* emplace_back(Args&&... args) { 642be7e01382ee9c036de9c09585677dfd25d70253halcanary Node* n = new Node(std::forward<Args>(args)...); 652be7e01382ee9c036de9c09585677dfd25d70253halcanary if (fTail) { 662be7e01382ee9c036de9c09585677dfd25d70253halcanary fTail->fNext = n; 672be7e01382ee9c036de9c09585677dfd25d70253halcanary } else { 682be7e01382ee9c036de9c09585677dfd25d70253halcanary fHead = n; 692be7e01382ee9c036de9c09585677dfd25d70253halcanary } 702be7e01382ee9c036de9c09585677dfd25d70253halcanary fTail = n; 712be7e01382ee9c036de9c09585677dfd25d70253halcanary return &n->fData; 722be7e01382ee9c036de9c09585677dfd25d70253halcanary } 732be7e01382ee9c036de9c09585677dfd25d70253halcanary class ConstIter { 742be7e01382ee9c036de9c09585677dfd25d70253halcanary public: 752be7e01382ee9c036de9c09585677dfd25d70253halcanary void operator++() { fNode = fNode->fNext; } 762be7e01382ee9c036de9c09585677dfd25d70253halcanary const T& operator*() const { return fNode->fData; } 772be7e01382ee9c036de9c09585677dfd25d70253halcanary bool operator!=(const ConstIter& rhs) const { return fNode != rhs.fNode; } 782be7e01382ee9c036de9c09585677dfd25d70253halcanary ConstIter(const Node* n) : fNode(n) {} 792be7e01382ee9c036de9c09585677dfd25d70253halcanary private: 802be7e01382ee9c036de9c09585677dfd25d70253halcanary const Node* fNode; 812be7e01382ee9c036de9c09585677dfd25d70253halcanary }; 822be7e01382ee9c036de9c09585677dfd25d70253halcanary ConstIter begin() const { return ConstIter(fHead); } 832be7e01382ee9c036de9c09585677dfd25d70253halcanary ConstIter end() const { return ConstIter(nullptr); } 842be7e01382ee9c036de9c09585677dfd25d70253halcanary 852be7e01382ee9c036de9c09585677dfd25d70253halcanaryprivate: 862be7e01382ee9c036de9c09585677dfd25d70253halcanary struct Node { 872be7e01382ee9c036de9c09585677dfd25d70253halcanary T fData; 882be7e01382ee9c036de9c09585677dfd25d70253halcanary Node* fNext; 892be7e01382ee9c036de9c09585677dfd25d70253halcanary template <class... Args> 902be7e01382ee9c036de9c09585677dfd25d70253halcanary Node(Args&&... args) : fData(std::forward<Args>(args)...), fNext(nullptr) {} 912be7e01382ee9c036de9c09585677dfd25d70253halcanary }; 922be7e01382ee9c036de9c09585677dfd25d70253halcanary Node* fHead; 932be7e01382ee9c036de9c09585677dfd25d70253halcanary Node* fTail; 942be7e01382ee9c036de9c09585677dfd25d70253halcanary SkSinglyLinkedList(const SkSinglyLinkedList<T>&) = delete; 952be7e01382ee9c036de9c09585677dfd25d70253halcanary SkSinglyLinkedList& operator=(const SkSinglyLinkedList<T>&) = delete; 962be7e01382ee9c036de9c09585677dfd25d70253halcanary}; 972be7e01382ee9c036de9c09585677dfd25d70253halcanary#endif // SkSinglyLinkedList_DEFINED 98