OLD | NEW |
| (Empty) |
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 | |
29 namespace WTF { | |
30 | |
31 // This class allows nodes to share code without dictating data member layout. | |
32 template<typename T> class DoublyLinkedListNode { | |
33 public: | |
34 DoublyLinkedListNode(); | |
35 | |
36 void setPrev(T*); | |
37 void setNext(T*); | |
38 | |
39 T* prev() const; | |
40 T* next() const; | |
41 }; | |
42 | |
43 template<typename T> inline DoublyLinkedListNode<T>::DoublyLinkedListNode() | |
44 { | |
45 setPrev(0); | |
46 setNext(0); | |
47 } | |
48 | |
49 template<typename T> inline void DoublyLinkedListNode<T>::setPrev(T* prev) | |
50 { | |
51 static_cast<T*>(this)->m_prev = prev; | |
52 } | |
53 | |
54 template<typename T> inline void DoublyLinkedListNode<T>::setNext(T* next) | |
55 { | |
56 static_cast<T*>(this)->m_next = next; | |
57 } | |
58 | |
59 template<typename T> inline T* DoublyLinkedListNode<T>::prev() const | |
60 { | |
61 return static_cast<const T*>(this)->m_prev; | |
62 } | |
63 | |
64 template<typename T> inline T* DoublyLinkedListNode<T>::next() const | |
65 { | |
66 return static_cast<const T*>(this)->m_next; | |
67 } | |
68 | |
69 template<typename T> class DoublyLinkedList { | |
70 public: | |
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 | |
86 private: | |
87 T* m_head; | |
88 T* m_tail; | |
89 }; | |
90 | |
91 template<typename T> inline DoublyLinkedList<T>::DoublyLinkedList() | |
92 : m_head(0) | |
93 , m_tail(0) | |
94 { | |
95 } | |
96 | |
97 template<typename T> inline bool DoublyLinkedList<T>::isEmpty() const | |
98 { | |
99 return !m_head; | |
100 } | |
101 | |
102 template<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 | |
110 template<typename T> inline void DoublyLinkedList<T>::clear() | |
111 { | |
112 m_head = 0; | |
113 m_tail = 0; | |
114 } | |
115 | |
116 template<typename T> inline T* DoublyLinkedList<T>::head() const | |
117 { | |
118 return m_head; | |
119 } | |
120 | |
121 template<typename T> inline T* DoublyLinkedList<T>::tail() const | |
122 { | |
123 return m_tail; | |
124 } | |
125 | |
126 template<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 | |
144 template<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 | |
162 template<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 | |
181 template<typename T> inline T* DoublyLinkedList<T>::removeHead() | |
182 { | |
183 T* node = head(); | |
184 if (node) | |
185 remove(node); | |
186 return node; | |
187 } | |
188 | |
189 } // namespace WTF | |
190 | |
191 using WTF::DoublyLinkedListNode; | |
192 using WTF::DoublyLinkedList; | |
193 | |
194 #endif | |
OLD | NEW |