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
29namespace WTF {
30
31template<typename T>
32class Bag {
33 WTF_MAKE_NONCOPYABLE(Bag);
34 WTF_MAKE_FAST_ALLOCATED;
35private:
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
49public:
50 Bag()
51 : m_head(nullptr)
52 {
53 }
54
55 ~Bag()
56 {
57 clear();
58 }
59
60 void clear()
61 {
62 while (m_head) {
63 Node* current = m_head;
64 m_head = current->m_next;
65 delete current;
66 }
67 m_head = nullptr;
68 }
69
70 template<typename... Args>
71 T* add(Args... args)
72 {
73 Node* newNode = new Node(args...);
74 newNode->m_next = m_head;
75 m_head = newNode;
76 return &newNode->m_item;
77 }
78
79 class iterator {
80 public:
81 iterator()
82 : m_node(0)
83 {
84 }
85
86 // This is sort of cheating; it's equivalent to iter == end().
87 bool operator!() const { return !m_node; }
88
89 T* operator*() const { return &m_node->m_item; }
90
91 iterator& operator++()
92 {
93 m_node = m_node->m_next;
94 return *this;
95 }
96
97 bool operator==(const iterator& other) const
98 {
99 return m_node == other.m_node;
100 }
101
102 bool operator!=(const iterator& other) const
103 {
104 return !(*this == other);
105 }
106
107 private:
108 template<typename U> friend class WTF::Bag;
109 Node* m_node;
110 };
111
112 iterator begin()
113 {
114 iterator result;
115 result.m_node = m_head;
116 return result;
117 }
118
119 iterator end() { return iterator(); }
120
121 bool isEmpty() const { return !m_head; }
122
123private:
124 Node* m_head;
125};
126
127} // namespace WTF
128
129using WTF::Bag;
130
131#endif // Bag_h
132
133