182d32d154c4ac1edcc3046167172f663a99a178
[WebKit-https.git] / Source / WTF / wtf / Bag.h
1 /*
2  * Copyright (C) 2013-2018 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  * 1. Redistributions of source code must retain the above copyright
8  *    notice, this list of conditions and the following disclaimer.
9  * 2. Redistributions in binary form must reproduce the above copyright
10  *    notice, this list of conditions and the following disclaimer in the
11  *    documentation and/or other materials provided with the distribution.
12  *
13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #pragma once
27
28 #include <wtf/DumbPtrTraits.h>
29 #include <wtf/FastMalloc.h>
30 #include <wtf/Noncopyable.h>
31
32 namespace WTF {
33
34 namespace Private {
35
36 template<typename T>
37 class BagNode {
38     WTF_MAKE_FAST_ALLOCATED;
39 public:
40     template<typename... Args>
41     BagNode(Args&&... args)
42         : m_item(std::forward<Args>(args)...)
43     { }
44     
45     T m_item;
46     BagNode* m_next { nullptr };
47 };
48
49 } // namespace Private
50
51 template<typename T, typename PtrTraits = DumbPtrTraits<Private::BagNode<T>>>
52 class Bag {
53     WTF_MAKE_NONCOPYABLE(Bag);
54     WTF_MAKE_FAST_ALLOCATED;
55     using Node = Private::BagNode<T>;
56
57 public:
58     Bag() = default;
59
60     template<typename U>
61     Bag(Bag<T, U>&& other)
62     {
63         ASSERT(!m_head);
64         m_head = other.unwrappedHead();
65         other.m_head = nullptr;
66     }
67
68     template<typename U>
69     Bag& operator=(Bag<T, U>&& other)
70     {
71         m_head = other.unwrappedHead();
72         other.m_head = nullptr;
73         return *this;
74     }
75     
76     ~Bag()
77     {
78         clear();
79     }
80     
81     void clear()
82     {
83         Node* head = this->unwrappedHead();
84         while (head) {
85             Node* current = head;
86             head = current->m_next;
87             delete current;
88         }
89         m_head = nullptr;
90     }
91     
92     template<typename... Args>
93     T* add(Args&&... args)
94     {
95         Node* newNode = new Node(std::forward<Args>(args)...);
96         newNode->m_next = unwrappedHead();
97         m_head = newNode;
98         return &newNode->m_item;
99     }
100     
101     class iterator {
102     public:
103         iterator()
104             : m_node(0)
105         {
106         }
107         
108         // This is sort of cheating; it's equivalent to iter == end().
109         bool operator!() const { return !m_node; }
110         
111         T* operator*() const { return &m_node->m_item; }
112         
113         iterator& operator++()
114         {
115             m_node = m_node->m_next;
116             return *this;
117         }
118         
119         bool operator==(const iterator& other) const
120         {
121             return m_node == other.m_node;
122         }
123
124         bool operator!=(const iterator& other) const
125         {
126             return !(*this == other);
127         }
128
129     private:
130         template<typename, typename> friend class WTF::Bag;
131         Node* m_node;
132     };
133     
134     iterator begin()
135     {
136         iterator result;
137         result.m_node = unwrappedHead();
138         return result;
139     }
140
141     const iterator begin() const
142     {
143         iterator result;
144         result.m_node = unwrappedHead();
145         return result;
146     }
147
148
149     iterator end() const { return iterator(); }
150     
151     bool isEmpty() const { return !m_head; }
152     
153 private:
154     Node* unwrappedHead() const { return PtrTraits::unwrap(m_head); }
155
156     typename PtrTraits::StorageType m_head { nullptr };
157 };
158
159 template<typename Poison, typename T> struct PoisonedPtrTraits;
160
161 template<typename Poison, typename T>
162 using PoisonedBag = Bag<T, PoisonedPtrTraits<Poison, Private::BagNode<T>>>;
163
164 } // namespace WTF
165
166 using WTF::Bag;
167 using WTF::PoisonedBag;