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