2 * Copyright (C) 2011 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
26 #ifndef DoublyLinkedList_h
27 #define DoublyLinkedList_h
31 // This class allows nodes to share code without dictating data member layout.
32 template<typename T
> class DoublyLinkedListNode
{
34 DoublyLinkedListNode();
43 template<typename T
> inline DoublyLinkedListNode
<T
>::DoublyLinkedListNode()
49 template<typename T
> inline void DoublyLinkedListNode
<T
>::setPrev(T
* prev
)
51 static_cast<T
*>(this)->m_prev
= prev
;
54 template<typename T
> inline void DoublyLinkedListNode
<T
>::setNext(T
* next
)
56 static_cast<T
*>(this)->m_next
= next
;
59 template<typename T
> inline T
* DoublyLinkedListNode
<T
>::prev() const
61 return static_cast<const T
*>(this)->m_prev
;
64 template<typename T
> inline T
* DoublyLinkedListNode
<T
>::next() const
66 return static_cast<const T
*>(this)->m_next
;
69 template<typename T
> class DoublyLinkedList
{
74 size_t size() const; // This is O(n).
91 template<typename T
> inline DoublyLinkedList
<T
>::DoublyLinkedList()
97 template<typename T
> inline bool DoublyLinkedList
<T
>::isEmpty() const
102 template<typename T
> inline size_t DoublyLinkedList
<T
>::size() const
105 for (T
* node
= m_head
; node
; node
= node
->next())
110 template<typename T
> inline void DoublyLinkedList
<T
>::clear()
116 template<typename T
> inline T
* DoublyLinkedList
<T
>::head() const
121 template<typename T
> inline T
* DoublyLinkedList
<T
>::tail() const
126 template<typename T
> inline void DoublyLinkedList
<T
>::push(T
* node
)
138 m_head
->setPrev(node
);
139 node
->setNext(m_head
);
144 template<typename T
> inline void DoublyLinkedList
<T
>::append(T
* node
)
156 m_tail
->setNext(node
);
157 node
->setPrev(m_tail
);
162 template<typename T
> inline void DoublyLinkedList
<T
>::remove(T
* node
)
165 ASSERT(node
!= m_head
);
166 node
->prev()->setNext(node
->next());
168 ASSERT(node
== m_head
);
169 m_head
= node
->next();
173 ASSERT(node
!= m_tail
);
174 node
->next()->setPrev(node
->prev());
176 ASSERT(node
== m_tail
);
177 m_tail
= node
->prev();
181 template<typename T
> inline T
* DoublyLinkedList
<T
>::removeHead()
191 using WTF::DoublyLinkedListNode
;
192 using WTF::DoublyLinkedList
;