[JSC] Compress Watchpoint size by using enum type and Packed<> data structure
[WebKit-https.git] / Source / WTF / wtf / SentinelLinkedList.h
1 /*
2  * Copyright (C) 2011, 2016 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 //    A SentinelLinkedList is a linked list with dummy head and tail sentinels,
27 //    which allow for branch-less insertion and removal, and removal without a
28 //    pointer to the list.
29 //    
30 //    Requires: Node is a concrete class with:
31 //        Node(SentinelTag);
32 //        void setPrev(Node*);
33 //        Node* prev();
34 //        void setNext(Node*);
35 //        Node* next();
36
37 #pragma once
38
39 #include <wtf/Packed.h>
40
41 namespace WTF {
42
43 enum SentinelTag { Sentinel };
44
45 template<typename T, typename PassedPtrTraits = DumbPtrTraits<T>>
46 class BasicRawSentinelNode {
47     WTF_MAKE_FAST_ALLOCATED;
48 public:
49     using PtrTraits = typename PassedPtrTraits::template RebindTraits<BasicRawSentinelNode>;
50
51     BasicRawSentinelNode(SentinelTag)
52     {
53     }
54     
55     BasicRawSentinelNode() = default;
56     
57     void setPrev(BasicRawSentinelNode* prev) { m_prev = prev; }
58     void setNext(BasicRawSentinelNode* next) { m_next = next; }
59     
60     T* prev() { return static_cast<T*>(PtrTraits::unwrap(m_prev)); }
61     T* next() { return static_cast<T*>(PtrTraits::unwrap(m_next)); }
62     
63     bool isOnList() const
64     {
65         ASSERT(!!m_prev == !!m_next);
66         return !!m_prev;
67     }
68     
69     void remove();
70
71     void prepend(BasicRawSentinelNode*);
72     void append(BasicRawSentinelNode*);
73     
74 private:
75     typename PtrTraits::StorageType m_next { nullptr };
76     typename PtrTraits::StorageType m_prev { nullptr };
77 };
78
79 template <typename T, typename RawNode = T> class SentinelLinkedList {
80 public:
81     typedef T* iterator;
82
83     SentinelLinkedList();
84
85     // Pushes to the front of the list. It's totally backwards from what you'd expect.
86     void push(T*);
87
88     // Appends to the end of the list.
89     void append(T*);
90     
91     static void remove(T*);
92     static void prepend(T* existingNode, T* newNode);
93     static void append(T* existingNode, T* newNode);
94     
95     bool isOnList(T*);
96
97     iterator begin();
98     iterator end();
99     
100     bool isEmpty() { return begin() == end(); }
101     
102     template<typename Func>
103     void forEach(const Func& func)
104     {
105         for (iterator iter = begin(); iter != end();) {
106             iterator next = iter->next();
107             func(iter);
108             iter = next;
109         }
110     }
111     
112     void takeFrom(SentinelLinkedList<T, RawNode>&);
113     
114 private:
115     RawNode m_headSentinel;
116     RawNode m_tailSentinel;
117 };
118
119 template <typename T, typename PtrTraits> void BasicRawSentinelNode<T, PtrTraits>::remove()
120 {
121     SentinelLinkedList<T, BasicRawSentinelNode>::remove(static_cast<T*>(this));
122 }
123
124 template <typename T, typename PtrTraits> void BasicRawSentinelNode<T, PtrTraits>::prepend(BasicRawSentinelNode* node)
125 {
126     SentinelLinkedList<T, BasicRawSentinelNode>::prepend(
127         static_cast<T*>(this), static_cast<T*>(node));
128 }
129
130 template <typename T, typename PtrTraits> void BasicRawSentinelNode<T, PtrTraits>::append(BasicRawSentinelNode* node)
131 {
132     SentinelLinkedList<T, BasicRawSentinelNode>::append(
133         static_cast<T*>(this), static_cast<T*>(node));
134 }
135
136 template <typename T, typename RawNode> inline SentinelLinkedList<T, RawNode>::SentinelLinkedList()
137     : m_headSentinel(Sentinel)
138     , m_tailSentinel(Sentinel)
139 {
140     m_headSentinel.setNext(&m_tailSentinel);
141     m_headSentinel.setPrev(nullptr);
142
143     m_tailSentinel.setPrev(&m_headSentinel);
144     m_tailSentinel.setNext(nullptr);
145 }
146
147 template <typename T, typename RawNode> inline typename SentinelLinkedList<T, RawNode>::iterator SentinelLinkedList<T, RawNode>::begin()
148 {
149     return static_cast<T*>(m_headSentinel.next());
150 }
151
152 template <typename T, typename RawNode> inline typename SentinelLinkedList<T, RawNode>::iterator SentinelLinkedList<T, RawNode>::end()
153 {
154     return static_cast<T*>(&m_tailSentinel);
155 }
156
157 template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::push(T* node)
158 {
159     ASSERT(node);
160     ASSERT(!node->prev());
161     ASSERT(!node->next());
162     
163     RawNode* prev = &m_headSentinel;
164     RawNode* next = m_headSentinel.next();
165
166     node->setPrev(prev);
167     node->setNext(next);
168
169     prev->setNext(node);
170     next->setPrev(node);
171 }
172
173 template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::append(T* node)
174 {
175     ASSERT(node);
176     ASSERT(!node->prev());
177     ASSERT(!node->next());
178     
179     RawNode* prev = m_tailSentinel.prev();
180     RawNode* next = &m_tailSentinel;
181
182     node->setPrev(prev);
183     node->setNext(next);
184
185     prev->setNext(node);
186     next->setPrev(node);
187 }
188
189 template <typename T, typename RawNode> inline void SentinelLinkedList<T, RawNode>::remove(T* node)
190 {
191     ASSERT(node);
192     ASSERT(!!node->prev());
193     ASSERT(!!node->next());
194     
195     RawNode* prev = node->prev();
196     RawNode* next = node->next();
197
198     prev->setNext(next);
199     next->setPrev(prev);
200     
201     node->setPrev(nullptr);
202     node->setNext(nullptr);
203 }
204
205 template <typename T, typename RawNode>
206 inline void SentinelLinkedList<T, RawNode>::prepend(T* existingNode, T* newNode)
207 {
208     ASSERT(existingNode);
209     ASSERT(!!existingNode->prev());
210     ASSERT(!!existingNode->next());
211     ASSERT(newNode);
212     ASSERT(!newNode->prev());
213     ASSERT(!newNode->next());
214
215     RawNode* prev = existingNode->prev();
216
217     newNode->setNext(existingNode);
218     newNode->setPrev(prev);
219     
220     prev->setNext(newNode);
221     existingNode->setPrev(newNode);
222 }
223
224 template <typename T, typename RawNode>
225 inline void SentinelLinkedList<T, RawNode>::append(T* existingNode, T* newNode)
226 {
227     ASSERT(existingNode);
228     ASSERT(!!existingNode->prev());
229     ASSERT(!!existingNode->next());
230     ASSERT(newNode);
231     ASSERT(!newNode->prev());
232     ASSERT(!newNode->next());
233
234     RawNode* next = existingNode->next();
235
236     newNode->setNext(next);
237     newNode->setPrev(existingNode);
238     
239     next->setPrev(newNode);
240     existingNode->setNext(newNode);
241 }
242
243 template <typename T, typename RawNode> inline bool SentinelLinkedList<T, RawNode>::isOnList(T* node)
244 {
245     if (!node->isOnList())
246         return false;
247     
248     for (T* iter = begin(); iter != end(); iter = iter->next()) {
249         if (iter == node)
250             return true;
251     }
252     
253     return false;
254 }
255
256 template <typename T, typename RawNode>
257 inline void SentinelLinkedList<T, RawNode>::takeFrom(SentinelLinkedList<T, RawNode>& other)
258 {
259     if (other.isEmpty())
260         return;
261     
262     m_tailSentinel.prev()->setNext(other.m_headSentinel.next());
263     other.m_headSentinel.next()->setPrev(m_tailSentinel.prev());
264     
265     m_tailSentinel.setPrev(other.m_tailSentinel.prev());
266     m_tailSentinel.prev()->setNext(&m_tailSentinel);
267
268     other.m_headSentinel.setNext(&other.m_tailSentinel);
269     other.m_tailSentinel.setPrev(&other.m_headSentinel);
270 }
271
272 template<typename T>
273 using PackedRawSentinelNode = BasicRawSentinelNode<T, PackedPtrTraits<T>>;
274
275 }
276
277 using WTF::BasicRawSentinelNode;
278 using WTF::PackedRawSentinelNode;
279 using WTF::SentinelLinkedList;