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
40 namespace WTF {
41
42 enum SentinelTag { Sentinel };
43
44 template <typename Node> class SentinelLinkedList {
45 public:
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
56 private:
57 Node m_headSentinel;
58 Node m_tailSentinel;
59 };
60
SentinelLinkedList()61 template <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
begin()72 template <typename Node> inline typename SentinelLinkedList<Node>::iterator SentinelLinkedList<Node>::begin()
73 {
74 return m_headSentinel.next();
75 }
76
end()77 template <typename Node> inline typename SentinelLinkedList<Node>::iterator SentinelLinkedList<Node>::end()
78 {
79 return &m_tailSentinel;
80 }
81
push(Node * node)82 template <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
remove(Node * node)95 template <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
106 using WTF::SentinelLinkedList;
107
108 #endif
109
110