1e585b07e77f679dd95a21e1b863cfc20e55d78b
[WebKit-https.git] / Source / WTF / wtf / Bag.h
1 /*
2  * Copyright (C) 2013-2019 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     ~Bag()
69     {
70         clear();
71     }
72     
73     void clear()
74     {
75         Node* head = this->unwrappedHead();
76         while (head) {
77             Node* current = head;
78             head = current->m_next;
79             delete current;
80         }
81         m_head = nullptr;
82     }
83     
84     template<typename... Args>
85     T* add(Args&&... args)
86     {
87         Node* newNode = new Node(std::forward<Args>(args)...);
88         newNode->m_next = unwrappedHead();
89         m_head = newNode;
90         return &newNode->m_item;
91     }
92     
93     class iterator {
94     public:
95         iterator()
96             : m_node(0)
97         {
98         }
99         
100         // This is sort of cheating; it's equivalent to iter == end().
101         bool operator!() const { return !m_node; }
102         
103         T* operator*() const { return &m_node->m_item; }
104         
105         iterator& operator++()
106         {
107             m_node = m_node->m_next;
108             return *this;
109         }
110         
111         bool operator==(const iterator& other) const
112         {
113             return m_node == other.m_node;
114         }
115
116         bool operator!=(const iterator& other) const
117         {
118             return !(*this == other);
119         }
120
121     private:
122         template<typename, typename> friend class WTF::Bag;
123         Node* m_node;
124     };
125     
126     iterator begin()
127     {
128         iterator result;
129         result.m_node = unwrappedHead();
130         return result;
131     }
132
133     const iterator begin() const
134     {
135         iterator result;
136         result.m_node = unwrappedHead();
137         return result;
138     }
139
140
141     iterator end() const { return iterator(); }
142     
143     bool isEmpty() const { return !m_head; }
144     
145 private:
146     Node* unwrappedHead() const { return PtrTraits::unwrap(m_head); }
147
148     typename PtrTraits::StorageType m_head { nullptr };
149 };
150
151 } // namespace WTF
152
153 using WTF::Bag;