diff options
Diffstat (limited to 'src/3rdparty/llvm/include/llvm/ADT')
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/PointerIntPair.h | 233 | ||||
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/ilist.h | 431 | ||||
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/ilist_base.h | 93 | ||||
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/ilist_iterator.h | 199 | ||||
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/ilist_node.h | 306 | ||||
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h | 53 | ||||
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/ilist_node_options.h | 133 | ||||
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/iterator.h | 339 | ||||
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/iterator_range.h | 68 | ||||
| -rw-r--r-- | src/3rdparty/llvm/include/llvm/ADT/simple_ilist.h | 315 |
10 files changed, 2170 insertions, 0 deletions
diff --git a/src/3rdparty/llvm/include/llvm/ADT/PointerIntPair.h b/src/3rdparty/llvm/include/llvm/ADT/PointerIntPair.h new file mode 100644 index 0000000000..884d05155b --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/PointerIntPair.h @@ -0,0 +1,233 @@ +//===- llvm/ADT/PointerIntPair.h - Pair for pointer and int -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines the PointerIntPair class. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_POINTERINTPAIR_H +#define LLVM_ADT_POINTERINTPAIR_H + +#include "llvm/Support/PointerLikeTypeTraits.h" +#include <cassert> +#include <cstdint> +#include <limits> + +namespace llvm { + +template <typename T> struct DenseMapInfo; +template <typename PointerT, unsigned IntBits, typename PtrTraits> +struct PointerIntPairInfo; + +/// PointerIntPair - This class implements a pair of a pointer and small +/// integer. It is designed to represent this in the space required by one +/// pointer by bitmangling the integer into the low part of the pointer. This +/// can only be done for small integers: typically up to 3 bits, but it depends +/// on the number of bits available according to PointerLikeTypeTraits for the +/// type. +/// +/// Note that PointerIntPair always puts the IntVal part in the highest bits +/// possible. For example, PointerIntPair<void*, 1, bool> will put the bit for +/// the bool into bit #2, not bit #0, which allows the low two bits to be used +/// for something else. For example, this allows: +/// PointerIntPair<PointerIntPair<void*, 1, bool>, 1, bool> +/// ... and the two bools will land in different bits. +template <typename PointerTy, unsigned IntBits, typename IntType = unsigned, + typename PtrTraits = PointerLikeTypeTraits<PointerTy>, + typename Info = PointerIntPairInfo<PointerTy, IntBits, PtrTraits>> +class PointerIntPair { + intptr_t Value = 0; + +public: + constexpr PointerIntPair() = default; + + PointerIntPair(PointerTy PtrVal, IntType IntVal) { + setPointerAndInt(PtrVal, IntVal); + } + + explicit PointerIntPair(PointerTy PtrVal) { initWithPointer(PtrVal); } + + PointerTy getPointer() const { return Info::getPointer(Value); } + + IntType getInt() const { return (IntType)Info::getInt(Value); } + + void setPointer(PointerTy PtrVal) { + Value = Info::updatePointer(Value, PtrVal); + } + + void setInt(IntType IntVal) { + Value = Info::updateInt(Value, static_cast<intptr_t>(IntVal)); + } + + void initWithPointer(PointerTy PtrVal) { + Value = Info::updatePointer(0, PtrVal); + } + + void setPointerAndInt(PointerTy PtrVal, IntType IntVal) { + Value = Info::updateInt(Info::updatePointer(0, PtrVal), + static_cast<intptr_t>(IntVal)); + } + + PointerTy const *getAddrOfPointer() const { + return const_cast<PointerIntPair *>(this)->getAddrOfPointer(); + } + + PointerTy *getAddrOfPointer() { + assert(Value == reinterpret_cast<intptr_t>(getPointer()) && + "Can only return the address if IntBits is cleared and " + "PtrTraits doesn't change the pointer"); + return reinterpret_cast<PointerTy *>(&Value); + } + + void *getOpaqueValue() const { return reinterpret_cast<void *>(Value); } + + void setFromOpaqueValue(void *Val) { + Value = reinterpret_cast<intptr_t>(Val); + } + + static PointerIntPair getFromOpaqueValue(void *V) { + PointerIntPair P; + P.setFromOpaqueValue(V); + return P; + } + + // Allow PointerIntPairs to be created from const void * if and only if the + // pointer type could be created from a const void *. + static PointerIntPair getFromOpaqueValue(const void *V) { + (void)PtrTraits::getFromVoidPointer(V); + return getFromOpaqueValue(const_cast<void *>(V)); + } + + bool operator==(const PointerIntPair &RHS) const { + return Value == RHS.Value; + } + + bool operator!=(const PointerIntPair &RHS) const { + return Value != RHS.Value; + } + + bool operator<(const PointerIntPair &RHS) const { return Value < RHS.Value; } + bool operator>(const PointerIntPair &RHS) const { return Value > RHS.Value; } + + bool operator<=(const PointerIntPair &RHS) const { + return Value <= RHS.Value; + } + + bool operator>=(const PointerIntPair &RHS) const { + return Value >= RHS.Value; + } +}; + +template <typename PointerT, unsigned IntBits, typename PtrTraits> +struct PointerIntPairInfo { + static_assert(PtrTraits::NumLowBitsAvailable < + std::numeric_limits<uintptr_t>::digits, + "cannot use a pointer type that has all bits free"); + static_assert(IntBits <= PtrTraits::NumLowBitsAvailable, + "PointerIntPair with integer size too large for pointer"); + enum : uintptr_t { + /// PointerBitMask - The bits that come from the pointer. + PointerBitMask = + ~(uintptr_t)(((intptr_t)1 << PtrTraits::NumLowBitsAvailable) - 1), + + /// IntShift - The number of low bits that we reserve for other uses, and + /// keep zero. + IntShift = (uintptr_t)PtrTraits::NumLowBitsAvailable - IntBits, + + /// IntMask - This is the unshifted mask for valid bits of the int type. + IntMask = (uintptr_t)(((intptr_t)1 << IntBits) - 1), + + // ShiftedIntMask - This is the bits for the integer shifted in place. + ShiftedIntMask = (uintptr_t)(IntMask << IntShift) + }; + + static PointerT getPointer(intptr_t Value) { + return PtrTraits::getFromVoidPointer( + reinterpret_cast<void *>(Value & PointerBitMask)); + } + + static intptr_t getInt(intptr_t Value) { + return (Value >> IntShift) & IntMask; + } + + static intptr_t updatePointer(intptr_t OrigValue, PointerT Ptr) { + intptr_t PtrWord = + reinterpret_cast<intptr_t>(PtrTraits::getAsVoidPointer(Ptr)); + assert((PtrWord & ~PointerBitMask) == 0 && + "Pointer is not sufficiently aligned"); + // Preserve all low bits, just update the pointer. + return PtrWord | (OrigValue & ~PointerBitMask); + } + + static intptr_t updateInt(intptr_t OrigValue, intptr_t Int) { + intptr_t IntWord = static_cast<intptr_t>(Int); + assert((IntWord & ~IntMask) == 0 && "Integer too large for field"); + + // Preserve all bits other than the ones we are updating. + return (OrigValue & ~ShiftedIntMask) | IntWord << IntShift; + } +}; + +template <typename T> struct isPodLike; +template <typename PointerTy, unsigned IntBits, typename IntType> +struct isPodLike<PointerIntPair<PointerTy, IntBits, IntType>> { + static const bool value = true; +}; + +// Provide specialization of DenseMapInfo for PointerIntPair. +template <typename PointerTy, unsigned IntBits, typename IntType> +struct DenseMapInfo<PointerIntPair<PointerTy, IntBits, IntType>> { + using Ty = PointerIntPair<PointerTy, IntBits, IntType>; + + static Ty getEmptyKey() { + uintptr_t Val = static_cast<uintptr_t>(-1); + Val <<= PointerLikeTypeTraits<Ty>::NumLowBitsAvailable; + return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val)); + } + + static Ty getTombstoneKey() { + uintptr_t Val = static_cast<uintptr_t>(-2); + Val <<= PointerLikeTypeTraits<PointerTy>::NumLowBitsAvailable; + return Ty::getFromOpaqueValue(reinterpret_cast<void *>(Val)); + } + + static unsigned getHashValue(Ty V) { + uintptr_t IV = reinterpret_cast<uintptr_t>(V.getOpaqueValue()); + return unsigned(IV) ^ unsigned(IV >> 9); + } + + static bool isEqual(const Ty &LHS, const Ty &RHS) { return LHS == RHS; } +}; + +// Teach SmallPtrSet that PointerIntPair is "basically a pointer". +template <typename PointerTy, unsigned IntBits, typename IntType, + typename PtrTraits> +struct PointerLikeTypeTraits< + PointerIntPair<PointerTy, IntBits, IntType, PtrTraits>> { + static inline void * + getAsVoidPointer(const PointerIntPair<PointerTy, IntBits, IntType> &P) { + return P.getOpaqueValue(); + } + + static inline PointerIntPair<PointerTy, IntBits, IntType> + getFromVoidPointer(void *P) { + return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); + } + + static inline PointerIntPair<PointerTy, IntBits, IntType> + getFromVoidPointer(const void *P) { + return PointerIntPair<PointerTy, IntBits, IntType>::getFromOpaqueValue(P); + } + + enum { NumLowBitsAvailable = PtrTraits::NumLowBitsAvailable - IntBits }; +}; + +} // end namespace llvm + +#endif // LLVM_ADT_POINTERINTPAIR_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist.h b/src/3rdparty/llvm/include/llvm/ADT/ilist.h new file mode 100644 index 0000000000..7e346e1260 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist.h @@ -0,0 +1,431 @@ +//==-- llvm/ADT/ilist.h - Intrusive Linked List Template ---------*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines classes to implement an intrusive doubly linked list class +// (i.e. each node of the list must contain a next and previous field for the +// list. +// +// The ilist class itself should be a plug in replacement for list. This list +// replacement does not provide a constant time size() method, so be careful to +// use empty() when you really want to know if it's empty. +// +// The ilist class is implemented as a circular list. The list itself contains +// a sentinel node, whose Next points at begin() and whose Prev points at +// rbegin(). The sentinel node itself serves as end() and rend(). +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_H +#define LLVM_ADT_ILIST_H + +#include "llvm/ADT/simple_ilist.h" +#include <cassert> +#include <cstddef> +#include <iterator> + +namespace llvm { + +/// Use delete by default for iplist and ilist. +/// +/// Specialize this to get different behaviour for ownership-related API. (If +/// you really want ownership semantics, consider using std::list or building +/// something like \a BumpPtrList.) +/// +/// \see ilist_noalloc_traits +template <typename NodeTy> struct ilist_alloc_traits { + static void deleteNode(NodeTy *V) { delete V; } +}; + +/// Custom traits to do nothing on deletion. +/// +/// Specialize ilist_alloc_traits to inherit from this to disable the +/// non-intrusive deletion in iplist (which implies ownership). +/// +/// If you want purely intrusive semantics with no callbacks, consider using \a +/// simple_ilist instead. +/// +/// \code +/// template <> +/// struct ilist_alloc_traits<MyType> : ilist_noalloc_traits<MyType> {}; +/// \endcode +template <typename NodeTy> struct ilist_noalloc_traits { + static void deleteNode(NodeTy *) {} +}; + +/// Callbacks do nothing by default in iplist and ilist. +/// +/// Specialize this for to use callbacks for when nodes change their list +/// membership. +template <typename NodeTy> struct ilist_callback_traits { + void addNodeToList(NodeTy *) {} + void removeNodeFromList(NodeTy *) {} + + /// Callback before transferring nodes to this list. + /// + /// \pre \c this!=&OldList + template <class Iterator> + void transferNodesFromList(ilist_callback_traits &OldList, Iterator /*first*/, + Iterator /*last*/) { + (void)OldList; + } +}; + +/// A fragment for template traits for intrusive list that provides default +/// node related operations. +/// +/// TODO: Remove this layer of indirection. It's not necessary. +template <typename NodeTy> +struct ilist_node_traits : ilist_alloc_traits<NodeTy>, + ilist_callback_traits<NodeTy> {}; + +/// Default template traits for intrusive list. +/// +/// By inheriting from this, you can easily use default implementations for all +/// common operations. +/// +/// TODO: Remove this customization point. Specializing ilist_traits is +/// already fully general. +template <typename NodeTy> +struct ilist_default_traits : public ilist_node_traits<NodeTy> {}; + +/// Template traits for intrusive list. +/// +/// Customize callbacks and allocation semantics. +template <typename NodeTy> +struct ilist_traits : public ilist_default_traits<NodeTy> {}; + +/// Const traits should never be instantiated. +template <typename Ty> struct ilist_traits<const Ty> {}; + +namespace ilist_detail { + +template <class T> T &make(); + +/// Type trait to check for a traits class that has a getNext member (as a +/// canary for any of the ilist_nextprev_traits API). +template <class TraitsT, class NodeT> struct HasGetNext { + typedef char Yes[1]; + typedef char No[2]; + template <size_t N> struct SFINAE {}; + + template <class U> + static Yes &test(U *I, decltype(I->getNext(&make<NodeT>())) * = 0); + template <class> static No &test(...); + +public: + static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); +}; + +/// Type trait to check for a traits class that has a createSentinel member (as +/// a canary for any of the ilist_sentinel_traits API). +template <class TraitsT> struct HasCreateSentinel { + typedef char Yes[1]; + typedef char No[2]; + + template <class U> + static Yes &test(U *I, decltype(I->createSentinel()) * = 0); + template <class> static No &test(...); + +public: + static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); +}; + +/// Type trait to check for a traits class that has a createNode member. +/// Allocation should be managed in a wrapper class, instead of in +/// ilist_traits. +template <class TraitsT, class NodeT> struct HasCreateNode { + typedef char Yes[1]; + typedef char No[2]; + template <size_t N> struct SFINAE {}; + + template <class U> + static Yes &test(U *I, decltype(I->createNode(make<NodeT>())) * = 0); + template <class> static No &test(...); + +public: + static const bool value = sizeof(test<TraitsT>(nullptr)) == sizeof(Yes); +}; + +template <class TraitsT, class NodeT> struct HasObsoleteCustomization { + static const bool value = HasGetNext<TraitsT, NodeT>::value || + HasCreateSentinel<TraitsT>::value || + HasCreateNode<TraitsT, NodeT>::value; +}; + +} // end namespace ilist_detail + +//===----------------------------------------------------------------------===// +// +/// A wrapper around an intrusive list with callbacks and non-intrusive +/// ownership. +/// +/// This wraps a purely intrusive list (like simple_ilist) with a configurable +/// traits class. The traits can implement callbacks and customize the +/// ownership semantics. +/// +/// This is a subset of ilist functionality that can safely be used on nodes of +/// polymorphic types, i.e. a heterogeneous list with a common base class that +/// holds the next/prev pointers. The only state of the list itself is an +/// ilist_sentinel, which holds pointers to the first and last nodes in the +/// list. +template <class IntrusiveListT, class TraitsT> +class iplist_impl : public TraitsT, IntrusiveListT { + typedef IntrusiveListT base_list_type; + +public: + typedef typename base_list_type::pointer pointer; + typedef typename base_list_type::const_pointer const_pointer; + typedef typename base_list_type::reference reference; + typedef typename base_list_type::const_reference const_reference; + typedef typename base_list_type::value_type value_type; + typedef typename base_list_type::size_type size_type; + typedef typename base_list_type::difference_type difference_type; + typedef typename base_list_type::iterator iterator; + typedef typename base_list_type::const_iterator const_iterator; + typedef typename base_list_type::reverse_iterator reverse_iterator; + typedef + typename base_list_type::const_reverse_iterator const_reverse_iterator; + +private: + // TODO: Drop this assertion and the transitive type traits anytime after + // v4.0 is branched (i.e,. keep them for one release to help out-of-tree code + // update). + static_assert( + !ilist_detail::HasObsoleteCustomization<TraitsT, value_type>::value, + "ilist customization points have changed!"); + + static bool op_less(const_reference L, const_reference R) { return L < R; } + static bool op_equal(const_reference L, const_reference R) { return L == R; } + +public: + iplist_impl() = default; + + iplist_impl(const iplist_impl &) = delete; + iplist_impl &operator=(const iplist_impl &) = delete; + + iplist_impl(iplist_impl &&X) + : TraitsT(std::move(X)), IntrusiveListT(std::move(X)) {} + iplist_impl &operator=(iplist_impl &&X) { + *static_cast<TraitsT *>(this) = std::move(X); + *static_cast<IntrusiveListT *>(this) = std::move(X); + return *this; + } + + ~iplist_impl() { clear(); } + + // Miscellaneous inspection routines. + size_type max_size() const { return size_type(-1); } + + using base_list_type::begin; + using base_list_type::end; + using base_list_type::rbegin; + using base_list_type::rend; + using base_list_type::empty; + using base_list_type::front; + using base_list_type::back; + + void swap(iplist_impl &RHS) { + assert(0 && "Swap does not use list traits callback correctly yet!"); + base_list_type::swap(RHS); + } + + iterator insert(iterator where, pointer New) { + this->addNodeToList(New); // Notify traits that we added a node... + return base_list_type::insert(where, *New); + } + + iterator insert(iterator where, const_reference New) { + return this->insert(where, new value_type(New)); + } + + iterator insertAfter(iterator where, pointer New) { + if (empty()) + return insert(begin(), New); + else + return insert(++where, New); + } + + /// Clone another list. + template <class Cloner> void cloneFrom(const iplist_impl &L2, Cloner clone) { + clear(); + for (const_reference V : L2) + push_back(clone(V)); + } + + pointer remove(iterator &IT) { + pointer Node = &*IT++; + this->removeNodeFromList(Node); // Notify traits that we removed a node... + base_list_type::remove(*Node); + return Node; + } + + pointer remove(const iterator &IT) { + iterator MutIt = IT; + return remove(MutIt); + } + + pointer remove(pointer IT) { return remove(iterator(IT)); } + pointer remove(reference IT) { return remove(iterator(IT)); } + + // erase - remove a node from the controlled sequence... and delete it. + iterator erase(iterator where) { + this->deleteNode(remove(where)); + return where; + } + + iterator erase(pointer IT) { return erase(iterator(IT)); } + iterator erase(reference IT) { return erase(iterator(IT)); } + + /// Remove all nodes from the list like clear(), but do not call + /// removeNodeFromList() or deleteNode(). + /// + /// This should only be used immediately before freeing nodes in bulk to + /// avoid traversing the list and bringing all the nodes into cache. + void clearAndLeakNodesUnsafely() { base_list_type::clear(); } + +private: + // transfer - The heart of the splice function. Move linked list nodes from + // [first, last) into position. + // + void transfer(iterator position, iplist_impl &L2, iterator first, iterator last) { + if (position == last) + return; + + if (this != &L2) // Notify traits we moved the nodes... + this->transferNodesFromList(L2, first, last); + + base_list_type::splice(position, L2, first, last); + } + +public: + //===----------------------------------------------------------------------=== + // Functionality derived from other functions defined above... + // + + using base_list_type::size; + + iterator erase(iterator first, iterator last) { + while (first != last) + first = erase(first); + return last; + } + + void clear() { erase(begin(), end()); } + + // Front and back inserters... + void push_front(pointer val) { insert(begin(), val); } + void push_back(pointer val) { insert(end(), val); } + void pop_front() { + assert(!empty() && "pop_front() on empty list!"); + erase(begin()); + } + void pop_back() { + assert(!empty() && "pop_back() on empty list!"); + iterator t = end(); erase(--t); + } + + // Special forms of insert... + template<class InIt> void insert(iterator where, InIt first, InIt last) { + for (; first != last; ++first) insert(where, *first); + } + + // Splice members - defined in terms of transfer... + void splice(iterator where, iplist_impl &L2) { + if (!L2.empty()) + transfer(where, L2, L2.begin(), L2.end()); + } + void splice(iterator where, iplist_impl &L2, iterator first) { + iterator last = first; ++last; + if (where == first || where == last) return; // No change + transfer(where, L2, first, last); + } + void splice(iterator where, iplist_impl &L2, iterator first, iterator last) { + if (first != last) transfer(where, L2, first, last); + } + void splice(iterator where, iplist_impl &L2, reference N) { + splice(where, L2, iterator(N)); + } + void splice(iterator where, iplist_impl &L2, pointer N) { + splice(where, L2, iterator(N)); + } + + template <class Compare> + void merge(iplist_impl &Right, Compare comp) { + if (this == &Right) + return; + this->transferNodesFromList(Right, Right.begin(), Right.end()); + base_list_type::merge(Right, comp); + } + void merge(iplist_impl &Right) { return merge(Right, op_less); } + + using base_list_type::sort; + + /// \brief Get the previous node, or \c nullptr for the list head. + pointer getPrevNode(reference N) const { + auto I = N.getIterator(); + if (I == begin()) + return nullptr; + return &*std::prev(I); + } + /// \brief Get the previous node, or \c nullptr for the list head. + const_pointer getPrevNode(const_reference N) const { + return getPrevNode(const_cast<reference >(N)); + } + + /// \brief Get the next node, or \c nullptr for the list tail. + pointer getNextNode(reference N) const { + auto Next = std::next(N.getIterator()); + if (Next == end()) + return nullptr; + return &*Next; + } + /// \brief Get the next node, or \c nullptr for the list tail. + const_pointer getNextNode(const_reference N) const { + return getNextNode(const_cast<reference >(N)); + } +}; + +/// An intrusive list with ownership and callbacks specified/controlled by +/// ilist_traits, only with API safe for polymorphic types. +/// +/// The \p Options parameters are the same as those for \a simple_ilist. See +/// there for a description of what's available. +template <class T, class... Options> +class iplist + : public iplist_impl<simple_ilist<T, Options...>, ilist_traits<T>> { + using iplist_impl_type = typename iplist::iplist_impl; + +public: + iplist() = default; + + iplist(const iplist &X) = delete; + iplist &operator=(const iplist &X) = delete; + + iplist(iplist &&X) : iplist_impl_type(std::move(X)) {} + iplist &operator=(iplist &&X) { + *static_cast<iplist_impl_type *>(this) = std::move(X); + return *this; + } +}; + +template <class T, class... Options> using ilist = iplist<T, Options...>; + +} // end namespace llvm + +namespace std { + + // Ensure that swap uses the fast list swap... + template<class Ty> + void swap(llvm::iplist<Ty> &Left, llvm::iplist<Ty> &Right) { + Left.swap(Right); + } + +} // end namespace std + +#endif // LLVM_ADT_ILIST_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_base.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_base.h new file mode 100644 index 0000000000..3d818a48d4 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_base.h @@ -0,0 +1,93 @@ +//===- llvm/ADT/ilist_base.h - Intrusive List Base --------------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_BASE_H +#define LLVM_ADT_ILIST_BASE_H + +#include "llvm/ADT/ilist_node_base.h" +#include <cassert> + +namespace llvm { + +/// Implementations of list algorithms using ilist_node_base. +template <bool EnableSentinelTracking> class ilist_base { +public: + using node_base_type = ilist_node_base<EnableSentinelTracking>; + + static void insertBeforeImpl(node_base_type &Next, node_base_type &N) { + node_base_type &Prev = *Next.getPrev(); + N.setNext(&Next); + N.setPrev(&Prev); + Prev.setNext(&N); + Next.setPrev(&N); + } + + static void removeImpl(node_base_type &N) { + node_base_type *Prev = N.getPrev(); + node_base_type *Next = N.getNext(); + Next->setPrev(Prev); + Prev->setNext(Next); + + // Not strictly necessary, but helps catch a class of bugs. + N.setPrev(nullptr); + N.setNext(nullptr); + } + + static void removeRangeImpl(node_base_type &First, node_base_type &Last) { + node_base_type *Prev = First.getPrev(); + node_base_type *Final = Last.getPrev(); + Last.setPrev(Prev); + Prev->setNext(&Last); + + // Not strictly necessary, but helps catch a class of bugs. + First.setPrev(nullptr); + Final->setNext(nullptr); + } + + static void transferBeforeImpl(node_base_type &Next, node_base_type &First, + node_base_type &Last) { + if (&Next == &Last || &First == &Last) + return; + + // Position cannot be contained in the range to be transferred. + assert(&Next != &First && + // Check for the most common mistake. + "Insertion point can't be one of the transferred nodes"); + + node_base_type &Final = *Last.getPrev(); + + // Detach from old list/position. + First.getPrev()->setNext(&Last); + Last.setPrev(First.getPrev()); + + // Splice [First, Final] into its new list/position. + node_base_type &Prev = *Next.getPrev(); + Final.setNext(&Next); + First.setPrev(&Prev); + Prev.setNext(&First); + Next.setPrev(&Final); + } + + template <class T> static void insertBefore(T &Next, T &N) { + insertBeforeImpl(Next, N); + } + + template <class T> static void remove(T &N) { removeImpl(N); } + template <class T> static void removeRange(T &First, T &Last) { + removeRangeImpl(First, Last); + } + + template <class T> static void transferBefore(T &Next, T &First, T &Last) { + transferBeforeImpl(Next, First, Last); + } +}; + +} // end namespace llvm + +#endif // LLVM_ADT_ILIST_BASE_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_iterator.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_iterator.h new file mode 100644 index 0000000000..671e644e01 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_iterator.h @@ -0,0 +1,199 @@ +//===- llvm/ADT/ilist_iterator.h - Intrusive List Iterator ------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#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, + typename std::enable_if<IsConst || !RHSIsConst, void *>::type = nullptr) + : NodePtr(RHS.NodePtr) {} + + // This is templated so that we can allow assigning to a const iterator from + // a nonconst iterator... + template <bool RHSIsConst> + typename std::enable_if<IsConst || !RHSIsConst, ilist_iterator &>::type + 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 diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_node.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_node.h new file mode 100644 index 0000000000..3362611697 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_node.h @@ -0,0 +1,306 @@ +//===- llvm/ADT/ilist_node.h - Intrusive Linked List Helper -----*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// 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 + +#include "llvm/ADT/ilist_node_base.h" +#include "llvm/ADT/ilist_node_options.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: + using self_iterator = ilist_iterator<OptionsT, false, false>; + using const_self_iterator = ilist_iterator<OptionsT, false, true>; + using reverse_self_iterator = ilist_iterator<OptionsT, true, false>; + using const_reverse_self_iterator = ilist_iterator<OptionsT, true, true>; + + 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: + self_iterator getIterator() { return self_iterator(*this); } + const_self_iterator getIterator() const { return const_self_iterator(*this); } + + reverse_self_iterator getReverseIterator() { + return reverse_self_iterator(*this); + } + + const_reverse_self_iterator getReverseIterator() const { + return const_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()"); + return node_base_type::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>; + + static node_type *getNodePtr(pointer N) { + return NodeAccess::getNodePtr<OptionsT>(N); + } + + static const node_type *getNodePtr(const_pointer N) { + return NodeAccess::getNodePtr<OptionsT>(N); + } + + static pointer getValuePtr(node_type *N) { + return NodeAccess::getValuePtr<OptionsT>(N); + } + + static const_pointer getValuePtr(const node_type *N) { + return NodeAccess::getValuePtr<OptionsT>(N); + } +}; + +} // end namespace ilist_detail + +template <class OptionsT> +class ilist_sentinel : public ilist_node_impl<OptionsT> { +public: + ilist_sentinel() { + 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: + ilist_node_with_parent() = default; + +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 + /// @{ + /// \brief 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)); + } + + /// \brief Get the previous node, or \c nullptr for the list head. + const NodeTy *getPrevNode() const { + return const_cast<ilist_node_with_parent *>(this)->getPrevNode(); + } + + /// \brief 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)); + } + + /// \brief 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 diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h new file mode 100644 index 0000000000..e5062ac4ea --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_base.h @@ -0,0 +1,53 @@ +//===- llvm/ADT/ilist_node_base.h - Intrusive List Node Base -----*- C++ -*-==// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_NODE_BASE_H +#define LLVM_ADT_ILIST_NODE_BASE_H + +#include "llvm/ADT/PointerIntPair.h" + +namespace llvm { + +/// Base class for ilist nodes. +/// +/// Optionally tracks whether this node is the sentinel. +template <bool EnableSentinelTracking> class ilist_node_base; + +template <> class ilist_node_base<false> { + ilist_node_base *Prev = nullptr; + ilist_node_base *Next = nullptr; + +public: + void setPrev(ilist_node_base *Prev) { this->Prev = Prev; } + void setNext(ilist_node_base *Next) { this->Next = Next; } + ilist_node_base *getPrev() const { return Prev; } + ilist_node_base *getNext() const { return Next; } + + bool isKnownSentinel() const { return false; } + void initializeSentinel() {} +}; + +template <> class ilist_node_base<true> { + PointerIntPair<ilist_node_base *, 1> PrevAndSentinel; + ilist_node_base *Next = nullptr; + +public: + void setPrev(ilist_node_base *Prev) { PrevAndSentinel.setPointer(Prev); } + void setNext(ilist_node_base *Next) { this->Next = Next; } + ilist_node_base *getPrev() const { return PrevAndSentinel.getPointer(); } + ilist_node_base *getNext() const { return Next; } + + bool isSentinel() const { return PrevAndSentinel.getInt(); } + bool isKnownSentinel() const { return isSentinel(); } + void initializeSentinel() { PrevAndSentinel.setInt(true); } +}; + +} // end namespace llvm + +#endif // LLVM_ADT_ILIST_NODE_BASE_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/ilist_node_options.h b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_options.h new file mode 100644 index 0000000000..a09fdda31c --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/ilist_node_options.h @@ -0,0 +1,133 @@ +//===- llvm/ADT/ilist_node_options.h - ilist_node Options -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ILIST_NODE_OPTIONS_H +#define LLVM_ADT_ILIST_NODE_OPTIONS_H + +//#include "llvm/Config/abi-breaking.h" +//#include "llvm/Config/llvm-config.h" + +#include <type_traits> + +namespace llvm { + +template <bool EnableSentinelTracking> class ilist_node_base; +template <bool EnableSentinelTracking> class ilist_base; + +/// Option to choose whether to track sentinels. +/// +/// This option affects the ABI for the nodes. When not specified explicitly, +/// the ABI depends on LLVM_ENABLE_ABI_BREAKING_CHECKS. Specify explicitly to +/// enable \a ilist_node::isSentinel(). +template <bool EnableSentinelTracking> struct ilist_sentinel_tracking {}; + +/// Option to specify a tag for the node type. +/// +/// This option allows a single value type to be inserted in multiple lists +/// simultaneously. See \a ilist_node for usage examples. +template <class Tag> struct ilist_tag {}; + +namespace ilist_detail { + +/// Helper trait for recording whether an option is specified explicitly. +template <bool IsExplicit> struct explicitness { + static const bool is_explicit = IsExplicit; +}; +typedef explicitness<true> is_explicit; +typedef explicitness<false> is_implicit; + +/// Check whether an option is valid. +/// +/// The steps for adding and enabling a new ilist option include: +/// \li define the option, ilist_foo<Bar>, above; +/// \li add new parameters for Bar to \a ilist_detail::node_options; +/// \li add an extraction meta-function, ilist_detail::extract_foo; +/// \li call extract_foo from \a ilist_detail::compute_node_options and pass it +/// into \a ilist_detail::node_options; and +/// \li specialize \c is_valid_option<ilist_foo<Bar>> to inherit from \c +/// std::true_type to get static assertions passing in \a simple_ilist and \a +/// ilist_node. +template <class Option> struct is_valid_option : std::false_type {}; + +/// Extract sentinel tracking option. +/// +/// Look through \p Options for the \a ilist_sentinel_tracking option, with the +/// default depending on LLVM_ENABLE_ABI_BREAKING_CHECKS. +template <class... Options> struct extract_sentinel_tracking; +template <bool EnableSentinelTracking, class... Options> +struct extract_sentinel_tracking< + ilist_sentinel_tracking<EnableSentinelTracking>, Options...> + : std::integral_constant<bool, EnableSentinelTracking>, is_explicit {}; +template <class Option1, class... Options> +struct extract_sentinel_tracking<Option1, Options...> + : extract_sentinel_tracking<Options...> {}; +#if LLVM_ENABLE_ABI_BREAKING_CHECKS +template <> struct extract_sentinel_tracking<> : std::true_type, is_implicit {}; +#else +template <> +struct extract_sentinel_tracking<> : std::false_type, is_implicit {}; +#endif +template <bool EnableSentinelTracking> +struct is_valid_option<ilist_sentinel_tracking<EnableSentinelTracking>> + : std::true_type {}; + +/// Extract custom tag option. +/// +/// Look through \p Options for the \a ilist_tag option, pulling out the +/// custom tag type, using void as a default. +template <class... Options> struct extract_tag; +template <class Tag, class... Options> +struct extract_tag<ilist_tag<Tag>, Options...> { + typedef Tag type; +}; +template <class Option1, class... Options> +struct extract_tag<Option1, Options...> : extract_tag<Options...> {}; +template <> struct extract_tag<> { typedef void type; }; +template <class Tag> struct is_valid_option<ilist_tag<Tag>> : std::true_type {}; + +/// Check whether options are valid. +/// +/// The conjunction of \a is_valid_option on each individual option. +template <class... Options> struct check_options; +template <> struct check_options<> : std::true_type {}; +template <class Option1, class... Options> +struct check_options<Option1, Options...> + : std::integral_constant<bool, is_valid_option<Option1>::value && + check_options<Options...>::value> {}; + +/// Traits for options for \a ilist_node. +/// +/// This is usually computed via \a compute_node_options. +template <class T, bool EnableSentinelTracking, bool IsSentinelTrackingExplicit, + class TagT> +struct node_options { + typedef T value_type; + typedef T *pointer; + typedef T &reference; + typedef const T *const_pointer; + typedef const T &const_reference; + + static const bool enable_sentinel_tracking = EnableSentinelTracking; + static const bool is_sentinel_tracking_explicit = IsSentinelTrackingExplicit; + typedef TagT tag; + typedef ilist_node_base<enable_sentinel_tracking> node_base_type; + typedef ilist_base<enable_sentinel_tracking> list_base_type; +}; + +template <class T, class... Options> struct compute_node_options { + typedef node_options<T, extract_sentinel_tracking<Options...>::value, + extract_sentinel_tracking<Options...>::is_explicit, + typename extract_tag<Options...>::type> + type; +}; + +} // end namespace ilist_detail +} // end namespace llvm + +#endif // LLVM_ADT_ILIST_NODE_OPTIONS_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/iterator.h b/src/3rdparty/llvm/include/llvm/ADT/iterator.h new file mode 100644 index 0000000000..711f8f2216 --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/iterator.h @@ -0,0 +1,339 @@ +//===- iterator.h - Utilities for using and defining iterators --*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ITERATOR_H +#define LLVM_ADT_ITERATOR_H + +#include "llvm/ADT/iterator_range.h" +#include <algorithm> +#include <cstddef> +#include <iterator> +#include <type_traits> +#include <utility> + +namespace llvm { + +/// \brief CRTP base class which implements the entire standard iterator facade +/// in terms of a minimal subset of the interface. +/// +/// Use this when it is reasonable to implement most of the iterator +/// functionality in terms of a core subset. If you need special behavior or +/// there are performance implications for this, you may want to override the +/// relevant members instead. +/// +/// Note, one abstraction that this does *not* provide is implementing +/// subtraction in terms of addition by negating the difference. Negation isn't +/// always information preserving, and I can see very reasonable iterator +/// designs where this doesn't work well. It doesn't really force much added +/// boilerplate anyways. +/// +/// Another abstraction that this doesn't provide is implementing increment in +/// terms of addition of one. These aren't equivalent for all iterator +/// categories, and respecting that adds a lot of complexity for little gain. +/// +/// Classes wishing to use `iterator_facade_base` should implement the following +/// methods: +/// +/// Forward Iterators: +/// (All of the following methods) +/// - DerivedT &operator=(const DerivedT &R); +/// - bool operator==(const DerivedT &R) const; +/// - const T &operator*() const; +/// - T &operator*(); +/// - DerivedT &operator++(); +/// +/// Bidirectional Iterators: +/// (All methods of forward iterators, plus the following) +/// - DerivedT &operator--(); +/// +/// Random-access Iterators: +/// (All methods of bidirectional iterators excluding the following) +/// - DerivedT &operator++(); +/// - DerivedT &operator--(); +/// (and plus the following) +/// - bool operator<(const DerivedT &RHS) const; +/// - DifferenceTypeT operator-(const DerivedT &R) const; +/// - DerivedT &operator+=(DifferenceTypeT N); +/// - DerivedT &operator-=(DifferenceTypeT N); +/// +template <typename DerivedT, typename IteratorCategoryT, typename T, + typename DifferenceTypeT = std::ptrdiff_t, typename PointerT = T *, + typename ReferenceT = T &> +class iterator_facade_base + : public std::iterator<IteratorCategoryT, T, DifferenceTypeT, PointerT, + ReferenceT> { +protected: + enum { + IsRandomAccess = std::is_base_of<std::random_access_iterator_tag, + IteratorCategoryT>::value, + IsBidirectional = std::is_base_of<std::bidirectional_iterator_tag, + IteratorCategoryT>::value, + }; + + /// A proxy object for computing a reference via indirecting a copy of an + /// iterator. This is used in APIs which need to produce a reference via + /// indirection but for which the iterator object might be a temporary. The + /// proxy preserves the iterator internally and exposes the indirected + /// reference via a conversion operator. + class ReferenceProxy { + friend iterator_facade_base; + + DerivedT I; + + ReferenceProxy(DerivedT I) : I(std::move(I)) {} + + public: + operator ReferenceT() const { return *I; } + }; + +public: + DerivedT operator+(DifferenceTypeT n) const { + static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, + "Must pass the derived type to this template!"); + static_assert( + IsRandomAccess, + "The '+' operator is only defined for random access iterators."); + DerivedT tmp = *static_cast<const DerivedT *>(this); + tmp += n; + return tmp; + } + friend DerivedT operator+(DifferenceTypeT n, const DerivedT &i) { + static_assert( + IsRandomAccess, + "The '+' operator is only defined for random access iterators."); + return i + n; + } + DerivedT operator-(DifferenceTypeT n) const { + static_assert( + IsRandomAccess, + "The '-' operator is only defined for random access iterators."); + DerivedT tmp = *static_cast<const DerivedT *>(this); + tmp -= n; + return tmp; + } + + DerivedT &operator++() { + static_assert(std::is_base_of<iterator_facade_base, DerivedT>::value, + "Must pass the derived type to this template!"); + return static_cast<DerivedT *>(this)->operator+=(1); + } + DerivedT operator++(int) { + DerivedT tmp = *static_cast<DerivedT *>(this); + ++*static_cast<DerivedT *>(this); + return tmp; + } + DerivedT &operator--() { + static_assert( + IsBidirectional, + "The decrement operator is only defined for bidirectional iterators."); + return static_cast<DerivedT *>(this)->operator-=(1); + } + DerivedT operator--(int) { + static_assert( + IsBidirectional, + "The decrement operator is only defined for bidirectional iterators."); + DerivedT tmp = *static_cast<DerivedT *>(this); + --*static_cast<DerivedT *>(this); + return tmp; + } + + bool operator!=(const DerivedT &RHS) const { + return !static_cast<const DerivedT *>(this)->operator==(RHS); + } + + bool operator>(const DerivedT &RHS) const { + static_assert( + IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return !static_cast<const DerivedT *>(this)->operator<(RHS) && + !static_cast<const DerivedT *>(this)->operator==(RHS); + } + bool operator<=(const DerivedT &RHS) const { + static_assert( + IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return !static_cast<const DerivedT *>(this)->operator>(RHS); + } + bool operator>=(const DerivedT &RHS) const { + static_assert( + IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return !static_cast<const DerivedT *>(this)->operator<(RHS); + } + + PointerT operator->() { return &static_cast<DerivedT *>(this)->operator*(); } + PointerT operator->() const { + return &static_cast<const DerivedT *>(this)->operator*(); + } + ReferenceProxy operator[](DifferenceTypeT n) { + static_assert(IsRandomAccess, + "Subscripting is only defined for random access iterators."); + return ReferenceProxy(static_cast<DerivedT *>(this)->operator+(n)); + } + ReferenceProxy operator[](DifferenceTypeT n) const { + static_assert(IsRandomAccess, + "Subscripting is only defined for random access iterators."); + return ReferenceProxy(static_cast<const DerivedT *>(this)->operator+(n)); + } +}; + +/// \brief CRTP base class for adapting an iterator to a different type. +/// +/// This class can be used through CRTP to adapt one iterator into another. +/// Typically this is done through providing in the derived class a custom \c +/// operator* implementation. Other methods can be overridden as well. +template < + typename DerivedT, typename WrappedIteratorT, + typename IteratorCategoryT = + typename std::iterator_traits<WrappedIteratorT>::iterator_category, + typename T = typename std::iterator_traits<WrappedIteratorT>::value_type, + typename DifferenceTypeT = + typename std::iterator_traits<WrappedIteratorT>::difference_type, + typename PointerT = typename std::conditional< + std::is_same<T, typename std::iterator_traits< + WrappedIteratorT>::value_type>::value, + typename std::iterator_traits<WrappedIteratorT>::pointer, T *>::type, + typename ReferenceT = typename std::conditional< + std::is_same<T, typename std::iterator_traits< + WrappedIteratorT>::value_type>::value, + typename std::iterator_traits<WrappedIteratorT>::reference, T &>::type, + // Don't provide these, they are mostly to act as aliases below. + typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>> +class iterator_adaptor_base + : public iterator_facade_base<DerivedT, IteratorCategoryT, T, + DifferenceTypeT, PointerT, ReferenceT> { + using BaseT = typename iterator_adaptor_base::iterator_facade_base; + +protected: + WrappedIteratorT I; + + iterator_adaptor_base() = default; + + explicit iterator_adaptor_base(WrappedIteratorT u) : I(std::move(u)) { + static_assert(std::is_base_of<iterator_adaptor_base, DerivedT>::value, + "Must pass the derived type to this template!"); + } + + const WrappedIteratorT &wrapped() const { return I; } + +public: + using difference_type = DifferenceTypeT; + + DerivedT &operator+=(difference_type n) { + static_assert( + BaseT::IsRandomAccess, + "The '+=' operator is only defined for random access iterators."); + I += n; + return *static_cast<DerivedT *>(this); + } + DerivedT &operator-=(difference_type n) { + static_assert( + BaseT::IsRandomAccess, + "The '-=' operator is only defined for random access iterators."); + I -= n; + return *static_cast<DerivedT *>(this); + } + using BaseT::operator-; + difference_type operator-(const DerivedT &RHS) const { + static_assert( + BaseT::IsRandomAccess, + "The '-' operator is only defined for random access iterators."); + return I - RHS.I; + } + + // We have to explicitly provide ++ and -- rather than letting the facade + // forward to += because WrappedIteratorT might not support +=. + using BaseT::operator++; + DerivedT &operator++() { + ++I; + return *static_cast<DerivedT *>(this); + } + using BaseT::operator--; + DerivedT &operator--() { + static_assert( + BaseT::IsBidirectional, + "The decrement operator is only defined for bidirectional iterators."); + --I; + return *static_cast<DerivedT *>(this); + } + + bool operator==(const DerivedT &RHS) const { return I == RHS.I; } + bool operator<(const DerivedT &RHS) const { + static_assert( + BaseT::IsRandomAccess, + "Relational operators are only defined for random access iterators."); + return I < RHS.I; + } + + ReferenceT operator*() const { return *I; } +}; + +/// \brief An iterator type that allows iterating over the pointees via some +/// other iterator. +/// +/// The typical usage of this is to expose a type that iterates over Ts, but +/// which is implemented with some iterator over T*s: +/// +/// \code +/// using iterator = pointee_iterator<SmallVectorImpl<T *>::iterator>; +/// \endcode +template <typename WrappedIteratorT, + typename T = typename std::remove_reference< + decltype(**std::declval<WrappedIteratorT>())>::type> +struct pointee_iterator + : iterator_adaptor_base< + pointee_iterator<WrappedIteratorT>, WrappedIteratorT, + typename std::iterator_traits<WrappedIteratorT>::iterator_category, + T> { + pointee_iterator() = default; + template <typename U> + pointee_iterator(U &&u) + : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} + + T &operator*() const { return **this->I; } +}; + +template <typename RangeT, typename WrappedIteratorT = + decltype(std::begin(std::declval<RangeT>()))> +iterator_range<pointee_iterator<WrappedIteratorT>> +make_pointee_range(RangeT &&Range) { + using PointeeIteratorT = pointee_iterator<WrappedIteratorT>; + return make_range(PointeeIteratorT(std::begin(std::forward<RangeT>(Range))), + PointeeIteratorT(std::end(std::forward<RangeT>(Range)))); +} + +template <typename WrappedIteratorT, + typename T = decltype(&*std::declval<WrappedIteratorT>())> +class pointer_iterator + : public iterator_adaptor_base<pointer_iterator<WrappedIteratorT>, + WrappedIteratorT, T> { + mutable T Ptr; + +public: + pointer_iterator() = default; + + explicit pointer_iterator(WrappedIteratorT u) + : pointer_iterator::iterator_adaptor_base(std::move(u)) {} + + T &operator*() { return Ptr = &*this->I; } + const T &operator*() const { return Ptr = &*this->I; } +}; + +template <typename RangeT, typename WrappedIteratorT = + decltype(std::begin(std::declval<RangeT>()))> +iterator_range<pointer_iterator<WrappedIteratorT>> +make_pointer_range(RangeT &&Range) { + using PointerIteratorT = pointer_iterator<WrappedIteratorT>; + return make_range(PointerIteratorT(std::begin(std::forward<RangeT>(Range))), + PointerIteratorT(std::end(std::forward<RangeT>(Range)))); +} + +} // end namespace llvm + +#endif // LLVM_ADT_ITERATOR_H diff --git a/src/3rdparty/llvm/include/llvm/ADT/iterator_range.h b/src/3rdparty/llvm/include/llvm/ADT/iterator_range.h new file mode 100644 index 0000000000..3cbf6198eb --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/iterator_range.h @@ -0,0 +1,68 @@ +//===- iterator_range.h - A range adaptor for iterators ---------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +/// \file +/// This provides a very simple, boring adaptor for a begin and end iterator +/// into a range type. This should be used to build range views that work well +/// with range based for loops and range based constructors. +/// +/// Note that code here follows more standards-based coding conventions as it +/// is mirroring proposed interfaces for standardization. +/// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_ITERATOR_RANGE_H +#define LLVM_ADT_ITERATOR_RANGE_H + +#include <iterator> +#include <utility> + +namespace llvm { + +/// \brief A range adaptor for a pair of iterators. +/// +/// This just wraps two iterators into a range-compatible interface. Nothing +/// fancy at all. +template <typename IteratorT> +class iterator_range { + IteratorT begin_iterator, end_iterator; + +public: + //TODO: Add SFINAE to test that the Container's iterators match the range's + // iterators. + template <typename Container> + iterator_range(Container &&c) + //TODO: Consider ADL/non-member begin/end calls. + : begin_iterator(c.begin()), end_iterator(c.end()) {} + iterator_range(IteratorT begin_iterator, IteratorT end_iterator) + : begin_iterator(std::move(begin_iterator)), + end_iterator(std::move(end_iterator)) {} + + IteratorT begin() const { return begin_iterator; } + IteratorT end() const { return end_iterator; } +}; + +/// \brief Convenience function for iterating over sub-ranges. +/// +/// This provides a bit of syntactic sugar to make using sub-ranges +/// in for loops a bit easier. Analogous to std::make_pair(). +template <class T> iterator_range<T> make_range(T x, T y) { + return iterator_range<T>(std::move(x), std::move(y)); +} + +template <typename T> iterator_range<T> make_range(std::pair<T, T> p) { + return iterator_range<T>(std::move(p.first), std::move(p.second)); +} + +template<typename T> +iterator_range<decltype(begin(std::declval<T>()))> drop_begin(T &&t, int n) { + return make_range(std::next(begin(t), n), end(t)); +} +} + +#endif diff --git a/src/3rdparty/llvm/include/llvm/ADT/simple_ilist.h b/src/3rdparty/llvm/include/llvm/ADT/simple_ilist.h new file mode 100644 index 0000000000..4c7598a1ac --- /dev/null +++ b/src/3rdparty/llvm/include/llvm/ADT/simple_ilist.h @@ -0,0 +1,315 @@ +//===- llvm/ADT/simple_ilist.h - Simple Intrusive List ----------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_SIMPLE_ILIST_H +#define LLVM_ADT_SIMPLE_ILIST_H + +#include "llvm/ADT/ilist_base.h" +#include "llvm/ADT/ilist_iterator.h" +#include "llvm/ADT/ilist_node.h" +#include "llvm/ADT/ilist_node_options.h" +#include "llvm/Support/Compiler.h" +#include <algorithm> +#include <cassert> +#include <cstddef> +#include <functional> +#include <iterator> +#include <utility> + +namespace llvm { + +/// A simple intrusive list implementation. +/// +/// This is a simple intrusive list for a \c T that inherits from \c +/// ilist_node<T>. The list never takes ownership of anything inserted in it. +/// +/// Unlike \a iplist<T> and \a ilist<T>, \a simple_ilist<T> never allocates or +/// deletes values, and has no callback traits. +/// +/// The API for adding nodes include \a push_front(), \a push_back(), and \a +/// insert(). These all take values by reference (not by pointer), except for +/// the range version of \a insert(). +/// +/// There are three sets of API for discarding nodes from the list: \a +/// remove(), which takes a reference to the node to remove, \a erase(), which +/// takes an iterator or iterator range and returns the next one, and \a +/// clear(), which empties out the container. All three are constant time +/// operations. None of these deletes any nodes; in particular, if there is a +/// single node in the list, then these have identical semantics: +/// \li \c L.remove(L.front()); +/// \li \c L.erase(L.begin()); +/// \li \c L.clear(); +/// +/// As a convenience for callers, there are parallel APIs that take a \c +/// Disposer (such as \c std::default_delete<T>): \a removeAndDispose(), \a +/// eraseAndDispose(), and \a clearAndDispose(). These have different names +/// because the extra semantic is otherwise non-obvious. They are equivalent +/// to calling \a std::for_each() on the range to be discarded. +/// +/// The currently available \p Options customize the nodes in the list. The +/// same options must be specified in the \a ilist_node instantation for +/// compatibility (although the order is irrelevant). +/// \li Use \a ilist_tag to designate which ilist_node for a given \p T this +/// list should use. This is useful if a type \p T is part of multiple, +/// independent lists simultaneously. +/// \li Use \a ilist_sentinel_tracking to always (or never) track whether a +/// node is a sentinel. Specifying \c true enables the \a +/// ilist_node::isSentinel() API. Unlike \a ilist_node::isKnownSentinel(), +/// which is only appropriate for assertions, \a ilist_node::isSentinel() is +/// appropriate for real logic. +/// +/// Here are examples of \p Options usage: +/// \li \c simple_ilist<T> gives the defaults. \li \c +/// simple_ilist<T,ilist_sentinel_tracking<true>> enables the \a +/// ilist_node::isSentinel() API. +/// \li \c simple_ilist<T,ilist_tag<A>,ilist_sentinel_tracking<false>> +/// specifies a tag of A and that tracking should be off (even when +/// LLVM_ENABLE_ABI_BREAKING_CHECKS are enabled). +/// \li \c simple_ilist<T,ilist_sentinel_tracking<false>,ilist_tag<A>> is +/// equivalent to the last. +/// +/// See \a is_valid_option for steps on adding a new option. +template <typename T, class... Options> +class simple_ilist + : ilist_detail::compute_node_options<T, Options...>::type::list_base_type, + ilist_detail::SpecificNodeAccess< + typename ilist_detail::compute_node_options<T, Options...>::type> { + static_assert(ilist_detail::check_options<Options...>::value, + "Unrecognized node option!"); + using OptionsT = + typename ilist_detail::compute_node_options<T, Options...>::type; + using list_base_type = typename OptionsT::list_base_type; + ilist_sentinel<OptionsT> Sentinel; + +public: + using value_type = typename OptionsT::value_type; + using pointer = typename OptionsT::pointer; + using reference = typename OptionsT::reference; + using const_pointer = typename OptionsT::const_pointer; + using const_reference = typename OptionsT::const_reference; + using iterator = ilist_iterator<OptionsT, false, false>; + using const_iterator = ilist_iterator<OptionsT, false, true>; + using reverse_iterator = ilist_iterator<OptionsT, true, false>; + using const_reverse_iterator = ilist_iterator<OptionsT, true, true>; + using size_type = size_t; + using difference_type = ptrdiff_t; + + simple_ilist() = default; + ~simple_ilist() = default; + + // No copy constructors. + simple_ilist(const simple_ilist &) = delete; + simple_ilist &operator=(const simple_ilist &) = delete; + + // Move constructors. + simple_ilist(simple_ilist &&X) { splice(end(), X); } + simple_ilist &operator=(simple_ilist &&X) { + clear(); + splice(end(), X); + return *this; + } + + iterator begin() { return ++iterator(Sentinel); } + const_iterator begin() const { return ++const_iterator(Sentinel); } + iterator end() { return iterator(Sentinel); } + const_iterator end() const { return const_iterator(Sentinel); } + reverse_iterator rbegin() { return ++reverse_iterator(Sentinel); } + const_reverse_iterator rbegin() const { + return ++const_reverse_iterator(Sentinel); + } + reverse_iterator rend() { return reverse_iterator(Sentinel); } + const_reverse_iterator rend() const { + return const_reverse_iterator(Sentinel); + } + + /// Check if the list is empty in constant time. + LLVM_NODISCARD bool empty() const { return Sentinel.empty(); } + + /// Calculate the size of the list in linear time. + LLVM_NODISCARD size_type size() const { + return std::distance(begin(), end()); + } + + reference front() { return *begin(); } + const_reference front() const { return *begin(); } + reference back() { return *rbegin(); } + const_reference back() const { return *rbegin(); } + + /// Insert a node at the front; never copies. + void push_front(reference Node) { insert(begin(), Node); } + + /// Insert a node at the back; never copies. + void push_back(reference Node) { insert(end(), Node); } + + /// Remove the node at the front; never deletes. + void pop_front() { erase(begin()); } + + /// Remove the node at the back; never deletes. + void pop_back() { erase(--end()); } + + /// Swap with another list in place using std::swap. + void swap(simple_ilist &X) { std::swap(*this, X); } + + /// Insert a node by reference; never copies. + iterator insert(iterator I, reference Node) { + list_base_type::insertBefore(*I.getNodePtr(), *this->getNodePtr(&Node)); + return iterator(&Node); + } + + /// Insert a range of nodes; never copies. + template <class Iterator> + void insert(iterator I, Iterator First, Iterator Last) { + for (; First != Last; ++First) + insert(I, *First); + } + + /// Clone another list. + template <class Cloner, class Disposer> + void cloneFrom(const simple_ilist &L2, Cloner clone, Disposer dispose) { + clearAndDispose(dispose); + for (const_reference V : L2) + push_back(*clone(V)); + } + + /// Remove a node by reference; never deletes. + /// + /// \see \a erase() for removing by iterator. + /// \see \a removeAndDispose() if the node should be deleted. + void remove(reference N) { list_base_type::remove(*this->getNodePtr(&N)); } + + /// Remove a node by reference and dispose of it. + template <class Disposer> + void removeAndDispose(reference N, Disposer dispose) { + remove(N); + dispose(&N); + } + + /// Remove a node by iterator; never deletes. + /// + /// \see \a remove() for removing by reference. + /// \see \a eraseAndDispose() it the node should be deleted. + iterator erase(iterator I) { + assert(I != end() && "Cannot remove end of list!"); + remove(*I++); + return I; + } + + /// Remove a range of nodes; never deletes. + /// + /// \see \a eraseAndDispose() if the nodes should be deleted. + iterator erase(iterator First, iterator Last) { + list_base_type::removeRange(*First.getNodePtr(), *Last.getNodePtr()); + return Last; + } + + /// Remove a node by iterator and dispose of it. + template <class Disposer> + iterator eraseAndDispose(iterator I, Disposer dispose) { + auto Next = std::next(I); + erase(I); + dispose(&*I); + return Next; + } + + /// Remove a range of nodes and dispose of them. + template <class Disposer> + iterator eraseAndDispose(iterator First, iterator Last, Disposer dispose) { + while (First != Last) + First = eraseAndDispose(First, dispose); + return Last; + } + + /// Clear the list; never deletes. + /// + /// \see \a clearAndDispose() if the nodes should be deleted. + void clear() { Sentinel.reset(); } + + /// Clear the list and dispose of the nodes. + template <class Disposer> void clearAndDispose(Disposer dispose) { + eraseAndDispose(begin(), end(), dispose); + } + + /// Splice in another list. + void splice(iterator I, simple_ilist &L2) { + splice(I, L2, L2.begin(), L2.end()); + } + + /// Splice in a node from another list. + void splice(iterator I, simple_ilist &L2, iterator Node) { + splice(I, L2, Node, std::next(Node)); + } + + /// Splice in a range of nodes from another list. + void splice(iterator I, simple_ilist &, iterator First, iterator Last) { + list_base_type::transferBefore(*I.getNodePtr(), *First.getNodePtr(), + *Last.getNodePtr()); + } + + /// Merge in another list. + /// + /// \pre \c this and \p RHS are sorted. + ///@{ + void merge(simple_ilist &RHS) { merge(RHS, std::less<T>()); } + template <class Compare> void merge(simple_ilist &RHS, Compare comp); + ///@} + + /// Sort the list. + ///@{ + void sort() { sort(std::less<T>()); } + template <class Compare> void sort(Compare comp); + ///@} +}; + +template <class T, class... Options> +template <class Compare> +void simple_ilist<T, Options...>::merge(simple_ilist &RHS, Compare comp) { + if (this == &RHS || RHS.empty()) + return; + iterator LI = begin(), LE = end(); + iterator RI = RHS.begin(), RE = RHS.end(); + while (LI != LE) { + if (comp(*RI, *LI)) { + // Transfer a run of at least size 1 from RHS to LHS. + iterator RunStart = RI++; + RI = std::find_if(RI, RE, [&](reference RV) { return !comp(RV, *LI); }); + splice(LI, RHS, RunStart, RI); + if (RI == RE) + return; + } + ++LI; + } + // Transfer the remaining RHS nodes once LHS is finished. + splice(LE, RHS, RI, RE); +} + +template <class T, class... Options> +template <class Compare> +void simple_ilist<T, Options...>::sort(Compare comp) { + // Vacuously sorted. + if (empty() || std::next(begin()) == end()) + return; + + // Split the list in the middle. + iterator Center = begin(), End = begin(); + while (End != end() && ++End != end()) { + ++Center; + ++End; + } + simple_ilist RHS; + RHS.splice(RHS.end(), *this, Center, end()); + + // Sort the sublists and merge back together. + sort(comp); + RHS.sort(comp); + merge(RHS, comp); +} + +} // end namespace llvm + +#endif // LLVM_ADT_SIMPLE_ILIST_H |