LLVM: /work/as-worker-4/publish-doxygen-docs/llvm-project/llvm/include/llvm/ADT/ilist_node.h (original) (raw)

An intrusive list node.

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 template parameter. This also enables the isSentinel() function. The same option must be passed to the intrusive list. (ilist_sentinel_tracking 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

When the ilist_parent option is passed to an ilist_node and the owning ilist, each node contains a pointer to the ilist's owner. This adds getParent() and setParent(ParentTy*) methods to the ilist_node, which will be used for node access by the ilist if the node class publicly inherits from ilist_node_with_parent. By default, setParent() is not automatically called by the ilist; a SymbolTableList will call setParent() on inserted nodes, but the sentinel must still be manually set after the list is created (e.g. SymTabList.end()->setParent(Parent)).

The primary benefit of using ilist_parent is that a parent pointer will be stored in the sentinel, meaning that you can safely use ilist_iterator::getNodeParent() to get the node parent from any valid (i.e. non-null) iterator, even one that points to a sentinel value.

See is_valid_option for steps on adding a new option.

#ifndef LLVM_ADT_ILIST_NODE_H

#define LLVM_ADT_ILIST_NODE_H

#include <type_traits>

namespace ilist_detail {

struct NodeAccess;

template <class NodeTy, class ParentTy> class node_parent_access {

public:

inline const ParentTy *getParent() const {

return static_cast<const NodeTy *>(this)->getNodeBaseParent();

}

return static_cast<NodeTy *>(this)->getNodeBaseParent();

}

return static_cast<NodeTy *>(this)->setNodeBaseParent(Parent);

}

};

template class node_parent_access<NodeTy, void> {};

}

template <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator;

template <class OptionsT, bool IsReverse, bool IsConst>

class ilist_iterator_w_bits;

template class ilist_sentinel;

template <class OptionsT, bool IsReverse, bool IsConst>

std::conditional_t<OptionsT::has_iterator_bits,

ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>,

ilist_iterator<OptionsT, IsReverse, IsConst>>;

template

class ilist_node_impl

: OptionsT::node_base_type,

public ilist_detail::node_parent_access<ilist_node_impl,

typename OptionsT::parent_ty> {

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;

friend class ilist_detail::node_parent_access<ilist_node_impl,

typename OptionsT::parent_ty>;

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>;

friend class ilist_iterator_w_bits<OptionsT, false, false>;

friend class ilist_iterator_w_bits<OptionsT, false, true>;

friend class ilist_iterator_w_bits<OptionsT, true, false>;

friend class ilist_iterator_w_bits<OptionsT, true, true>;

protected:

private:

return static_cast<ilist_node_impl *>(node_base_type::getPrev());

}

return static_cast<ilist_node_impl *>(node_base_type::getNext());

}

return static_cast<ilist_node_impl *>(node_base_type::getPrev());

}

return static_cast<ilist_node_impl *>(node_base_type::getNext());

}

public:

}

}

using node_base_type::isKnownSentinel;

template

std::enable_if_t<T::is_sentinel_tracking_explicit, bool> isSentinel() const {

return node_base_type::isSentinel();

}

};

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 {

struct NodeAccess {

protected:

template

static ilist_node_impl *getNodePtr(typename OptionsT::pointer N) {

return N;

}

template

static const ilist_node_impl *

getNodePtr(typename OptionsT::const_pointer N) {

return N;

}

template

static typename OptionsT::pointer getValuePtr(ilist_node_impl *N) {

return static_cast<typename OptionsT::pointer>(N);

}

template

static typename OptionsT::const_pointer

getValuePtr(const ilist_node_impl *N) {

return static_cast<typename OptionsT::const_pointer>(N);

}

template

static ilist_node_impl *getPrev(ilist_node_impl &N) {

return N.getPrev();

}

template

static ilist_node_impl *getNext(ilist_node_impl &N) {

return N.getNext();

}

template

static const ilist_node_impl *

getPrev(const ilist_node_impl &N) {

return N.getPrev();

}

template

static const ilist_node_impl *

getNext(const ilist_node_impl &N) {

return N.getNext();

}

};

template struct SpecificNodeAccess : NodeAccess {

protected:

using pointer = typename OptionsT::pointer;

using const_pointer = typename OptionsT::const_pointer;

using node_type = ilist_node_impl;

}

}

}

}

};

}

template

class ilist_sentinel : public ilist_node_impl {

public:

this->initializeSentinel();

}

this->setPrev(this);

this->setNext(this);

}

bool empty() const { return this == this->getPrev(); }

};

template <typename NodeTy, typename ParentTy, class... Options>

class ilist_node_with_parent : public ilist_node<NodeTy, Options...> {

protected:

private:

const ParentTy *getNodeParent() const {

return static_cast<const NodeTy *>(this)->getParent();

}

public:

const auto &List =

getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));

return List.getPrevNode(*static_cast<NodeTy *>(this));

}

}

const auto &List =

getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));

return List.getNextNode(*static_cast<NodeTy *>(this));

}

}

};

}

#endif

const ParentTy * getParent() const

void setParent(ParentTy *Parent)

ilist_node_impl()=default

ilist_select_iterator_type< OptionsT, false, true > const_self_iterator

ilist_select_iterator_type< OptionsT, true, false > reverse_self_iterator

reverse_self_iterator getReverseIterator()

std::enable_if_t< T::is_sentinel_tracking_explicit, bool > isSentinel() const

Check whether this is the sentinel node.

ilist_select_iterator_type< OptionsT, true, true > const_reverse_self_iterator

self_iterator getIterator()

ilist_select_iterator_type< OptionsT, false, false > self_iterator

NodeTy * getNextNode()

Get the next node, or nullptr for the list tail.

ilist_node_with_parent()=default

This is an optimization pass for GlobalISel generic memory operations.

std::conditional_t< OptionsT::has_iterator_bits, ilist_iterator_w_bits< OptionsT, IsReverse, IsConst >, ilist_iterator< OptionsT, IsReverse, IsConst > > ilist_select_iterator_type

static ilist_node_impl< OptionsT > * getPrev(ilist_node_impl< OptionsT > &N)

static ilist_node_impl< OptionsT > * getNext(ilist_node_impl< OptionsT > &N)

static ilist_node_impl< OptionsT > * getNodePtr(typename OptionsT::pointer N)

static OptionsT::pointer getValuePtr(ilist_node_impl< OptionsT > *N)

static pointer getValuePtr(node_type *N)

typename OptionsT::const_pointer const_pointer

ilist_node_impl< OptionsT > node_type

static node_type * getNodePtr(pointer N)

typename OptionsT::pointer pointer