1 /*
2  * Copyright 2017 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 
8 #ifndef SkArenaAllocList_DEFINED
9 #define SkArenaAllocList_DEFINED
10 
11 #include "include/core/SkTypes.h"
12 #include "src/core/SkArenaAlloc.h"
13 
14 /**
15  * A singly linked list of Ts stored in a SkArenaAlloc. The arena rather than the list owns
16  * the elements. This supports forward iteration and range based for loops.
17  */
18 template <typename T>
19 class SkArenaAllocList {
20 private:
21     struct Node;
22 
23 public:
24     SkArenaAllocList() = default;
25 
reset()26     void reset() { fHead = fTail = nullptr; }
27 
28     template <typename... Args>
29     inline T& append(SkArenaAlloc* arena, Args... args);
30 
31     class Iter {
32     public:
33         Iter() = default;
34         inline Iter& operator++();
35         T& operator*() const { return fCurr->fT; }
36         T* operator->() const { return &fCurr->fT; }
37         bool operator==(const Iter& that) const { return fCurr == that.fCurr; }
38         bool operator!=(const Iter& that) const { return !(*this == that); }
39 
40     private:
41         friend class SkArenaAllocList;
Iter(Node * node)42         explicit Iter(Node* node) : fCurr(node) {}
43         Node* fCurr = nullptr;
44     };
45 
begin()46     Iter begin() { return Iter(fHead); }
end()47     Iter end() { return Iter(); }
tail()48     Iter tail() { return Iter(fTail); }
49 
50 private:
51     struct Node {
52         template <typename... Args>
NodeNode53         Node(Args... args) : fT(std::forward<Args>(args)...) {}
54         T fT;
55         Node* fNext = nullptr;
56     };
57     Node* fHead = nullptr;
58     Node* fTail = nullptr;
59 };
60 
61 template <typename T>
62 template <typename... Args>
append(SkArenaAlloc * arena,Args...args)63 T& SkArenaAllocList<T>::append(SkArenaAlloc* arena, Args... args) {
64     SkASSERT(!fHead == !fTail);
65     auto* n = arena->make<Node>(std::forward<Args>(args)...);
66     if (!fTail) {
67         fHead = fTail = n;
68     } else {
69         fTail = fTail->fNext = n;
70     }
71     return fTail->fT;
72 }
73 
74 template <typename T>
75 typename SkArenaAllocList<T>::Iter& SkArenaAllocList<T>::Iter::operator++() {
76     fCurr = fCurr->fNext;
77     return *this;
78 }
79 
80 #endif
81