blob: 0579534b89ff1ce26a0bd8d282fb8820d849d53e [file] [log] [blame]
// Copyright (c) 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
#ifndef SOURCE_UTIL_ILIST_NODE_H_
#define SOURCE_UTIL_ILIST_NODE_H_
#include <cassert>
namespace spvtools {
namespace utils {
template <class NodeType>
class IntrusiveList;
// IntrusiveNodeBase is the base class for nodes in an IntrusiveList.
// See the comments in ilist.h on how to use the class.
template <class NodeType>
class IntrusiveNodeBase {
public:
// Creates a new node that is not in a list.
inline IntrusiveNodeBase();
inline IntrusiveNodeBase(const IntrusiveNodeBase&);
inline IntrusiveNodeBase& operator=(const IntrusiveNodeBase&);
inline IntrusiveNodeBase(IntrusiveNodeBase&& that);
// Destroys a node. It is an error to destroy a node that is part of a
// list, unless it is a sentinel.
virtual ~IntrusiveNodeBase();
IntrusiveNodeBase& operator=(IntrusiveNodeBase&& that);
// Returns true if |this| is in a list.
inline bool IsInAList() const;
// Returns the node that comes after the given node in the list, if one
// exists. If the given node is not in a list or is at the end of the list,
// the return value is nullptr.
inline NodeType* NextNode() const;
// Returns the node that comes before the given node in the list, if one
// exists. If the given node is not in a list or is at the start of the
// list, the return value is nullptr.
inline NodeType* PreviousNode() const;
// Inserts the given node immediately before |pos| in the list.
// If the given node is already in a list, it will first be removed
// from that list.
//
// It is assumed that the given node is of type NodeType. It is an error if
// |pos| is not already in a list.
inline void InsertBefore(NodeType* pos);
// Inserts the given node immediately after |pos| in the list.
// If the given node is already in a list, it will first be removed
// from that list.
//
// It is assumed that the given node is of type NodeType. It is an error if
// |pos| is not already in a list, or if |pos| is equal to |this|.
inline void InsertAfter(NodeType* pos);
// Removes the given node from the list. It is assumed that the node is
// in a list. Note that this does not free any storage related to the node,
// it becomes the caller's responsibility to free the storage.
inline void RemoveFromList();
protected:
// Replaces |this| with |target|. |this| is a sentinel if and only if
// |target| is also a sentinel.
//
// If neither node is a sentinel, |target| takes
// the place of |this|. It is assumed that |target| is not in a list.
//
// If both are sentinels, then it will cause all of the
// nodes in the list containing |this| to be moved to the list containing
// |target|. In this case, it is assumed that |target| is an empty list.
//
// No storage will be deleted.
void ReplaceWith(NodeType* target);
// Returns true if |this| is the sentinel node of an empty list.
bool IsEmptyList();
// The pointers to the next and previous nodes in the list.
// If the current node is not part of a list, then |next_node_| and
// |previous_node_| are equal to |nullptr|.
NodeType* next_node_;
NodeType* previous_node_;
// Only true for the sentinel node stored in the list itself.
bool is_sentinel_;
friend IntrusiveList<NodeType>;
};
// Implementation of IntrusiveNodeBase
template <class NodeType>
inline IntrusiveNodeBase<NodeType>::IntrusiveNodeBase()
: next_node_(nullptr), previous_node_(nullptr), is_sentinel_(false) {}
template <class NodeType>
inline IntrusiveNodeBase<NodeType>::IntrusiveNodeBase(
const IntrusiveNodeBase&) {
next_node_ = nullptr;
previous_node_ = nullptr;
is_sentinel_ = false;
}
template <class NodeType>
inline IntrusiveNodeBase<NodeType>& IntrusiveNodeBase<NodeType>::operator=(
const IntrusiveNodeBase&) {
assert(!is_sentinel_);
if (IsInAList()) {
RemoveFromList();
}
return *this;
}
template <class NodeType>
inline IntrusiveNodeBase<NodeType>::IntrusiveNodeBase(IntrusiveNodeBase&& that)
: next_node_(nullptr),
previous_node_(nullptr),
is_sentinel_(that.is_sentinel_) {
if (is_sentinel_) {
next_node_ = this;
previous_node_ = this;
}
that.ReplaceWith(this);
}
template <class NodeType>
IntrusiveNodeBase<NodeType>::~IntrusiveNodeBase() {
assert(is_sentinel_ || !IsInAList());
}
template <class NodeType>
IntrusiveNodeBase<NodeType>& IntrusiveNodeBase<NodeType>::operator=(
IntrusiveNodeBase&& that) {
that.ReplaceWith(this);
return *this;
}
template <class NodeType>
inline bool IntrusiveNodeBase<NodeType>::IsInAList() const {
return next_node_ != nullptr;
}
template <class NodeType>
inline NodeType* IntrusiveNodeBase<NodeType>::NextNode() const {
if (!next_node_->is_sentinel_) return next_node_;
return nullptr;
}
template <class NodeType>
inline NodeType* IntrusiveNodeBase<NodeType>::PreviousNode() const {
if (!previous_node_->is_sentinel_) return previous_node_;
return nullptr;
}
template <class NodeType>
inline void IntrusiveNodeBase<NodeType>::InsertBefore(NodeType* pos) {
assert(!this->is_sentinel_ && "Sentinel nodes cannot be moved around.");
assert(pos->IsInAList() && "Pos should already be in a list.");
if (this->IsInAList()) this->RemoveFromList();
this->next_node_ = pos;
this->previous_node_ = pos->previous_node_;
pos->previous_node_ = static_cast<NodeType*>(this);
this->previous_node_->next_node_ = static_cast<NodeType*>(this);
}
template <class NodeType>
inline void IntrusiveNodeBase<NodeType>::InsertAfter(NodeType* pos) {
assert(!this->is_sentinel_ && "Sentinel nodes cannot be moved around.");
assert(pos->IsInAList() && "Pos should already be in a list.");
assert(this != pos && "Can't insert a node after itself.");
if (this->IsInAList()) {
this->RemoveFromList();
}
this->previous_node_ = pos;
this->next_node_ = pos->next_node_;
pos->next_node_ = static_cast<NodeType*>(this);
this->next_node_->previous_node_ = static_cast<NodeType*>(this);
}
template <class NodeType>
inline void IntrusiveNodeBase<NodeType>::RemoveFromList() {
assert(!this->is_sentinel_ && "Sentinel nodes cannot be moved around.");
assert(this->IsInAList() &&
"Cannot remove a node from a list if it is not in a list.");
this->next_node_->previous_node_ = this->previous_node_;
this->previous_node_->next_node_ = this->next_node_;
this->next_node_ = nullptr;
this->previous_node_ = nullptr;
}
template <class NodeType>
void IntrusiveNodeBase<NodeType>::ReplaceWith(NodeType* target) {
if (this->is_sentinel_) {
assert(target->IsEmptyList() &&
"If target is not an empty list, the nodes in that list would not "
"be linked to a sentinel.");
} else {
assert(IsInAList() && "The node being replaced must be in a list.");
assert(!target->is_sentinel_ &&
"Cannot turn a sentinel node into one that is not.");
}
if (!this->IsEmptyList()) {
// Link target into the same position that |this| was in.
target->next_node_ = this->next_node_;
target->previous_node_ = this->previous_node_;
target->next_node_->previous_node_ = target;
target->previous_node_->next_node_ = target;
// Reset |this| to itself default value.
if (!this->is_sentinel_) {
// Reset |this| so that it is not in a list.
this->next_node_ = nullptr;
this->previous_node_ = nullptr;
} else {
// Set |this| so that it is the head of an empty list.
// We cannot treat sentinel nodes like others because it is invalid for
// a sentinel node to not be in a list.
this->next_node_ = static_cast<NodeType*>(this);
this->previous_node_ = static_cast<NodeType*>(this);
}
} else {
// If |this| points to itself, it must be a sentinel node with an empty
// list. Reset |this| so that it is the head of an empty list. We want
// |target| to be the same. The asserts above guarantee that.
}
}
template <class NodeType>
bool IntrusiveNodeBase<NodeType>::IsEmptyList() {
if (next_node_ == this) {
assert(is_sentinel_ &&
"None sentinel nodes should never point to themselves.");
assert(previous_node_ == this &&
"Inconsistency with the previous and next nodes.");
return true;
}
return false;
}
} // namespace utils
} // namespace spvtools
#endif // SOURCE_UTIL_ILIST_NODE_H_