Unreviewed, reland r201532. The associated regressions have been fixed
[WebKit-https.git] / Source / WTF / wtf / Bag.h
1 /*
2  * Copyright (C) 2013 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 namespace WTF {
30
31 template<typename T>
32 class Bag {
33     WTF_MAKE_NONCOPYABLE(Bag);
34     WTF_MAKE_FAST_ALLOCATED;
35 private:
36     class Node {
37         WTF_MAKE_FAST_ALLOCATED;
38     public:
39         template<typename... Args>
40         Node(Args... args)
41             : m_item(args...)
42         {
43         }
44         
45         T m_item;
46         Node* m_next;
47     };
48     
49 public:
50     Bag()
51     {
52     }
53
54     Bag(Bag<T>&& other)
55     {
56         ASSERT(!m_head);
57         m_head = other.m_head;
58         other.m_head = nullptr;
59     }
60
61     Bag& operator=(Bag<T>&& other)
62     {
63         m_head = other.m_head;
64         other.m_head = nullptr;
65         return *this;
66     }
67     
68     ~Bag()
69     {
70         clear();
71     }
72     
73     void clear()
74     {
75         while (m_head) {
76             Node* current = m_head;
77             m_head = current->m_next;
78             delete current;
79         }
80         m_head = nullptr;
81     }
82     
83     template<typename... Args>
84     T* add(Args... args)
85     {
86         Node* newNode = new Node(args...);
87         newNode->m_next = m_head;
88         m_head = newNode;
89         return &newNode->m_item;
90     }
91     
92     class iterator {
93     public:
94         iterator()
95             : m_node(0)
96         {
97         }
98         
99         // This is sort of cheating; it's equivalent to iter == end().
100         bool operator!() const { return !m_node; }
101         
102         T* operator*() const { return &m_node->m_item; }
103         
104         iterator& operator++()
105         {
106             m_node = m_node->m_next;
107             return *this;
108         }
109         
110         bool operator==(const iterator& other) const
111         {
112             return m_node == other.m_node;
113         }
114
115         bool operator!=(const iterator& other) const
116         {
117             return !(*this == other);
118         }
119
120     private:
121         template<typename U> friend class WTF::Bag;
122         Node* m_node;
123     };
124     
125     iterator begin()
126     {
127         iterator result;
128         result.m_node = m_head;
129         return result;
130     }
131     
132     iterator end() { return iterator(); }
133     
134     bool isEmpty() const { return !m_head; }
135     
136 private:
137     Node* m_head { nullptr };
138 };
139
140 } // namespace WTF
141
142 using WTF::Bag;
143
144 #endif // Bag_h
145