Line data    Source code

       1             : /*
       2             :  * Copyright 2016 Google Inc.
       3             :  *
       4             :  * Use of this source code is governed by a BSD-style license that can be
       5             :  * found in the LICENSE file.
       6             :  */
       7             : #ifndef SkSinglyLinkedList_DEFINED
       8             : #define SkSinglyLinkedList_DEFINED
       9             : 
      10             : #include <utility>
      11             : 
      12             : #include "SkTypes.h"
      13             : 
      14             : template <typename T> class SkSinglyLinkedList {
      15             :     struct Node;
      16             : public:
      17           0 :     SkSinglyLinkedList() : fHead(nullptr), fTail(nullptr) {}
      18           0 :     ~SkSinglyLinkedList() { this->reset(); }
      19           0 :     void reset() {
      20           0 :         SkASSERT(fHead != nullptr || nullptr == fTail);
      21             :         // Use a while loop rather than recursion to avoid stack overflow.
      22           0 :         Node* node = fHead;
      23           0 :         while (node) {
      24           0 :             Node* next = node->fNext;
      25           0 :             SkASSERT(next != nullptr || node == fTail);
      26           0 :             delete node;
      27           0 :             node = next;
      28             :         }
      29           0 :         fHead = nullptr;
      30           0 :         fTail = nullptr;
      31           0 :     }
      32           0 :     T* back() { return fTail ? &fTail->fData : nullptr; }
      33           0 :     T* front() { return fHead ? &fHead->fData : nullptr; }
      34             :     bool empty() const { return fHead == nullptr; }
      35             :     #ifdef SK_DEBUG
      36           0 :     int count() {  // O(n), debug only.
      37           0 :         int count = 0;
      38           0 :         for (Node* node = fHead; node; node = node->fNext) {
      39           0 :             ++count;
      40             :         }
      41           0 :         return count;
      42             :     }
      43             :     #endif
      44           0 :     void pop_front() {
      45           0 :         if (Node* node = fHead) {
      46           0 :             fHead = node->fNext;
      47           0 :             delete node;
      48           0 :             if (fHead == nullptr) {
      49           0 :                 fTail = nullptr;
      50             :             }
      51             :         }
      52           0 :     }
      53           0 :     template <class... Args> T* emplace_front(Args&&... args) {
      54           0 :         Node* n = new Node(std::forward<Args>(args)...);
      55           0 :         n->fNext = fHead;
      56           0 :         if (!fTail) {
      57           0 :             fTail = n;
      58           0 :             SkASSERT(!fHead);
      59             :         }
      60           0 :         fHead = n;
      61           0 :         return &n->fData;
      62             :     }
      63           0 :     template <class... Args> T* emplace_back(Args&&... args) {
      64           0 :         Node* n = new Node(std::forward<Args>(args)...);
      65           0 :         if (fTail) {
      66           0 :             fTail->fNext = n;
      67             :         } else {
      68           0 :             fHead = n;
      69             :         }
      70           0 :         fTail = n;
      71           0 :         return &n->fData;
      72             :     }
      73             :     class ConstIter {
      74             :     public:
      75           0 :         void operator++() { fNode = fNode->fNext; }
      76           0 :         const T& operator*() const { return fNode->fData; }
      77           0 :         bool operator!=(const ConstIter& rhs) const { return fNode != rhs.fNode; }
      78           0 :         ConstIter(const Node* n) : fNode(n) {}
      79             :     private:
      80             :         const Node* fNode;
      81             :     };
      82           0 :     ConstIter begin() const { return ConstIter(fHead); }
      83           0 :     ConstIter end() const { return ConstIter(nullptr); }
      84             : 
      85             : private:
      86           0 :     struct Node {
      87             :         T fData;
      88             :         Node* fNext;
      89             :         template <class... Args>
      90           0 :         Node(Args&&... args) : fData(std::forward<Args>(args)...), fNext(nullptr) {}
      91             :     };
      92             :     Node* fHead;
      93             :     Node* fTail;
      94             :     SkSinglyLinkedList(const SkSinglyLinkedList<T>&) = delete;
      95             :     SkSinglyLinkedList& operator=(const SkSinglyLinkedList<T>&) = delete;
      96             : };
      97             : #endif  // SkSinglyLinkedList_DEFINED