1/*
2 * Copyright (C) 2011 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
28namespace WTF {
29
30// This class allows nodes to share code without dictating data member layout.
31template<typename T> class DoublyLinkedListNode {
32public:
33 DoublyLinkedListNode();
34
35 void setPrev(T*);
36 void setNext(T*);
37
38 T* prev() const;
39 T* next() const;
40};
41
42template<typename T> inline DoublyLinkedListNode<T>::DoublyLinkedListNode()
43{
44 setPrev(0);
45 setNext(0);
46}
47
48template<typename T> inline void DoublyLinkedListNode<T>::setPrev(T* prev)
49{
50 static_cast<T*>(this)->m_prev = prev;
51}
52
53template<typename T> inline void DoublyLinkedListNode<T>::setNext(T* next)
54{
55 static_cast<T*>(this)->m_next = next;
56}
57
58template<typename T> inline T* DoublyLinkedListNode<T>::prev() const
59{
60 return static_cast<const T*>(this)->m_prev;
61}
62
63template<typename T> inline T* DoublyLinkedListNode<T>::next() const
64{
65 return static_cast<const T*>(this)->m_next;
66}
67
68template<typename T> class DoublyLinkedList {
69public:
70 DoublyLinkedList();
71
72 bool isEmpty() const;
73 size_t size() const; // This is O(n).
74 void clear();
75
76 T* head() const;
77 T* removeHead();
78
79 T* tail() const;
80
81 void push(T*);
82 void append(T*);
83 void remove(T*);
84 void append(DoublyLinkedList<T>&);
85
86private:
87 T* m_head;
88 T* m_tail;
89};
90
91template<typename T> inline DoublyLinkedList<T>::DoublyLinkedList()
92 : m_head(0)
93 , m_tail(0)
94{
95}
96
97template<typename T> inline bool DoublyLinkedList<T>::isEmpty() const
98{
99 return !m_head;
100}
101
102template<typename T> inline size_t DoublyLinkedList<T>::size() const
103{
104 size_t size = 0;
105 for (T* node = m_head; node; node = node->next())
106 ++size;
107 return size;
108}
109
110template<typename T> inline void DoublyLinkedList<T>::clear()
111{
112 m_head = 0;
113 m_tail = 0;
114}
115
116template<typename T> inline T* DoublyLinkedList<T>::head() const
117{
118 return m_head;
119}
120
121template<typename T> inline T* DoublyLinkedList<T>::tail() const
122{
123 return m_tail;
124}
125
126template<typename T> inline void DoublyLinkedList<T>::push(T* node)
127{
128 if (!m_head) {
129 ASSERT(!m_tail);
130 m_head = node;
131 m_tail = node;
132 node->setPrev(0);
133 node->setNext(0);
134 return;
135 }
136
137 ASSERT(m_tail);
138 m_head->setPrev(node);
139 node->setNext(m_head);
140 node->setPrev(0);
141 m_head = node;
142}
143
144template<typename T> inline void DoublyLinkedList<T>::append(T* node)
145{
146 if (!m_tail) {
147 ASSERT(!m_head);
148 m_head = node;
149 m_tail = node;
150 node->setPrev(0);
151 node->setNext(0);
152 return;
153 }
154
155 ASSERT(m_head);
156 m_tail->setNext(node);
157 node->setPrev(m_tail);
158 node->setNext(0);
159 m_tail = node;
160}
161
162template<typename T> inline void DoublyLinkedList<T>::remove(T* node)
163{
164 if (node->prev()) {
165 ASSERT(node != m_head);
166 node->prev()->setNext(node->next());
167 } else {
168 ASSERT(node == m_head);
169 m_head = node->next();
170 }
171
172 if (node->next()) {
173 ASSERT(node != m_tail);
174 node->next()->setPrev(node->prev());
175 } else {
176 ASSERT(node == m_tail);
177 m_tail = node->prev();
178 }
179}
180
181template<typename T> inline T* DoublyLinkedList<T>::removeHead()
182{
183 T* node = head();
184 if (node)
185 remove(node);
186 return node;
187}
188
189template<typename T> inline void DoublyLinkedList<T>::append(DoublyLinkedList<T>& other)
190{
191 if (!other.head())
192 return;
193
194 if (!head()) {
195 m_head = other.head();
196 m_tail = other.tail();
197 other.clear();
198 return;
199 }
200
201 ASSERT(tail());
202 ASSERT(other.head());
203 T* otherHead = other.head();
204 T* otherTail = other.tail();
205 other.clear();
206
207 ASSERT(!m_tail->next());
208 m_tail->setNext(otherHead);
209 ASSERT(!otherHead->prev());
210 otherHead->setPrev(m_tail);
211 m_tail = otherTail;
212}
213
214} // namespace WTF
215
216using WTF::DoublyLinkedListNode;
217using WTF::DoublyLinkedList;
218