Unreviewed, rolling out r234489.
[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 #ifndef Bag_h
27 #define Bag_h
28
29 #include <wtf/DumbPtrTraits.h>
30 #include <wtf/FastMalloc.h>
31 #include <wtf/Noncopyable.h>
32
33 namespace WTF {
34
35 namespace Private {
36
37 template<typename T>
38 class BagNode {
39     WTF_MAKE_FAST_ALLOCATED;
40 public:
41     template<typename... Args>
42     BagNode(Args&&... args)
43         : m_item(std::forward<Args>(args)...)
44     { }
45     
46     T m_item;
47     BagNode* m_next { nullptr };
48 };
49
50 } // namespace Private
51
52 template<typename T, typename PtrTraits = DumbPtrTraits<Private::BagNode<T>>>
53 class Bag {
54     WTF_MAKE_NONCOPYABLE(Bag);
55     WTF_MAKE_FAST_ALLOCATED;
56     using Node = Private::BagNode<T>;
57
58 public:
59     Bag() = default;
60
61     template<typename U>
62     Bag(Bag<T, U>&& other)
63     {
64         ASSERT(!m_head);
65         m_head = other.unwrappedHead();
66         other.m_head = nullptr;
67     }
68
69     template<typename U>
70     Bag& operator=(Bag<T, U>&& other)
71     {
72         m_head = other.unwrappedHead();
73         other.m_head = nullptr;
74         return *this;
75     }
76     
77     ~Bag()
78     {
79         clear();
80     }
81     
82     void clear()
83     {
84         Node* head = this->unwrappedHead();
85         while (head) {
86             Node* current = head;
87             head = current->m_next;
88             delete current;
89         }
90         m_head = nullptr;
91     }
92     
93     template<typename... Args>
94     T* add(Args&&... args)
95     {
96         Node* newNode = new Node(std::forward<Args>(args)...);
97         newNode->m_next = unwrappedHead();
98         m_head = newNode;
99         return &newNode->m_item;
100     }
101     
102     class iterator {
103     public:
104         iterator()
105             : m_node(0)
106         {
107         }
108         
109         // This is sort of cheating; it's equivalent to iter == end().
110         bool operator!() const { return !m_node; }
111         
112         T* operator*() const { return &m_node->m_item; }
113         
114         iterator& operator++()
115         {
116             m_node = m_node->m_next;
117             return *this;
118         }
119         
120         bool operator==(const iterator& other) const
121         {
122             return m_node == other.m_node;
123         }
124
125         bool operator!=(const iterator& other) const
126         {
127             return !(*this == other);
128         }
129
130     private:
131         template<typename, typename> friend class WTF::Bag;
132         Node* m_node;
133     };
134     
135     iterator begin()
136     {
137         iterator result;
138         result.m_node = unwrappedHead();
139         return result;
140     }
141
142     const iterator begin() const
143     {
144         iterator result;
145         result.m_node = unwrappedHead();
146         return result;
147     }
148
149
150     iterator end() const { return iterator(); }
151     
152     bool isEmpty() const { return !m_head; }
153     
154 private:
155     Node* unwrappedHead() const { return PtrTraits::unwrap(m_head); }
156
157     typename PtrTraits::StorageType m_head { nullptr };
158 };
159
160 template<typename Poison, typename T> struct PoisonedPtrTraits;
161
162 template<typename Poison, typename T>
163 using PoisonedBag = Bag<T, PoisonedPtrTraits<Poison, Private::BagNode<T>>>;
164
165 } // namespace WTF
166
167 using WTF::Bag;
168 using WTF::PoisonedBag;
169
170 #endif // Bag_h
171