Home | History | Annotate | Download | only in core 
      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     SkSinglyLinkedList() : fHead(nullptr), fTail(nullptr) {}
     18     ~SkSinglyLinkedList() { this->reset(); }
     19     void reset() {
     20         SkASSERT(fHead != nullptr || nullptr == fTail);
     21         // Use a while loop rather than recursion to avoid stack overflow.
     22         Node* node = fHead;
     23         while (node) {
     24             Node* next = node->fNext;
     25             SkASSERT(next != nullptr || node == fTail);
     26             delete node;
     27             node = next;
     28         }
     29         fHead = nullptr;
     30         fTail = nullptr;
     31     }
     32     T* back() { return fTail ? &fTail->fData : nullptr; }
     33     T* front() { return fHead ? &fHead->fData : nullptr; }
     34     bool empty() const { return fHead == nullptr; }
     35     #ifdef SK_DEBUG
     36     int count() {  // O(n), debug only.
     37         int count = 0;
     38         for (Node* node = fHead; node; node = node->fNext) {
     39             ++count;
     40         }
     41         return count;
     42     }
     43     #endif
     44     void pop_front() {
     45         if (Node* node = fHead) {
     46             fHead = node->fNext;
     47             delete node;
     48             if (fHead == nullptr) {
     49                 fTail = nullptr;
     50             }
     51         }
     52     }
     53     template <class... Args> T* emplace_front(Args&&... args) {
     54         Node* n = new Node(std::forward<Args>(args)...);
     55         n->fNext = fHead;
     56         if (!fTail) {
     57             fTail = n;
     58             SkASSERT(!fHead);
     59         }
     60         fHead = n;
     61         return &n->fData;
     62     }
     63     template <class... Args> T* emplace_back(Args&&... args) {
     64         Node* n = new Node(std::forward<Args>(args)...);
     65         if (fTail) {
     66             fTail->fNext = n;
     67         } else {
     68             fHead = n;
     69         }
     70         fTail = n;
     71         return &n->fData;
     72     }
     73     class ConstIter {
     74     public:
     75         void operator++() { fNode = fNode->fNext; }
     76         const T& operator*() const { return fNode->fData; }
     77         bool operator!=(const ConstIter& rhs) const { return fNode != rhs.fNode; }
     78         ConstIter(const Node* n) : fNode(n) {}
     79     private:
     80         const Node* fNode;
     81     };
     82     ConstIter begin() const { return ConstIter(fHead); }
     83     ConstIter end() const { return ConstIter(nullptr); }
     84 
     85 private:
     86     struct Node {
     87         T fData;
     88         Node* fNext;
     89         template <class... Args>
     90         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
     98