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