diff options
Diffstat (limited to 'libbase/include')
| -rw-r--r-- | libbase/include/core/adt/ilist_iterator.h | 591 |
1 files changed, 591 insertions, 0 deletions
diff --git a/libbase/include/core/adt/ilist_iterator.h b/libbase/include/core/adt/ilist_iterator.h new file mode 100644 index 0000000..90985d8 --- /dev/null +++ b/libbase/include/core/adt/ilist_iterator.h @@ -0,0 +1,591 @@ +/* + RCC-Project + + Copyright (C) 2026 Richard Qin + + This file is part of RCC-Project. + + RCC-Project is free software; you can redistribute it and/or modify it under + the terms of the GNU General Public License as published by the Free + Software Foundation; either version 3 of the License, or (at your option) any + later version. + + RCC-Project is distributed in the hope that it will be useful, but WITHOUT ANY + WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR + A PARTICULAR PURPOSE. See the GNU General Public License for more details. + + You should have received a copy of the GNU General Public License along with + RCC-Project; see the file COPYING. If not see + <http://www.gnu.org/licenses/>. +*/ + +//===- core/adt/ilist_iterator.h - Intrusive List Iterator ------*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef LIBBASE_ADT_ILIST_ITERATOR_H +#define LIBBASE_ADT_ILIST_ITERATOR_H + +#include "core/adt/ilist_node.h" +#include <cassert> +#include <cstddef> +#include <iterator> +#include <type_traits> + +namespace libbase +{ + +namespace ilist_detail +{ + +/// Find const-correct node types. +template <class OptionsT, bool IsConst> struct IteratorTraits; +template <class OptionsT> struct IteratorTraits<OptionsT, false> +{ + using value_type = typename OptionsT::value_type; + using pointer = typename OptionsT::pointer; + using reference = typename OptionsT::reference; + using node_pointer = ilist_node_impl<OptionsT> *; + using node_reference = ilist_node_impl<OptionsT> &; +}; +template <class OptionsT> struct IteratorTraits<OptionsT, true> +{ + using value_type = const typename OptionsT::value_type; + using pointer = typename OptionsT::const_pointer; + using reference = typename OptionsT::const_reference; + using node_pointer = const ilist_node_impl<OptionsT> *; + using node_reference = const ilist_node_impl<OptionsT> &; +}; + +template <bool IsReverse> struct IteratorHelper; +template <> struct IteratorHelper<false> : ilist_detail::NodeAccess +{ + using Access = ilist_detail::NodeAccess; + + template <class T> + static void + increment (T *&I) + { + I = Access::getNext (*I); + } + template <class T> + static void + decrement (T *&I) + { + I = Access::getPrev (*I); + } +}; +template <> struct IteratorHelper<true> : ilist_detail::NodeAccess +{ + using Access = ilist_detail::NodeAccess; + + template <class T> + static void + increment (T *&I) + { + I = Access::getPrev (*I); + } + template <class T> + static void + decrement (T *&I) + { + I = Access::getNext (*I); + } +}; + +/// Mixin class used to add a \a getNodeParent() function to iterators iff the +/// list uses \a ilist_parent, calling through to the node's \a getParent(). For +/// more details see \a ilist_node. +template <class IteratorTy, class ParentTy, bool IsConst> +class iterator_parent_access; +template <class IteratorTy, class ParentTy> +class iterator_parent_access<IteratorTy, ParentTy, true> +{ +public: + inline const ParentTy * + getNodeParent () const + { + return static_cast<const IteratorTy *> (this)->NodePtr->getParent (); + } +}; +template <class IteratorTy, class ParentTy> +class iterator_parent_access<IteratorTy, ParentTy, false> +{ +public: + inline ParentTy * + getNodeParent () const + { + return static_cast<const IteratorTy *> (this)->NodePtr->getParent (); + } +}; +template <class IteratorTy> class iterator_parent_access<IteratorTy, void, true> +{ +}; +template <class IteratorTy> +class iterator_parent_access<IteratorTy, void, false> +{ +}; + +} // end namespace ilist_detail + +/// Iterator for intrusive lists based on ilist_node. +template <class OptionsT, bool IsReverse, bool IsConst> +class ilist_iterator : ilist_detail::SpecificNodeAccess<OptionsT>, + public ilist_detail::iterator_parent_access< + ilist_iterator<OptionsT, IsReverse, IsConst>, + typename OptionsT::parent_ty, IsConst> +{ + friend ilist_iterator<OptionsT, IsReverse, !IsConst>; + friend ilist_iterator<OptionsT, !IsReverse, IsConst>; + friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; + friend ilist_detail::iterator_parent_access< + ilist_iterator<OptionsT, IsReverse, IsConst>, + typename OptionsT::parent_ty, IsConst>; + + using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; + using Access = ilist_detail::SpecificNodeAccess<OptionsT>; + +public: + using value_type = typename Traits::value_type; + using pointer = typename Traits::pointer; + using reference = typename Traits::reference; + using difference_type = ptrdiff_t; + using iterator_category = std::bidirectional_iterator_tag; + using const_pointer = typename OptionsT::const_pointer; + using const_reference = typename OptionsT::const_reference; + +private: + using node_pointer = typename Traits::node_pointer; + using node_reference = typename Traits::node_reference; + + node_pointer NodePtr = nullptr; + +public: + /// Create from an ilist_node. + explicit ilist_iterator (node_reference N) : NodePtr (&N) + { + } + + explicit ilist_iterator (pointer NP) : NodePtr (Access::getNodePtr (NP)) + { + } + explicit ilist_iterator (reference NR) : NodePtr (Access::getNodePtr (&NR)) + { + } + ilist_iterator () = default; + + // This is templated so that we can allow constructing a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + ilist_iterator (const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS, + std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr) + : NodePtr (RHS.NodePtr) + { + } + + // This is templated so that we can allow assigning to a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator &> + operator= (const ilist_iterator<OptionsT, IsReverse, RHSIsConst> &RHS) + { + NodePtr = RHS.NodePtr; + return *this; + } + + /// Explicit conversion between forward/reverse iterators. + /// + /// Translate between forward and reverse iterators without changing range + /// boundaries. The resulting iterator will dereference (and have a handle) + /// to the previous node, which is somewhat unexpected; but converting the + /// two endpoints in a range will give the same range in reverse. + /// + /// This matches std::reverse_iterator conversions. + explicit ilist_iterator ( + const ilist_iterator<OptionsT, !IsReverse, IsConst> &RHS) + : ilist_iterator (++RHS.getReverse ()) + { + } + + /// Get a reverse iterator to the same node. + /// + /// Gives a reverse iterator that will dereference (and have a handle) to the + /// same node. Converting the endpoint iterators in a range will give a + /// different range; for range operations, use the explicit conversions. + ilist_iterator<OptionsT, !IsReverse, IsConst> + getReverse () const + { + if (NodePtr) + { + return ilist_iterator<OptionsT, !IsReverse, IsConst> (*NodePtr); + } + return ilist_iterator<OptionsT, !IsReverse, IsConst> (); + } + + /// Const-cast. + ilist_iterator<OptionsT, IsReverse, false> + getNonConst () const + { + if (NodePtr) + { + return ilist_iterator<OptionsT, IsReverse, false> ( + const_cast<typename ilist_iterator<OptionsT, IsReverse, + false>::node_reference> ( + *NodePtr)); + } + return ilist_iterator<OptionsT, IsReverse, false> (); + } + + // Accessors... + reference + operator* () const + { + assert (!NodePtr->isKnownSentinel ()); + return *Access::getValuePtr (NodePtr); + } + pointer + operator->() const + { + return &operator* (); + } + + // Comparison operators + friend bool + operator== (const ilist_iterator &LHS, const ilist_iterator &RHS) + { + return LHS.NodePtr == RHS.NodePtr; + } + friend bool + operator!= (const ilist_iterator &LHS, const ilist_iterator &RHS) + { + return LHS.NodePtr != RHS.NodePtr; + } + + // Increment and decrement operators... + ilist_iterator & + operator-- () + { + NodePtr = IsReverse ? NodePtr->getNext () : NodePtr->getPrev (); + return *this; + } + ilist_iterator & + operator++ () + { + NodePtr = IsReverse ? NodePtr->getPrev () : NodePtr->getNext (); + return *this; + } + ilist_iterator + operator-- (int) + { + ilist_iterator tmp = *this; + --*this; + return tmp; + } + ilist_iterator + operator++ (int) + { + ilist_iterator tmp = *this; + ++*this; + return tmp; + } + + bool + isValid () const + { + return NodePtr; + } + + /// Get the underlying ilist_node. + node_pointer + getNodePtr () const + { + return static_cast<node_pointer> (NodePtr); + } + + /// Check for end. Only valid if ilist_sentinel_tracking<true>. + bool + isEnd () const + { + return NodePtr ? NodePtr->isSentinel () : false; + } +}; + +/// Iterator for intrusive lists based on ilist_node. Much like ilist_iterator, +/// but with the addition of two bits recording whether this position (when in +/// a range) is half or fully open. +template <class OptionsT, bool IsReverse, bool IsConst> +class ilist_iterator_w_bits + : ilist_detail::SpecificNodeAccess<OptionsT>, + public ilist_detail::iterator_parent_access< + ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>, + typename OptionsT::parent_ty, IsConst> +{ + friend ilist_iterator_w_bits<OptionsT, IsReverse, !IsConst>; + friend ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst>; + friend ilist_iterator<OptionsT, !IsReverse, !IsConst>; + friend ilist_detail::iterator_parent_access< + ilist_iterator_w_bits<OptionsT, IsReverse, IsConst>, + typename OptionsT::parent_ty, IsConst>; + + using Traits = ilist_detail::IteratorTraits<OptionsT, IsConst>; + using Access = ilist_detail::SpecificNodeAccess<OptionsT>; + +public: + using value_type = typename Traits::value_type; + using pointer = typename Traits::pointer; + using reference = typename Traits::reference; + using difference_type = ptrdiff_t; + using iterator_category = std::bidirectional_iterator_tag; + using const_pointer = typename OptionsT::const_pointer; + using const_reference = typename OptionsT::const_reference; + +private: + using node_pointer = typename Traits::node_pointer; + using node_reference = typename Traits::node_reference; + + node_pointer NodePtr = nullptr; + + /// Is this position intended to contain any debug-info immediately before + /// the position? + mutable bool HeadInclusiveBit = false; + /// Is this position intended to contain any debug-info immediately after + /// the position? + mutable bool TailInclusiveBit = false; + +public: + /// Create from an ilist_node. + explicit ilist_iterator_w_bits (node_reference N) : NodePtr (&N) + { + } + + explicit ilist_iterator_w_bits (pointer NP) + : NodePtr (Access::getNodePtr (NP)) + { + } + explicit ilist_iterator_w_bits (reference NR) + : NodePtr (Access::getNodePtr (&NR)) + { + } + ilist_iterator_w_bits () = default; + + // This is templated so that we can allow constructing a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + ilist_iterator_w_bits ( + const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS, + std::enable_if_t<IsConst || !RHSIsConst, void *> = nullptr) + : NodePtr (RHS.NodePtr) + { + HeadInclusiveBit = RHS.HeadInclusiveBit; + TailInclusiveBit = RHS.TailInclusiveBit; + } + + // This is templated so that we can allow assigning to a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + std::enable_if_t<IsConst || !RHSIsConst, ilist_iterator_w_bits &> + operator= (const ilist_iterator_w_bits<OptionsT, IsReverse, RHSIsConst> &RHS) + { + NodePtr = RHS.NodePtr; + HeadInclusiveBit = RHS.HeadInclusiveBit; + TailInclusiveBit = RHS.TailInclusiveBit; + return *this; + } + + /// Explicit conversion between forward/reverse iterators. + /// + /// Translate between forward and reverse iterators without changing range + /// boundaries. The resulting iterator will dereference (and have a handle) + /// to the previous node, which is somewhat unexpected; but converting the + /// two endpoints in a range will give the same range in reverse. + /// + /// This matches std::reverse_iterator conversions. + explicit ilist_iterator_w_bits ( + const ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> &RHS) + : ilist_iterator_w_bits (++RHS.getReverse ()) + { + } + + /// Get a reverse iterator to the same node. + /// + /// Gives a reverse iterator that will dereference (and have a handle) to the + /// same node. Converting the endpoint iterators in a range will give a + /// different range; for range operations, use the explicit conversions. + ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> + getReverse () const + { + if (NodePtr) + { + return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> (*NodePtr); + } + return ilist_iterator_w_bits<OptionsT, !IsReverse, IsConst> (); + } + + /// Const-cast. + ilist_iterator_w_bits<OptionsT, IsReverse, false> + getNonConst () const + { + if (NodePtr) + { + auto New = ilist_iterator_w_bits<OptionsT, IsReverse, false> ( + const_cast<typename ilist_iterator_w_bits<OptionsT, IsReverse, + false>::node_reference> ( + *NodePtr)); + New.HeadInclusiveBit = HeadInclusiveBit; + New.TailInclusiveBit = TailInclusiveBit; + return New; + } + return ilist_iterator_w_bits<OptionsT, IsReverse, false> (); + } + + // Accessors... + reference + operator* () const + { + assert (!NodePtr->isKnownSentinel ()); + return *Access::getValuePtr (NodePtr); + } + pointer + operator->() const + { + return &operator* (); + } + + // Comparison operators + friend bool + operator== (const ilist_iterator_w_bits &LHS, + const ilist_iterator_w_bits &RHS) + { + return LHS.NodePtr == RHS.NodePtr; + } + friend bool + operator!= (const ilist_iterator_w_bits &LHS, + const ilist_iterator_w_bits &RHS) + { + return LHS.NodePtr != RHS.NodePtr; + } + + // Increment and decrement operators... + ilist_iterator_w_bits & + operator-- () + { + NodePtr = IsReverse ? NodePtr->getNext () : NodePtr->getPrev (); + HeadInclusiveBit = false; + TailInclusiveBit = false; + return *this; + } + ilist_iterator_w_bits & + operator++ () + { + NodePtr = IsReverse ? NodePtr->getPrev () : NodePtr->getNext (); + HeadInclusiveBit = false; + TailInclusiveBit = false; + return *this; + } + ilist_iterator_w_bits + operator-- (int) + { + ilist_iterator_w_bits tmp = *this; + --*this; + return tmp; + } + ilist_iterator_w_bits + operator++ (int) + { + ilist_iterator_w_bits tmp = *this; + ++*this; + return tmp; + } + + bool + isValid () const + { + return NodePtr; + } + + /// Get the underlying ilist_node. + node_pointer + getNodePtr () const + { + return static_cast<node_pointer> (NodePtr); + } + + /// Check for end. Only valid if ilist_sentinel_tracking<true>. + bool + isEnd () const + { + return NodePtr ? NodePtr->isSentinel () : false; + } + + bool + getHeadBit () const + { + return HeadInclusiveBit; + } + bool + getTailBit () const + { + return TailInclusiveBit; + } + void + setHeadBit (bool SetBit) const + { + HeadInclusiveBit = SetBit; + } + void + setTailBit (bool SetBit) const + { + TailInclusiveBit = SetBit; + } +}; + +template <typename From> struct simplify_type; + +/// Allow ilist_iterators to convert into pointers to a node automatically when +/// used by the dyn_cast, cast, isa mechanisms... +/// +/// FIXME: remove this, since there is no implicit conversion to NodeTy. +template <class OptionsT, bool IsConst> +struct simplify_type<ilist_iterator<OptionsT, false, IsConst>> +{ + using iterator = ilist_iterator<OptionsT, false, IsConst>; + using SimpleType = typename iterator::pointer; + + static SimpleType + getSimplifiedValue (const iterator &Node) + { + return &*Node; + } +}; +template <class OptionsT, bool IsConst> +struct simplify_type<const ilist_iterator<OptionsT, false, IsConst>> + : simplify_type<ilist_iterator<OptionsT, false, IsConst>> +{ +}; + +// ilist_iterator_w_bits should also be accessible via isa/dyn_cast. +template <class OptionsT, bool IsConst> +struct simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> +{ + using iterator = ilist_iterator_w_bits<OptionsT, false, IsConst>; + using SimpleType = typename iterator::pointer; + + static SimpleType + getSimplifiedValue (const iterator &Node) + { + return &*Node; + } +}; +template <class OptionsT, bool IsConst> +struct simplify_type<const ilist_iterator_w_bits<OptionsT, false, IsConst>> + : simplify_type<ilist_iterator_w_bits<OptionsT, false, IsConst>> +{ +}; + +} // end namespace libbase + +#endif // LIBBASE_ADT_ILIST_ITERATOR_H |