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//    A SentinelLinkedList is a linked list with dummy head and tail sentinels,
27//    which allow for branch-less insertion and removal, and removal without a
28//    pointer to the list.
29//
30//    Requires: Node is a concrete class with:
31//        Node(SentinelTag);
32//        void setPrev(Node*);
33//        Node* prev();
34//        void setNext(Node*);
35//        Node* next();
36
37#ifndef SentinelLinkedList_h
38#define SentinelLinkedList_h
39
40namespace WTF {
41
42enum SentinelTag { Sentinel };
43
44template <typename Node> class SentinelLinkedList {
45public:
46    typedef Node* iterator;
47
48    SentinelLinkedList();
49
50    void push(Node*);
51    static void remove(Node*);
52
53    iterator begin();
54    iterator end();
55
56private:
57    Node m_headSentinel;
58    Node m_tailSentinel;
59};
60
61template <typename Node> inline SentinelLinkedList<Node>::SentinelLinkedList()
62    : m_headSentinel(Sentinel)
63    , m_tailSentinel(Sentinel)
64{
65    m_headSentinel.setNext(&m_tailSentinel);
66    m_headSentinel.setPrev(0);
67
68    m_tailSentinel.setPrev(&m_headSentinel);
69    m_tailSentinel.setNext(0);
70}
71
72template <typename Node> inline typename SentinelLinkedList<Node>::iterator SentinelLinkedList<Node>::begin()
73{
74    return m_headSentinel.next();
75}
76
77template <typename Node> inline typename SentinelLinkedList<Node>::iterator SentinelLinkedList<Node>::end()
78{
79    return &m_tailSentinel;
80}
81
82template <typename Node> inline void SentinelLinkedList<Node>::push(Node* node)
83{
84    ASSERT(node);
85    Node* prev = &m_headSentinel;
86    Node* next = m_headSentinel.next();
87
88    node->setPrev(prev);
89    node->setNext(next);
90
91    prev->setNext(node);
92    next->setPrev(node);
93}
94
95template <typename Node> inline void SentinelLinkedList<Node>::remove(Node* node)
96{
97    Node* prev = node->prev();
98    Node* next = node->next();
99
100    prev->setNext(next);
101    next->setPrev(prev);
102}
103
104}
105
106using WTF::SentinelLinkedList;
107
108#endif
109
110