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
41namespace WTF {
42
43enum SentinelTag { Sentinel };
44
45template<typename T, typename PassedPtrTraits = DumbPtrTraits<T>>
46class BasicRawSentinelNode {
47 WTF_MAKE_FAST_ALLOCATED;
48public:
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
74private:
75 typename PtrTraits::StorageType m_next { nullptr };
76 typename PtrTraits::StorageType m_prev { nullptr };
77};
78
79template <typename T, typename RawNode = T> class SentinelLinkedList {
80public:
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
114private:
115 RawNode m_headSentinel;
116 RawNode m_tailSentinel;
117};
118
119template <typename T, typename PtrTraits> void BasicRawSentinelNode<T, PtrTraits>::remove()
120{
121 SentinelLinkedList<T, BasicRawSentinelNode>::remove(static_cast<T*>(this));
122}
123
124template <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
130template <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
136template <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
147template <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
152template <typename T, typename RawNode> inline typename SentinelLinkedList<T, RawNode>::iterator SentinelLinkedList<T, RawNode>::end()
153{
154 return static_cast<T*>(&m_tailSentinel);
155}
156
157template <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
173template <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
189template <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
205template <typename T, typename RawNode>
206inline 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
224template <typename T, typename RawNode>
225inline 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
243template <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
256template <typename T, typename RawNode>
257inline 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
272template<typename T>
273using PackedRawSentinelNode = BasicRawSentinelNode<T, PackedPtrTraits<T>>;
274
275}
276
277using WTF::BasicRawSentinelNode;
278using WTF::PackedRawSentinelNode;
279using WTF::SentinelLinkedList;
280