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
31template <typename Node> class DoublyLinkedList {
32public:
33    DoublyLinkedList();
34
35    bool isEmpty();
36
37    Node* head();
38
39    void append(Node*);
40    void remove(Node*);
41
42private:
43    Node* m_head;
44    Node* m_tail;
45};
46
47template <typename Node> inline DoublyLinkedList<Node>::DoublyLinkedList()
48    : m_head(0)
49    , m_tail(0)
50{
51}
52
53template <typename Node> inline bool DoublyLinkedList<Node>::isEmpty()
54{
55    return !m_head;
56}
57
58template <typename Node> inline Node* DoublyLinkedList<Node>::head()
59{
60    return m_head;
61}
62
63template <typename Node> inline void DoublyLinkedList<Node>::append(Node* node)
64{
65    if (!m_tail) {
66        ASSERT(!m_head);
67        m_head = node;
68        m_tail = node;
69        node->setPrev(0);
70        node->setNext(0);
71        return;
72    }
73
74    ASSERT(m_head);
75    m_tail->setNext(node);
76    node->setPrev(m_tail);
77    node->setNext(0);
78    m_tail = node;
79}
80
81template <typename Node> inline void DoublyLinkedList<Node>::remove(Node* node)
82{
83    if (node->prev()) {
84        ASSERT(node != m_head);
85        node->prev()->setNext(node->next());
86    } else {
87        ASSERT(node == m_head);
88        m_head = node->next();
89    }
90
91    if (node->next()) {
92        ASSERT(node != m_tail);
93        node->next()->setPrev(node->prev());
94    } else {
95        ASSERT(node == m_tail);
96        m_tail = node->prev();
97    }
98}
99
100} // namespace WTF
101
102using WTF::DoublyLinkedList;
103
104#endif
105