198 lines
7.2 KiB
C++
198 lines
7.2 KiB
C++
//===- llvm/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 LLVM_ADT_ILIST_ITERATOR_H
|
|
#define LLVM_ADT_ILIST_ITERATOR_H
|
|
|
|
#include "llvm/ADT/ilist_node.h"
|
|
#include <cassert>
|
|
#include <cstddef>
|
|
#include <iterator>
|
|
#include <type_traits>
|
|
|
|
namespace llvm {
|
|
|
|
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); }
|
|
};
|
|
|
|
} // 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> {
|
|
friend ilist_iterator<OptionsT, IsReverse, !IsConst>;
|
|
friend ilist_iterator<OptionsT, !IsReverse, IsConst>;
|
|
friend ilist_iterator<OptionsT, !IsReverse, !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;
|
|
}
|
|
|
|
/// 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; }
|
|
};
|
|
|
|
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>> {};
|
|
|
|
} // end namespace llvm
|
|
|
|
#endif // LLVM_ADT_ILIST_ITERATOR_H
|