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