Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(703)

Side by Side Diff: Source/WTF/wtf/DoublyLinkedList.h

Issue 14238015: Move Source/WTF/wtf to Source/wtf (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Created 7 years, 8 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
(Empty)
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
29 namespace WTF {
30
31 // This class allows nodes to share code without dictating data member layout.
32 template<typename T> class DoublyLinkedListNode {
33 public:
34 DoublyLinkedListNode();
35
36 void setPrev(T*);
37 void setNext(T*);
38
39 T* prev() const;
40 T* next() const;
41 };
42
43 template<typename T> inline DoublyLinkedListNode<T>::DoublyLinkedListNode()
44 {
45 setPrev(0);
46 setNext(0);
47 }
48
49 template<typename T> inline void DoublyLinkedListNode<T>::setPrev(T* prev)
50 {
51 static_cast<T*>(this)->m_prev = prev;
52 }
53
54 template<typename T> inline void DoublyLinkedListNode<T>::setNext(T* next)
55 {
56 static_cast<T*>(this)->m_next = next;
57 }
58
59 template<typename T> inline T* DoublyLinkedListNode<T>::prev() const
60 {
61 return static_cast<const T*>(this)->m_prev;
62 }
63
64 template<typename T> inline T* DoublyLinkedListNode<T>::next() const
65 {
66 return static_cast<const T*>(this)->m_next;
67 }
68
69 template<typename T> class DoublyLinkedList {
70 public:
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
86 private:
87 T* m_head;
88 T* m_tail;
89 };
90
91 template<typename T> inline DoublyLinkedList<T>::DoublyLinkedList()
92 : m_head(0)
93 , m_tail(0)
94 {
95 }
96
97 template<typename T> inline bool DoublyLinkedList<T>::isEmpty() const
98 {
99 return !m_head;
100 }
101
102 template<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
110 template<typename T> inline void DoublyLinkedList<T>::clear()
111 {
112 m_head = 0;
113 m_tail = 0;
114 }
115
116 template<typename T> inline T* DoublyLinkedList<T>::head() const
117 {
118 return m_head;
119 }
120
121 template<typename T> inline T* DoublyLinkedList<T>::tail() const
122 {
123 return m_tail;
124 }
125
126 template<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
144 template<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
162 template<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
181 template<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
191 using WTF::DoublyLinkedListNode;
192 using WTF::DoublyLinkedList;
193
194 #endif
OLDNEW
« no previous file with comments | « Source/WTF/wtf/Deque.h ('k') | Source/WTF/wtf/DynamicAnnotations.h » ('j') | Source/config.h » ('J')

Powered by Google App Engine
This is Rietveld 408576698