LLVM  14.0.0git
/home/buildbot/as-worker-4/publish-doxygen-docs/llvm-project/llvm/include/llvm/ADT/ilist_node.h

An intrusive list node.A base class to enable membership in intrusive lists, including simple_ilist, iplist, and ilist. The first template parameter is the value_type for the list.

An ilist node can be configured with compile-time options to change behaviour and/or add API.

By default, an ilist_node knows whether it is the list sentinel (an instance of ilist_sentinel) if and only if LLVM_ENABLE_ABI_BREAKING_CHECKS. The function isKnownSentinel() always returns false tracking is off. Sentinel tracking steals a bit from the "prev" link, which adds a mask operation when decrementing an iterator, but enables bug-finding assertions in ilist_iterator.

To turn sentinel tracking on all the time, pass in the ilist_sentinel_tracking<true> template parameter. This also enables the isSentinel() function. The same option must be passed to the intrusive list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the time.)

A type can inherit from ilist_node multiple times by passing in different ilist_tag options. This allows a single instance to be inserted into multiple lists simultaneously, where each list is given the same tag.

struct A {}; struct B {}; struct N : ilist_node<N, ilist_tag>, ilist_node<N, ilist_tag> {};

void foo() { simple_ilist<N, ilist_tag> ListA; simple_ilist<N, ilist_tag> ListB; N N1; ListA.push_back(N1); ListB.push_back(N1); } \endexample

See is_valid_option for steps on adding a new option.

