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