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 195