//===- llvm/ADT/ilist_node.h - Intrusive Linked List Helper -----*- C++ -*-===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file defines the ilist_node class template, which is a convenient
// base class for creating classes that can be used with ilists.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_ADT_ILIST_NODE_H
#define LLVM_ADT_ILIST_NODE_H
namespace llvm {
namespace ilist_detail {
struct NodeAccess;
} // end namespace ilist_detail
template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;
template <class OptionsT> class ilist_sentinel;
/// Implementation for an ilist node.
///
/// Templated on an appropriate \a ilist_detail::node_options, usually computed
/// by \a ilist_detail::compute_node_options.
///
/// This is a wrapper around \a ilist_node_base whose main purpose is to
/// provide type safety: you can't insert nodes of \a ilist_node_impl into the
/// wrong \a simple_ilist or \a iplist.
template <class OptionsT> class ilist_node_impl : OptionsT::node_base_type {
using value_type = typename OptionsT::value_type;
using node_base_type = typename OptionsT::node_base_type;
using list_base_type = typename OptionsT::list_base_type;
friend typename OptionsT::list_base_type;
friend struct ilist_detail::NodeAccess;
friend class ilist_sentinel<OptionsT>;
friend class ilist_iterator<OptionsT, false, false>;
friend class ilist_iterator<OptionsT, false, true>;
friend class ilist_iterator<OptionsT, true, false>;
friend class ilist_iterator<OptionsT, true, true>;
protected:
ilist_node_impl() = default;
private:
ilist_node_impl *getPrev() {
return static_cast<ilist_node_impl *>(node_base_type::getPrev());
}
ilist_node_impl *getNext() {
return static_cast<ilist_node_impl *>(node_base_type::getNext());
}
const ilist_node_impl *getPrev() const {
return static_cast<ilist_node_impl *>(node_base_type::getPrev());
}
const ilist_node_impl *getNext() const {
return static_cast<ilist_node_impl *>(node_base_type::getNext());
}
void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); }
void setNext(ilist_node_impl *N) { node_base_type::setNext(N); }
public:
return reverse_self_iterator(*this);
}
}
// Under-approximation, but always available for assertions.
using node_base_type::isKnownSentinel;
/// Check whether this is the sentinel node.
///
/// This requires sentinel tracking to be explicitly enabled. Use the
/// ilist_sentinel_tracking<true> option to get this API.
bool isSentinel() const {
static_assert(OptionsT::is_sentinel_tracking_explicit,
"Use ilist_sentinel_tracking<true> to enable isSentinel()");
}
};
/// An intrusive list node.
///
/// A base class to enable membership in intrusive lists, including \a
/// simple_ilist, \a iplist, and \a ilist. The first template parameter is the
/// \a value_type for the list.
///
/// An ilist node can be configured with compile-time options to change
/// behaviour and/or add API.
///
/// By default, an \a ilist_node knows whether it is the list sentinel (an
/// instance of \a ilist_sentinel) if and only if
/// LLVM_ENABLE_ABI_BREAKING_CHECKS. The function \a isKnownSentinel() always
/// returns \c false tracking is off. Sentinel tracking steals a bit from the
/// "prev" link, which adds a mask operation when decrementing an iterator, but
/// enables bug-finding assertions in \a ilist_iterator.
///
/// To turn sentinel tracking on all the time, pass in the
/// ilist_sentinel_tracking<true> template parameter. This also enables the \a
/// isSentinel() function. The same option must be passed to the intrusive
/// list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the
/// time.)
///
/// A type can inherit from ilist_node multiple times by passing in different
/// \a ilist_tag options. This allows a single instance to be inserted into
/// multiple lists simultaneously, where each list is given the same tag.
///
/// \example
/// struct A {};
/// struct B {};
/// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {};
///
/// void foo() {
/// simple_ilist<N, ilist_tag<A>> ListA;
/// simple_ilist<N, ilist_tag<B>> ListB;
/// N N1;
/// ListA.push_back(N1);
/// ListB.push_back(N1);
/// }
/// \endexample
///
/// See \a is_valid_option for steps on adding a new option.
template <class T, class... Options>
class ilist_node
: public ilist_node_impl<
typename ilist_detail::compute_node_options<T, Options...>::type> {
static_assert(ilist_detail::check_options<Options...>::value,
"Unrecognized node option!");
};
namespace ilist_detail {
/// An access class for ilist_node private API.
///
/// This gives access to the private parts of ilist nodes. Nodes for an ilist
/// should friend this class if they inherit privately from ilist_node.
///
/// Using this class outside of the ilist implementation is unsupported.
struct NodeAccess {
protected:
template <class OptionsT>
static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) {
return N;
}
template <class OptionsT>
static const ilist_node_impl<OptionsT> *
getNodePtr(typename OptionsT::const_pointer N) {
return N;
}
template <class OptionsT>
static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) {
return static_cast<typename OptionsT::pointer>(N);
}
template <class OptionsT>
static typename OptionsT::const_pointer
getValuePtr(const ilist_node_impl<OptionsT> *N) {
return static_cast<typename OptionsT::const_pointer>(N);
}
template <class OptionsT>
static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) {
return N.getPrev();
}
template <class OptionsT>
static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) {
return N.getNext();
}
template <class OptionsT>
static const ilist_node_impl<OptionsT> *
getPrev(const ilist_node_impl<OptionsT> &N) {
return N.getPrev();
}
template <class OptionsT>
static const ilist_node_impl<OptionsT> *
getNext(const ilist_node_impl<OptionsT> &N) {
return N.getNext();
}
};
template <class OptionsT> struct SpecificNodeAccess : NodeAccess {
protected:
using pointer = typename OptionsT::pointer;
using const_pointer = typename OptionsT::const_pointer;
using node_type = ilist_node_impl<OptionsT>;
return NodeAccess::getNodePtr<OptionsT>(N);
}
return NodeAccess::getNodePtr<OptionsT>(N);
}
return NodeAccess::getValuePtr<OptionsT>(N);
}
return NodeAccess::getValuePtr<OptionsT>(N);
}
};
} // end namespace ilist_detail
template <class OptionsT>
class ilist_sentinel : public ilist_node_impl<OptionsT> {
public:
this->initializeSentinel();
reset();
}
void reset() {
this->setPrev(this);
this->setNext(this);
}
bool empty() const { return this == this->getPrev(); }
};
/// An ilist node that can access its parent list.
///
/// Requires \c NodeTy to have \a getParent() to find the parent node, and the
/// \c ParentTy to have \a getSublistAccess() to get a reference to the list.
template <typename NodeTy, typename ParentTy, class... Options>
class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {
protected:
private:
/// Forward to NodeTy::getParent().
///
/// Note: do not use the name "getParent()". We want a compile error
/// (instead of recursion) when the subclass fails to implement \a
/// getParent().
const ParentTy *getNodeParent() const {
return static_cast<const NodeTy *>(this)->getParent();
}
public:
/// @name Adjacent Node Accessors
/// @{
/// Get the previous node, or \c nullptr for the list head.
NodeTy *getPrevNode() {
// Should be separated to a reused function, but then we couldn't use auto
// (and would need the type of the list).
const auto &List =
getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
return List.getPrevNode(*static_cast<NodeTy *>(this));
}
/// Get the previous node, or \c nullptr for the list head.
const NodeTy *getPrevNode() const {
return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
}
/// Get the next node, or \c nullptr for the list tail.
NodeTy *getNextNode() {
// Should be separated to a reused function, but then we couldn't use auto
// (and would need the type of the list).
const auto &List =
getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
return List.getNextNode(*static_cast<NodeTy *>(this));
}
/// Get the next node, or \c nullptr for the list tail.
const NodeTy *getNextNode() const {
return const_cast<ilist_node_with_parent *>(this)->getNextNode();
}
/// @}
};
} // end namespace llvm
#endif // LLVM_ADT_ILIST_NODE_H

