diff options
author | Chandler Carruth <chandlerc@gmail.com> | 2014-04-24 03:31:23 +0000 |
---|---|---|
committer | Chandler Carruth <chandlerc@gmail.com> | 2014-04-24 03:31:23 +0000 |
commit | beee61d3e6c7e202160233c2f24ec9d5d03f89cc (patch) | |
tree | 522d14fb568009e0a26493485a796a0bc51d6ad2 /include | |
parent | c118614379930598cb4ecfb80bfbb662f1588f64 (diff) | |
download | llvm-beee61d3e6c7e202160233c2f24ec9d5d03f89cc.tar.gz llvm-beee61d3e6c7e202160233c2f24ec9d5d03f89cc.tar.bz2 llvm-beee61d3e6c7e202160233c2f24ec9d5d03f89cc.tar.xz |
[ADT] Add a generic iterator utility for adapting iterators much like
Boost's iterator_adaptor, and a specific adaptor which iterates over
pointees when wrapped around an iterator over pointers.
This is the result of a long discussion on IRC with Duncan Smith, Dave
Blaikie, Richard Smith, and myself. Essentially, I could use some subset
of the iterator facade facilities often used from Boost, and everyone
seemed interested in having the functionality in a reasonably generic
form. I've tried to strike a balance between the pragmatism and the
established Boost design. The primary differences are:
1) Delegating to the standard iterator interface names rather than
special names that then make up a second iterator-like API.
2) Using the name 'pointee_iterator' which seems more clear than
'indirect_iterator'. The whole business of calling the '*p' operation
'pointer indirection' in the standard is ... quite confusing. And
'dereference' is no better of a term for moving from a pointer to
a reference.
Hoping Duncan, and others continue to provide comments on this until
we've got a nice, minimal abstraction.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207069 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include')
-rw-r--r-- | include/llvm/ADT/iterator.h | 145 |
1 files changed, 145 insertions, 0 deletions
diff --git a/include/llvm/ADT/iterator.h b/include/llvm/ADT/iterator.h new file mode 100644 index 0000000000..1edf61ca0c --- /dev/null +++ b/include/llvm/ADT/iterator.h @@ -0,0 +1,145 @@ +//===- 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 <iterator> + +namespace llvm { + +/// \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. +/// +/// FIXME: Factor out the iterator-facade-like aspects into a base class that +/// can be used for defining completely custom iterators. +template <typename DerivedT, typename WrappedIteratorT, typename T, + typename PointerT = T *, typename ReferenceT = T &, + // Don't provide these, they are mostly to act as aliases below. + typename WrappedTraitsT = std::iterator_traits<WrappedIteratorT>> +class iterator_adaptor_base + : public std::iterator<typename WrappedTraitsT::iterator_category, T, + typename WrappedTraitsT::difference_type, PointerT, + ReferenceT> { +protected: + WrappedIteratorT I; + + iterator_adaptor_base() {} + + template < + typename U, + typename = typename std::enable_if< + !std::is_same<typename std::remove_cv< + typename std::remove_reference<U>::type>::type, + DerivedT>::value>::type> + explicit iterator_adaptor_base(U &&u) + : I(std::forward<U &&>(u)) {} + +public: + typedef typename iterator_adaptor_base::iterator::difference_type + difference_type; + + DerivedT &operator+=(difference_type n) { + I += n; + return *static_cast<DerivedT *>(this); + } + DerivedT &operator-=(difference_type n) { + I -= n; + return *static_cast<DerivedT *>(this); + } + DerivedT operator+(difference_type n) const { + DerivedT tmp = *this; + tmp += n; + return tmp; + } + friend DerivedT operator+(difference_type n, const DerivedT &i) { + return i + n; + } + DerivedT operator-(difference_type n) const { + DerivedT tmp = *this; + tmp -= n; + return tmp; + } + difference_type operator-(const DerivedT &RHS) const { return I - RHS.I; } + + DerivedT &operator++() { + ++I; + return *static_cast<DerivedT *>(this); + } + DerivedT &operator--() { + --I; + return *static_cast<DerivedT *>(this); + } + DerivedT operator++(int) { + DerivedT tmp = *static_cast<DerivedT *>(this); + ++*this; + return tmp; + } + DerivedT operator--(int) { + DerivedT tmp = *static_cast<DerivedT *>(this); + --*this; + return tmp; + } + + bool operator==(const DerivedT &RHS) const { return I == RHS.I; } + bool operator!=(const DerivedT &RHS) const { + return !static_cast<const DerivedT *>(this)->operator==(RHS); + } + + bool operator<(const DerivedT &RHS) const { return I < RHS.I; } + bool operator>(const DerivedT &RHS) const { + return !static_cast<const DerivedT *>(this)->operator<(RHS) && + !static_cast<const DerivedT *>(this)->operator==(RHS); + } + bool operator<=(const DerivedT &RHS) const { + return !static_cast<const DerivedT *>(this)->operator>(RHS); + } + bool operator>=(const DerivedT &RHS) const { + return !static_cast<const DerivedT *>(this)->operator<(RHS); + } + + ReferenceT operator*() const { return *I; } + PointerT operator->() const { + return static_cast<const DerivedT *>(this)->operator*(); + } + ReferenceT operator[](difference_type n) const { + return *static_cast<const DerivedT *>(this)->operator+(n); + } +}; + +/// \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 +/// typedef pointee_iterator<SmallVectorImpl<T *>::iterator> iterator; +/// \endcode +template < + typename WrappedIteratorT, + typename T = typename std::remove_pointer< + typename std::iterator_traits<WrappedIteratorT>::value_type>::type> +struct pointee_iterator + : iterator_adaptor_base<pointee_iterator<WrappedIteratorT>, + WrappedIteratorT, T> { + pointee_iterator() {} + template <typename U> + pointee_iterator(U &&u) + : pointee_iterator::iterator_adaptor_base(std::forward<U &&>(u)) {} + + T &operator*() const { return **this->I; } +}; + +} + +#endif |