17ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//==-- llvm/ADT/ilist_node.h - Intrusive Linked List Helper ------*- C++ -*-==// 27ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 37ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// The LLVM Compiler Infrastructure 47ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 57ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// This file is distributed under the University of Illinois Open Source 67ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// License. See LICENSE.TXT for details. 77ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 87ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 97ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 107ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// This file defines the ilist_node class template, which is a convenient 117ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// base class for creating classes that can be used with ilists. 127ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens// 137ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens//===----------------------------------------------------------------------===// 147ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 157ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#ifndef LLVM_ADT_ILIST_NODE_H 167ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#define LLVM_ADT_ILIST_NODE_H 177ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 187ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#include "llvm/ADT/ilist_node_base.h" 192df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens#include "llvm/ADT/ilist_node_options.h" 207ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 217ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensnamespace llvm { 227ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 232df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensnamespace ilist_detail { 242df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensstruct NodeAccess; 252df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} // end namespace ilist_detail 262df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenstemplate<typename NodeTy> 287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensstruct ilist_traits; 297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 302df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <class OptionsT, bool IsReverse, bool IsConst> class ilist_iterator; 312df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <class OptionsT> class ilist_sentinel; 322df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 332df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Implementation for an ilist node. 342df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 352df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// Templated on an appropriate \a ilist_detail::node_options, usually computed 362df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// by \a ilist_detail::compute_node_options. 372df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 382df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// This is a wrapper around \a ilist_node_base whose main purpose is to 392df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// provide type safety: you can't insert nodes of \a ilist_node_impl into the 402df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// wrong \a simple_ilist or \a iplist. 412df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <class OptionsT> class ilist_node_impl : OptionsT::node_base_type { 422df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef typename OptionsT::value_type value_type; 432df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef typename OptionsT::node_base_type node_base_type; 442df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef typename OptionsT::list_base_type list_base_type; 457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 462df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens friend typename OptionsT::list_base_type; 472df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens friend struct ilist_detail::NodeAccess; 482df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens friend class ilist_sentinel<OptionsT>; 492df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens friend class ilist_iterator<OptionsT, false, false>; 502df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens friend class ilist_iterator<OptionsT, false, true>; 512df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens friend class ilist_iterator<OptionsT, true, false>; 522df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens friend class ilist_iterator<OptionsT, true, true>; 537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensprotected: 552df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens ilist_node_impl() = default; 562df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 572df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef ilist_iterator<OptionsT, false, false> self_iterator; 582df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef ilist_iterator<OptionsT, false, true> const_self_iterator; 592df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef ilist_iterator<OptionsT, true, false> reverse_self_iterator; 602df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef ilist_iterator<OptionsT, true, true> const_reverse_self_iterator; 617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensprivate: 632df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens ilist_node_impl *getPrev() { 642df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return static_cast<ilist_node_impl *>(node_base_type::getPrev()); 657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 662df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens ilist_node_impl *getNext() { 672df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return static_cast<ilist_node_impl *>(node_base_type::getNext()); 687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 702df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens const ilist_node_impl *getPrev() const { 712df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return static_cast<ilist_node_impl *>(node_base_type::getPrev()); 727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 732df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens const ilist_node_impl *getNext() const { 742df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return static_cast<ilist_node_impl *>(node_base_type::getNext()); 757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 772df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens void setPrev(ilist_node_impl *N) { node_base_type::setPrev(N); } 782df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens void setNext(ilist_node_impl *N) { node_base_type::setNext(N); } 797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 812df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens self_iterator getIterator() { return self_iterator(*this); } 822df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens const_self_iterator getIterator() const { return const_self_iterator(*this); } 832df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens reverse_self_iterator getReverseIterator() { 842df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return reverse_self_iterator(*this); 852df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 862df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens const_reverse_self_iterator getReverseIterator() const { 872df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return const_reverse_self_iterator(*this); 887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 902df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens // Under-approximation, but always available for assertions. 912df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens using node_base_type::isKnownSentinel; 922df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 932df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens /// Check whether this is the sentinel node. 942df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens /// 952df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens /// This requires sentinel tracking to be explicitly enabled. Use the 962df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens /// ilist_sentinel_tracking<true> option to get this API. 972df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens bool isSentinel() const { 982df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static_assert(OptionsT::is_sentinel_tracking_explicit, 992df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens "Use ilist_sentinel_tracking<true> to enable isSentinel()"); 1002df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return node_base_type::isSentinel(); 1012df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 1022df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens}; 1032df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 1042df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// An intrusive list node. 1052df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 1062df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// A base class to enable membership in intrusive lists, including \a 1072df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// simple_ilist, \a iplist, and \a ilist. The first template parameter is the 1082df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// \a value_type for the list. 1092df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 1102df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// An ilist node can be configured with compile-time options to change 1112df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// behaviour and/or add API. 1122df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 1132df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// By default, an \a ilist_node knows whether it is the list sentinel (an 1142df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// instance of \a ilist_sentinel) if and only if 1152df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// LLVM_ENABLE_ABI_BREAKING_CHECKS. The function \a isKnownSentinel() always 1162df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// returns \c false tracking is off. Sentinel tracking steals a bit from the 1172df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// "prev" link, which adds a mask operation when decrementing an iterator, but 1182df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// enables bug-finding assertions in \a ilist_iterator. 1192df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 1202df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// To turn sentinel tracking on all the time, pass in the 1212df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// ilist_sentinel_tracking<true> template parameter. This also enables the \a 1222df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// isSentinel() function. The same option must be passed to the intrusive 1232df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// list. (ilist_sentinel_tracking<false> turns sentinel tracking off all the 1242df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// time.) 1252df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 1262df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// A type can inherit from ilist_node multiple times by passing in different 1272df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// \a ilist_tag options. This allows a single instance to be inserted into 1282df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// multiple lists simultaneously, where each list is given the same tag. 1292df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 1302df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// \example 1312df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// struct A {}; 1322df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// struct B {}; 1332df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// struct N : ilist_node<N, ilist_tag<A>>, ilist_node<N, ilist_tag<B>> {}; 1342df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 1352df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// void foo() { 1362df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// simple_ilist<N, ilist_tag<A>> ListA; 1372df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// simple_ilist<N, ilist_tag<B>> ListB; 1382df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// N N1; 1392df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// ListA.push_back(N1); 1402df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// ListB.push_back(N1); 1412df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// } 1422df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// \endexample 1432df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// 1442df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens/// See \a is_valid_option for steps on adding a new option. 1452df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <class T, class... Options> 1462df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensclass ilist_node 1472df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens : public ilist_node_impl< 1482df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typename ilist_detail::compute_node_options<T, Options...>::type> { 1492df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static_assert(ilist_detail::check_options<Options...>::value, 1502df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens "Unrecognized node option!"); 1517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 1527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1532df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensnamespace ilist_detail { 1547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// An access class for ilist_node private API. 1557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 1567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// This gives access to the private parts of ilist nodes. Nodes for an ilist 1577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// should friend this class if they inherit privately from ilist_node. 1587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 1597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Using this class outside of the ilist implementation is unsupported. 1602df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensstruct NodeAccess { 1612df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensprotected: 1622df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <class OptionsT> 1632df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static ilist_node_impl<OptionsT> *getNodePtr(typename OptionsT::pointer N) { 1642df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return N; 1652df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 1662df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <class OptionsT> 1672df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static const ilist_node_impl<OptionsT> * 1682df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens getNodePtr(typename OptionsT::const_pointer N) { 1697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return N; 1707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1712df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <class OptionsT> 1722df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static typename OptionsT::pointer getValuePtr(ilist_node_impl<OptionsT> *N) { 1732df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return static_cast<typename OptionsT::pointer>(N); 1747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1752df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <class OptionsT> 1762df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static typename OptionsT::const_pointer 1772df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens getValuePtr(const ilist_node_impl<OptionsT> *N) { 1782df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return static_cast<typename OptionsT::const_pointer>(N); 1797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 1812df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <class OptionsT> 1822df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static ilist_node_impl<OptionsT> *getPrev(ilist_node_impl<OptionsT> &N) { 1837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return N.getPrev(); 1847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1852df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <class OptionsT> 1862df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static ilist_node_impl<OptionsT> *getNext(ilist_node_impl<OptionsT> &N) { 1877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return N.getNext(); 1887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1892df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <class OptionsT> 1902df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static const ilist_node_impl<OptionsT> * 1912df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens getPrev(const ilist_node_impl<OptionsT> &N) { 1927ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return N.getPrev(); 1937ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1942df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens template <class OptionsT> 1952df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static const ilist_node_impl<OptionsT> * 1962df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens getNext(const ilist_node_impl<OptionsT> &N) { 1977ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return N.getNext(); 1987ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 1997ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 2007ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2012df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <class OptionsT> struct SpecificNodeAccess : NodeAccess { 2022df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensprotected: 2032df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef typename OptionsT::pointer pointer; 2042df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef typename OptionsT::const_pointer const_pointer; 2052df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens typedef ilist_node_impl<OptionsT> node_type; 2062df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 2072df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static node_type *getNodePtr(pointer N) { 2082df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return NodeAccess::getNodePtr<OptionsT>(N); 2092df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 2102df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static const node_type *getNodePtr(const_pointer N) { 2112df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return NodeAccess::getNodePtr<OptionsT>(N); 2122df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 2132df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static pointer getValuePtr(node_type *N) { 2142df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return NodeAccess::getValuePtr<OptionsT>(N); 2152df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 2162df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens static const_pointer getValuePtr(const node_type *N) { 2172df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens return NodeAccess::getValuePtr<OptionsT>(N); 2182df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens } 2192df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens}; 2202df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens} // end namespace ilist_detail 2212df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens 2222df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <class OptionsT> 2232df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensclass ilist_sentinel : public ilist_node_impl<OptionsT> { 2247ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 2257ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ilist_sentinel() { 2262df178997d17474042e8c3704cc93ab2db6619bfNicolas Capens this->initializeSentinel(); 2277ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens reset(); 2287ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2297ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2307ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens void reset() { 2317ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens this->setPrev(this); 2327ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens this->setNext(this); 2337ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2347ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2357ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens bool empty() const { return this == this->getPrev(); } 2367ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 2377ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2387ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// An ilist node that can access its parent list. 2397ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// 2407ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// Requires \c NodeTy to have \a getParent() to find the parent node, and the 2417ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens/// \c ParentTy to have \a getSublistAccess() to get a reference to the list. 2422df178997d17474042e8c3704cc93ab2db6619bfNicolas Capenstemplate <typename NodeTy, typename ParentTy, class... Options> 2432df178997d17474042e8c3704cc93ab2db6619bfNicolas Capensclass ilist_node_with_parent : public ilist_node<NodeTy, Options...> { 2447ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensprotected: 2457ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens ilist_node_with_parent() = default; 2467ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2477ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capensprivate: 2487ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// Forward to NodeTy::getParent(). 2497ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// 2507ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// Note: do not use the name "getParent()". We want a compile error 2517ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// (instead of recursion) when the subclass fails to implement \a 2527ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// getParent(). 2537ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const ParentTy *getNodeParent() const { 2547ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return static_cast<const NodeTy *>(this)->getParent(); 2557ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2567ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2577ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capenspublic: 2587ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// @name Adjacent Node Accessors 2597ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// @{ 2607ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// \brief Get the previous node, or \c nullptr for the list head. 2617ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NodeTy *getPrevNode() { 2627ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Should be separated to a reused function, but then we couldn't use auto 2637ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // (and would need the type of the list). 2647ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const auto &List = 2657ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr)); 2667ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return List.getPrevNode(*static_cast<NodeTy *>(this)); 2677ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2687ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// \brief Get the previous node, or \c nullptr for the list head. 2697ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const NodeTy *getPrevNode() const { 2707ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return const_cast<ilist_node_with_parent *>(this)->getPrevNode(); 2717ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2727ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2737ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// \brief Get the next node, or \c nullptr for the list tail. 2747ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens NodeTy *getNextNode() { 2757ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // Should be separated to a reused function, but then we couldn't use auto 2767ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens // (and would need the type of the list). 2777ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const auto &List = 2787ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr)); 2797ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return List.getNextNode(*static_cast<NodeTy *>(this)); 2807ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2817ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// \brief Get the next node, or \c nullptr for the list tail. 2827ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens const NodeTy *getNextNode() const { 2837ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens return const_cast<ilist_node_with_parent *>(this)->getNextNode(); 2847ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens } 2857ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens /// @} 2867ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens}; 2877ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2887ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens} // End llvm namespace 2897ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens 2907ad046f5968d4709c3c68d165387d13f1da7bab6Nicolas Capens#endif 291