1// Copyright (c) 2017 Google Inc.
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15#ifndef SOURCE_UTIL_ILIST_NODE_H_
16#define SOURCE_UTIL_ILIST_NODE_H_
17
18#include <cassert>
19
20namespace spvtools {
21namespace utils {
22
23template <class NodeType>
24class IntrusiveList;
25
26// IntrusiveNodeBase is the base class for nodes in an IntrusiveList.
27// See the comments in ilist.h on how to use the class.
28
29template <class NodeType>
30class IntrusiveNodeBase {
31 public:
32 // Creates a new node that is not in a list.
33 inline IntrusiveNodeBase();
34 inline IntrusiveNodeBase(const IntrusiveNodeBase&);
35 inline IntrusiveNodeBase& operator=(const IntrusiveNodeBase&);
36 inline IntrusiveNodeBase(IntrusiveNodeBase&& that);
37
38 // Destroys a node. It is an error to destroy a node that is part of a
39 // list, unless it is a sentinel.
40 virtual ~IntrusiveNodeBase();
41
42 IntrusiveNodeBase& operator=(IntrusiveNodeBase&& that);
43
44 // Returns true if |this| is in a list.
45 inline bool IsInAList() const;
46
47 // Returns the node that comes after the given node in the list, if one
48 // exists. If the given node is not in a list or is at the end of the list,
49 // the return value is nullptr.
50 inline NodeType* NextNode() const;
51
52 // Returns the node that comes before the given node in the list, if one
53 // exists. If the given node is not in a list or is at the start of the
54 // list, the return value is nullptr.
55 inline NodeType* PreviousNode() const;
56
57 // Inserts the given node immediately before |pos| in the list.
58 // If the given node is already in a list, it will first be removed
59 // from that list.
60 //
61 // It is assumed that the given node is of type NodeType. It is an error if
62 // |pos| is not already in a list.
63 inline void InsertBefore(NodeType* pos);
64
65 // Inserts the given node immediately after |pos| in the list.
66 // If the given node is already in a list, it will first be removed
67 // from that list.
68 //
69 // It is assumed that the given node is of type NodeType. It is an error if
70 // |pos| is not already in a list, or if |pos| is equal to |this|.
71 inline void InsertAfter(NodeType* pos);
72
73 // Removes the given node from the list. It is assumed that the node is
74 // in a list. Note that this does not free any storage related to the node,
75 // it becomes the caller's responsibility to free the storage.
76 inline void RemoveFromList();
77
78 protected:
79 // Replaces |this| with |target|. |this| is a sentinel if and only if
80 // |target| is also a sentinel.
81 //
82 // If neither node is a sentinel, |target| takes
83 // the place of |this|. It is assumed that |target| is not in a list.
84 //
85 // If both are sentinels, then it will cause all of the
86 // nodes in the list containing |this| to be moved to the list containing
87 // |target|. In this case, it is assumed that |target| is an empty list.
88 //
89 // No storage will be deleted.
90 void ReplaceWith(NodeType* target);
91
92 // Returns true if |this| is the sentinel node of an empty list.
93 bool IsEmptyList();
94
95 // The pointers to the next and previous nodes in the list.
96 // If the current node is not part of a list, then |next_node_| and
97 // |previous_node_| are equal to |nullptr|.
98 NodeType* next_node_;
99 NodeType* previous_node_;
100
101 // Only true for the sentinel node stored in the list itself.
102 bool is_sentinel_;
103
104 friend IntrusiveList<NodeType>;
105};
106
107// Implementation of IntrusiveNodeBase
108
109template <class NodeType>
110inline IntrusiveNodeBase<NodeType>::IntrusiveNodeBase()
111 : next_node_(nullptr), previous_node_(nullptr), is_sentinel_(false) {}
112
113template <class NodeType>
114inline IntrusiveNodeBase<NodeType>::IntrusiveNodeBase(
115 const IntrusiveNodeBase&) {
116 next_node_ = nullptr;
117 previous_node_ = nullptr;
118 is_sentinel_ = false;
119}
120
121template <class NodeType>
122inline IntrusiveNodeBase<NodeType>& IntrusiveNodeBase<NodeType>::operator=(
123 const IntrusiveNodeBase&) {
124 assert(!is_sentinel_);
125 if (IsInAList()) {
126 RemoveFromList();
127 }
128 return *this;
129}
130
131template <class NodeType>
132inline IntrusiveNodeBase<NodeType>::IntrusiveNodeBase(IntrusiveNodeBase&& that)
133 : next_node_(nullptr),
134 previous_node_(nullptr),
135 is_sentinel_(that.is_sentinel_) {
136 if (is_sentinel_) {
137 next_node_ = this;
138 previous_node_ = this;
139 }
140 that.ReplaceWith(this);
141}
142
143template <class NodeType>
144IntrusiveNodeBase<NodeType>::~IntrusiveNodeBase() {
145 assert(is_sentinel_ || !IsInAList());
146}
147
148template <class NodeType>
149IntrusiveNodeBase<NodeType>& IntrusiveNodeBase<NodeType>::operator=(
150 IntrusiveNodeBase&& that) {
151 that.ReplaceWith(this);
152 return *this;
153}
154
155template <class NodeType>
156inline bool IntrusiveNodeBase<NodeType>::IsInAList() const {
157 return next_node_ != nullptr;
158}
159
160template <class NodeType>
161inline NodeType* IntrusiveNodeBase<NodeType>::NextNode() const {
162 if (!next_node_->is_sentinel_) return next_node_;
163 return nullptr;
164}
165
166template <class NodeType>
167inline NodeType* IntrusiveNodeBase<NodeType>::PreviousNode() const {
168 if (!previous_node_->is_sentinel_) return previous_node_;
169 return nullptr;
170}
171
172template <class NodeType>
173inline void IntrusiveNodeBase<NodeType>::InsertBefore(NodeType* pos) {
174 assert(!this->is_sentinel_ && "Sentinel nodes cannot be moved around.");
175 assert(pos->IsInAList() && "Pos should already be in a list.");
176 if (this->IsInAList()) this->RemoveFromList();
177
178 this->next_node_ = pos;
179 this->previous_node_ = pos->previous_node_;
180 pos->previous_node_ = static_cast<NodeType*>(this);
181 this->previous_node_->next_node_ = static_cast<NodeType*>(this);
182}
183
184template <class NodeType>
185inline void IntrusiveNodeBase<NodeType>::InsertAfter(NodeType* pos) {
186 assert(!this->is_sentinel_ && "Sentinel nodes cannot be moved around.");
187 assert(pos->IsInAList() && "Pos should already be in a list.");
188 assert(this != pos && "Can't insert a node after itself.");
189
190 if (this->IsInAList()) {
191 this->RemoveFromList();
192 }
193
194 this->previous_node_ = pos;
195 this->next_node_ = pos->next_node_;
196 pos->next_node_ = static_cast<NodeType*>(this);
197 this->next_node_->previous_node_ = static_cast<NodeType*>(this);
198}
199
200template <class NodeType>
201inline void IntrusiveNodeBase<NodeType>::RemoveFromList() {
202 assert(!this->is_sentinel_ && "Sentinel nodes cannot be moved around.");
203 assert(this->IsInAList() &&
204 "Cannot remove a node from a list if it is not in a list.");
205
206 this->next_node_->previous_node_ = this->previous_node_;
207 this->previous_node_->next_node_ = this->next_node_;
208 this->next_node_ = nullptr;
209 this->previous_node_ = nullptr;
210}
211
212template <class NodeType>
213void IntrusiveNodeBase<NodeType>::ReplaceWith(NodeType* target) {
214 if (this->is_sentinel_) {
215 assert(target->IsEmptyList() &&
216 "If target is not an empty list, the nodes in that list would not "
217 "be linked to a sentinel.");
218 } else {
219 assert(IsInAList() && "The node being replaced must be in a list.");
220 assert(!target->is_sentinel_ &&
221 "Cannot turn a sentinel node into one that is not.");
222 }
223
224 if (!this->IsEmptyList()) {
225 // Link target into the same position that |this| was in.
226 target->next_node_ = this->next_node_;
227 target->previous_node_ = this->previous_node_;
228 target->next_node_->previous_node_ = target;
229 target->previous_node_->next_node_ = target;
230
231 // Reset |this| to itself default value.
232 if (!this->is_sentinel_) {
233 // Reset |this| so that it is not in a list.
234 this->next_node_ = nullptr;
235 this->previous_node_ = nullptr;
236 } else {
237 // Set |this| so that it is the head of an empty list.
238 // We cannot treat sentinel nodes like others because it is invalid for
239 // a sentinel node to not be in a list.
240 this->next_node_ = static_cast<NodeType*>(this);
241 this->previous_node_ = static_cast<NodeType*>(this);
242 }
243 } else {
244 // If |this| points to itself, it must be a sentinel node with an empty
245 // list. Reset |this| so that it is the head of an empty list. We want
246 // |target| to be the same. The asserts above guarantee that.
247 }
248}
249
250template <class NodeType>
251bool IntrusiveNodeBase<NodeType>::IsEmptyList() {
252 if (next_node_ == this) {
253 assert(is_sentinel_ &&
254 "None sentinel nodes should never point to themselves.");
255 assert(previous_node_ == this &&
256 "Inconsistency with the previous and next nodes.");
257 return true;
258 }
259 return false;
260}
261
262} // namespace utils
263} // namespace spvtools
264
265#endif // SOURCE_UTIL_ILIST_NODE_H_
266