llvm::ilist_node_impl::self_iterator
ilist_iterator< OptionsT, false, false > self_iterator
Definition: ilist_node.h:53
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ilist_node_impl::ilist_iterator< OptionsT, false, false >
friend class ilist_iterator< OptionsT, false, false >
Definition: ilist_node.h:47
llvm::ilist_sentinel::empty
bool empty() const
Definition: ilist_node.h:248
pointer
Replace within non kernel function use of LDS with pointer
Definition: AMDGPUReplaceLDSUseWithPointer.cpp:443
llvm::ilist_detail::NodeAccess::getNext
static ilist_node_impl< OptionsT > * getNext(ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:193
llvm::ilist_node_with_parent::getNextNode
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
Definition: ilist_node.h:288
llvm::ilist_detail::NodeAccess::getNodePtr
static ilist_node_impl< OptionsT > * getNodePtr(typename OptionsT::pointer N)
Definition: ilist_node.h:166
llvm::ilist_detail::SpecificNodeAccess::pointer
typename OptionsT::pointer pointer
Definition: ilist_node.h:212
llvm::ilist_node_impl::getReverseIterator
reverse_self_iterator getReverseIterator()
Definition: ilist_node.h:84
llvm::ilist_node_impl::reverse_self_iterator
ilist_iterator< OptionsT, true, false > reverse_self_iterator
Definition: ilist_node.h:55
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::ilist_node_impl::ilist_iterator< OptionsT, true, false >
friend class ilist_iterator< OptionsT, true, false >
Definition: ilist_node.h:49
llvm::ilist_detail::SpecificNodeAccess::getNodePtr
static node_type * getNodePtr(pointer N)
Definition: ilist_node.h:216
isSentinel
static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE)
Definition: DWARFAcceleratorTable.cpp:425
llvm::ilist_detail::SpecificNodeAccess::getValuePtr
static pointer getValuePtr(node_type *N)
Definition: ilist_node.h:224
llvm::ilist_detail::SpecificNodeAccess::const_pointer
typename OptionsT::const_pointer const_pointer
Definition: ilist_node.h:213
false
Definition: StackSlotColoring.cpp:142
Options
const char LLVMTargetMachineRef LLVMPassBuilderOptionsRef Options
Definition: PassBuilderBindings.cpp:48
llvm::ilist_node_impl::isSentinel
bool isSentinel() const
Check whether this is the sentinel node.
Definition: ilist_node.h:99
llvm::ilist_node_impl::const_self_iterator
ilist_iterator< OptionsT, false, true > const_self_iterator
Definition: ilist_node.h:54
llvm::ilist_detail::SpecificNodeAccess::node_type
ilist_node_impl< OptionsT > node_type
Definition: ilist_node.h:214
llvm::ilist_node_with_parent::ilist_node_with_parent
ilist_node_with_parent()=default
llvm::ilist_node_impl::ilist_node_impl
ilist_node_impl()=default
llvm::ilist_node_with_parent::getPrevNode
NodeTy * getPrevNode()
Definition: ilist_node.h:274
llvm::ilist_sentinel::ilist_sentinel
ilist_sentinel()
Definition: ilist_node.h:238
ilist_node_base.h
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:776
llvm::ilist_node_impl::getIterator
self_iterator getIterator()
Definition: ilist_node.h:81
llvm::ilist_node_impl::const_reverse_self_iterator
ilist_iterator< OptionsT, true, true > const_reverse_self_iterator
Definition: ilist_node.h:56
llvm::ilist_node_impl::ilist_iterator< OptionsT, false, true >
friend class ilist_iterator< OptionsT, false, true >
Definition: ilist_node.h:48
llvm::ilist_node_impl::NodeAccess
friend struct ilist_detail::NodeAccess
Definition: ilist_node.h:45
llvm::ilist_detail::NodeAccess::getValuePtr
static OptionsT::pointer getValuePtr(ilist_node_impl< OptionsT > *N)
Definition: ilist_node.h:177
llvm::ilist_detail::NodeAccess::getPrev
static ilist_node_impl< OptionsT > * getPrev(ilist_node_impl< OptionsT > &N)
Definition: ilist_node.h:188
List
const NodeList & List
Definition: RDFGraph.cpp:201
N
#define N
true
basic Basic Alias true
Definition: BasicAliasAnalysis.cpp:1815
llvm::ilist_sentinel::reset
void reset()
Definition: ilist_node.h:243
llvm::ilist_node_impl::ilist_iterator< OptionsT, true, true >
friend class ilist_iterator< OptionsT, true, true >
Definition: ilist_node.h:50
ilist_node_options.h