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