| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2011 Apple Inc. All rights reserved. | 2 * Copyright (C) 2011 Apple Inc. All rights reserved. |
| 3 * | 3 * |
| 4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
| 5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
| 6 * are met: | 6 * are met: |
| 7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
| 8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
| 9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
| 10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
| (...skipping 11 matching lines...) Expand all Loading... |
| 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF | 22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF |
| 23 * THE POSSIBILITY OF SUCH DAMAGE. | 23 * THE POSSIBILITY OF SUCH DAMAGE. |
| 24 */ | 24 */ |
| 25 | 25 |
| 26 #ifndef DoublyLinkedList_h | 26 #ifndef DoublyLinkedList_h |
| 27 #define DoublyLinkedList_h | 27 #define DoublyLinkedList_h |
| 28 | 28 |
| 29 namespace WTF { | 29 namespace WTF { |
| 30 | 30 |
| 31 // This class allows nodes to share code without dictating data member layout. | 31 // This class allows nodes to share code without dictating data member layout. |
| 32 template<typename T> class DoublyLinkedListNode { | 32 template <typename T> |
| 33 public: | 33 class DoublyLinkedListNode { |
| 34 DoublyLinkedListNode(); | 34 public: |
| 35 DoublyLinkedListNode(); |
| 35 | 36 |
| 36 void setPrev(T*); | 37 void setPrev(T*); |
| 37 void setNext(T*); | 38 void setNext(T*); |
| 38 | 39 |
| 39 T* prev() const; | 40 T* prev() const; |
| 40 T* next() const; | 41 T* next() const; |
| 41 }; | 42 }; |
| 42 | 43 |
| 43 template<typename T> inline DoublyLinkedListNode<T>::DoublyLinkedListNode() | 44 template <typename T> |
| 44 { | 45 inline DoublyLinkedListNode<T>::DoublyLinkedListNode() { |
| 45 setPrev(0); | 46 setPrev(0); |
| 46 setNext(0); | 47 setNext(0); |
| 47 } | 48 } |
| 48 | 49 |
| 49 template<typename T> inline void DoublyLinkedListNode<T>::setPrev(T* prev) | 50 template <typename T> |
| 50 { | 51 inline void DoublyLinkedListNode<T>::setPrev(T* prev) { |
| 51 static_cast<T*>(this)->m_prev = prev; | 52 static_cast<T*>(this)->m_prev = prev; |
| 52 } | 53 } |
| 53 | 54 |
| 54 template<typename T> inline void DoublyLinkedListNode<T>::setNext(T* next) | 55 template <typename T> |
| 55 { | 56 inline void DoublyLinkedListNode<T>::setNext(T* next) { |
| 56 static_cast<T*>(this)->m_next = next; | 57 static_cast<T*>(this)->m_next = next; |
| 57 } | 58 } |
| 58 | 59 |
| 59 template<typename T> inline T* DoublyLinkedListNode<T>::prev() const | 60 template <typename T> |
| 60 { | 61 inline T* DoublyLinkedListNode<T>::prev() const { |
| 61 return static_cast<const T*>(this)->m_prev; | 62 return static_cast<const T*>(this)->m_prev; |
| 62 } | 63 } |
| 63 | 64 |
| 64 template<typename T> inline T* DoublyLinkedListNode<T>::next() const | 65 template <typename T> |
| 65 { | 66 inline T* DoublyLinkedListNode<T>::next() const { |
| 66 return static_cast<const T*>(this)->m_next; | 67 return static_cast<const T*>(this)->m_next; |
| 67 } | 68 } |
| 68 | 69 |
| 69 template<typename T> class DoublyLinkedList { | 70 template <typename T> |
| 70 public: | 71 class DoublyLinkedList { |
| 71 DoublyLinkedList(); | 72 public: |
| 73 DoublyLinkedList(); |
| 72 | 74 |
| 73 bool isEmpty() const; | 75 bool isEmpty() const; |
| 74 size_t size() const; // This is O(n). | 76 size_t size() const; // This is O(n). |
| 75 void clear(); | 77 void clear(); |
| 76 | 78 |
| 77 T* head() const; | 79 T* head() const; |
| 78 T* removeHead(); | 80 T* removeHead(); |
| 79 | 81 |
| 80 T* tail() const; | 82 T* tail() const; |
| 81 | 83 |
| 82 void push(T*); | 84 void push(T*); |
| 83 void append(T*); | 85 void append(T*); |
| 84 void remove(T*); | 86 void remove(T*); |
| 85 | 87 |
| 86 private: | 88 private: |
| 87 T* m_head; | 89 T* m_head; |
| 88 T* m_tail; | 90 T* m_tail; |
| 89 }; | 91 }; |
| 90 | 92 |
| 91 template<typename T> inline DoublyLinkedList<T>::DoublyLinkedList() | 93 template <typename T> |
| 92 : m_head(0) | 94 inline DoublyLinkedList<T>::DoublyLinkedList() |
| 93 , m_tail(0) | 95 : m_head(0), m_tail(0) { |
| 94 { | |
| 95 } | 96 } |
| 96 | 97 |
| 97 template<typename T> inline bool DoublyLinkedList<T>::isEmpty() const | 98 template <typename T> |
| 98 { | 99 inline bool DoublyLinkedList<T>::isEmpty() const { |
| 99 return !m_head; | 100 return !m_head; |
| 100 } | 101 } |
| 101 | 102 |
| 102 template<typename T> inline size_t DoublyLinkedList<T>::size() const | 103 template <typename T> |
| 103 { | 104 inline size_t DoublyLinkedList<T>::size() const { |
| 104 size_t size = 0; | 105 size_t size = 0; |
| 105 for (T* node = m_head; node; node = node->next()) | 106 for (T* node = m_head; node; node = node->next()) |
| 106 ++size; | 107 ++size; |
| 107 return size; | 108 return size; |
| 108 } | 109 } |
| 109 | 110 |
| 110 template<typename T> inline void DoublyLinkedList<T>::clear() | 111 template <typename T> |
| 111 { | 112 inline void DoublyLinkedList<T>::clear() { |
| 112 m_head = 0; | 113 m_head = 0; |
| 113 m_tail = 0; | 114 m_tail = 0; |
| 114 } | 115 } |
| 115 | 116 |
| 116 template<typename T> inline T* DoublyLinkedList<T>::head() const | 117 template <typename T> |
| 117 { | 118 inline T* DoublyLinkedList<T>::head() const { |
| 118 return m_head; | 119 return m_head; |
| 119 } | 120 } |
| 120 | 121 |
| 121 template<typename T> inline T* DoublyLinkedList<T>::tail() const | 122 template <typename T> |
| 122 { | 123 inline T* DoublyLinkedList<T>::tail() const { |
| 123 return m_tail; | 124 return m_tail; |
| 124 } | 125 } |
| 125 | 126 |
| 126 template<typename T> inline void DoublyLinkedList<T>::push(T* node) | 127 template <typename T> |
| 127 { | 128 inline void DoublyLinkedList<T>::push(T* node) { |
| 128 if (!m_head) { | 129 if (!m_head) { |
| 129 ASSERT(!m_tail); | 130 ASSERT(!m_tail); |
| 130 m_head = node; | 131 m_head = node; |
| 131 m_tail = node; | 132 m_tail = node; |
| 132 node->setPrev(0); | 133 node->setPrev(0); |
| 133 node->setNext(0); | 134 node->setNext(0); |
| 134 return; | 135 return; |
| 135 } | 136 } |
| 136 | 137 |
| 137 ASSERT(m_tail); | 138 ASSERT(m_tail); |
| 138 m_head->setPrev(node); | 139 m_head->setPrev(node); |
| 139 node->setNext(m_head); | 140 node->setNext(m_head); |
| 140 node->setPrev(0); | 141 node->setPrev(0); |
| 141 m_head = node; | 142 m_head = node; |
| 142 } | 143 } |
| 143 | 144 |
| 144 template<typename T> inline void DoublyLinkedList<T>::append(T* node) | 145 template <typename T> |
| 145 { | 146 inline void DoublyLinkedList<T>::append(T* node) { |
| 146 if (!m_tail) { | 147 if (!m_tail) { |
| 147 ASSERT(!m_head); | 148 ASSERT(!m_head); |
| 148 m_head = node; | 149 m_head = node; |
| 149 m_tail = node; | 150 m_tail = node; |
| 150 node->setPrev(0); | 151 node->setPrev(0); |
| 151 node->setNext(0); | 152 node->setNext(0); |
| 152 return; | 153 return; |
| 153 } | 154 } |
| 154 | 155 |
| 155 ASSERT(m_head); | 156 ASSERT(m_head); |
| 156 m_tail->setNext(node); | 157 m_tail->setNext(node); |
| 157 node->setPrev(m_tail); | 158 node->setPrev(m_tail); |
| 158 node->setNext(0); | 159 node->setNext(0); |
| 159 m_tail = node; | 160 m_tail = node; |
| 160 } | 161 } |
| 161 | 162 |
| 162 template<typename T> inline void DoublyLinkedList<T>::remove(T* node) | 163 template <typename T> |
| 163 { | 164 inline void DoublyLinkedList<T>::remove(T* node) { |
| 164 if (node->prev()) { | 165 if (node->prev()) { |
| 165 ASSERT(node != m_head); | 166 ASSERT(node != m_head); |
| 166 node->prev()->setNext(node->next()); | 167 node->prev()->setNext(node->next()); |
| 167 } else { | 168 } else { |
| 168 ASSERT(node == m_head); | 169 ASSERT(node == m_head); |
| 169 m_head = node->next(); | 170 m_head = node->next(); |
| 170 } | 171 } |
| 171 | 172 |
| 172 if (node->next()) { | 173 if (node->next()) { |
| 173 ASSERT(node != m_tail); | 174 ASSERT(node != m_tail); |
| 174 node->next()->setPrev(node->prev()); | 175 node->next()->setPrev(node->prev()); |
| 175 } else { | 176 } else { |
| 176 ASSERT(node == m_tail); | 177 ASSERT(node == m_tail); |
| 177 m_tail = node->prev(); | 178 m_tail = node->prev(); |
| 178 } | 179 } |
| 179 } | 180 } |
| 180 | 181 |
| 181 template<typename T> inline T* DoublyLinkedList<T>::removeHead() | 182 template <typename T> |
| 182 { | 183 inline T* DoublyLinkedList<T>::removeHead() { |
| 183 T* node = head(); | 184 T* node = head(); |
| 184 if (node) | 185 if (node) |
| 185 remove(node); | 186 remove(node); |
| 186 return node; | 187 return node; |
| 187 } | 188 } |
| 188 | 189 |
| 189 } // namespace WTF | 190 } // namespace WTF |
| 190 | 191 |
| 191 using WTF::DoublyLinkedListNode; | 192 using WTF::DoublyLinkedListNode; |
| 192 using WTF::DoublyLinkedList; | 193 using WTF::DoublyLinkedList; |
| 193 | 194 |
| 194 #endif | 195 #endif |
| OLD | NEW |