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 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 189} // namespace WTF 190 191using WTF::DoublyLinkedListNode; 192using WTF::DoublyLinkedList; 193 194#endif 195