Vc/common/iterators.h

0001 /*  This file is part of the Vc library. {{{
0002 Copyright © 2013-2015 Matthias Kretz <kretz@kde.org>
0003
0004 Redistribution and use in source and binary forms, with or without
0005 modification, are permitted provided that the following conditions are met:
0006     * Redistributions of source code must retain the above copyright
0007       notice, this list of conditions and the following disclaimer.
0008     * Redistributions in binary form must reproduce the above copyright
0009       notice, this list of conditions and the following disclaimer in the
0010       documentation and/or other materials provided with the distribution.
0011     * Neither the names of contributing organizations nor the
0012       names of its contributors may be used to endorse or promote products
0013       derived from this software without specific prior written permission.
0014
0015 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
0016 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
0017 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
0018 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY
0019 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
0020 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
0021 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
0022 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
0023 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
0024 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
0025
0026 }}}*/
0027
0028 #ifndef VC_COMMON_ITERATORS_H_
0029 #define VC_COMMON_ITERATORS_H_
0030
0031 #include <array>
0032 #include <iterator>
0033 #ifdef Vc_MSVC
0034 #include <intrin.h> // for _BitScanForward
0035 #endif  // Vc_MSVC
0036 #include "where.h"
0037 #include "elementreference.h"
0038 #include "macros.h"
0039
0040 namespace Vc_VERSIONED_NAMESPACE
0041 {
0042 namespace Common
0043 {
0044
0045 template<typename _V, typename Flags> class MemoryVector;
0046 template<typename _V, typename Flags> class MemoryVectorIterator;
0047
0048 template <typename V> class Iterator;
0049 template <typename V, bool> class IteratorBase;
0050 template <typename V> class IteratorBase<V, true>
0051 {
0052 public:
0053     using iterator_category = std::input_iterator_tag;
0054     using value_type = typename V::value_type;
0055     using difference_type = int;
0056     using reference = value_type;
0057     Vc_ALWAYS_INLINE reference operator*() const { return v()[i()]; }
0058     Vc_ALWAYS_INLINE reference operator[](difference_type i2) const { return v()[i2]; }
0059
0060 private:
0061     Vc_INTRINSIC V &v() const { return *static_cast<const Iterator<V> *>(this)->v; }
0062     Vc_INTRINSIC difference_type i() const
0063     {
0064         return static_cast<const Iterator<V> *>(this)->i;
0065     }
0066 };
0067
0068 template <typename V> class IteratorBase<V, false>
0069 {
0070 public:
0071     using iterator_category = std::input_iterator_tag;
0072     using value_type = typename V::value_type;
0073     using difference_type = int;
0074     using reference = Vc::Detail::ElementReference<V, IteratorBase>;
0075     Vc_ALWAYS_INLINE reference operator*() const { return {*v(), i()}; }
0076     Vc_ALWAYS_INLINE reference operator[](difference_type i2) const { return {*v(), i2}; }
0077
0078 private:
0079     Vc_INTRINSIC V *v() const { return static_cast<const Iterator<V> *>(this)->v; }
0080     Vc_INTRINSIC difference_type i() const
0081     {
0082         return static_cast<const Iterator<V> *>(this)->i;
0083     }
0084
0085     friend reference;
0086     static Vc_INTRINSIC value_type get(const V &o, int i)
0087     {
0088         return o[i];
0089     }
0090     template <typename T> static Vc_INTRINSIC void set(V &o, int i, T &&v)
0091     {
0092         o[i] = std::forward<T>(v);
0093     }
0094 };
0095
0096 // class Iterator {{{
0097 template <typename V> class Iterator : public IteratorBase<V, std::is_const<V>::value>
0098 {
0099     using Base = IteratorBase<V, std::is_const<V>::value>;
0100     friend Base;
0101
0102 public:
0103     using typename Base::iterator_category;
0104     using typename Base::value_type;
0105     using typename Base::difference_type;
0106     using pointer = const Iterator *;
0107     using typename Base::reference;
0108
0109     constexpr Iterator() = default;
0110     constexpr Iterator(V &_v, difference_type _i) : v(&_v), i(_i) {}
0111     // rely on implicit copy constructor/assignment
0112
0113     Vc_ALWAYS_INLINE pointer operator->() const { return this; }
0114     using Base::operator*;
0115
0116     Vc_ALWAYS_INLINE Iterator &operator++()    { ++i; return *this; }
0117     Vc_ALWAYS_INLINE Iterator  operator++(int) { Iterator tmp = *this; ++i; return tmp; }
0118
0119     // bidirectional iteration is supported
0120     Vc_ALWAYS_INLINE Iterator &operator--()    { --i; return *this; }
0121     Vc_ALWAYS_INLINE Iterator  operator--(int) { Iterator tmp = *this; --i; return tmp; }
0122
0123     // RandomAccessIterator:
0124     using Base::operator[];
0125     Vc_ALWAYS_INLINE Iterator &operator+=(difference_type d) { i += d; return *this; }
0126     Vc_ALWAYS_INLINE Iterator &operator-=(difference_type d) { i -= d; return *this; }
0127     Vc_ALWAYS_INLINE Iterator operator+(difference_type d) const { return {*v, i + d}; }
0128     Vc_ALWAYS_INLINE Iterator operator-(difference_type d) const { return {*v, i - d}; }
0129     Vc_ALWAYS_INLINE difference_type operator-(const Iterator &rhs) const { return i - rhs.i; }
0130     friend Vc_ALWAYS_INLINE Iterator operator+(difference_type d, const Iterator &rhs)
0131     {
0132         return {*rhs.v, rhs.i + d};
0133     }
0134
0135     // InputIterator would not need to test v == rhs.v, but except for `reference` this
0136     // class implements a complete RandomAccessIterator
0137     Vc_ALWAYS_INLINE bool operator==(const Iterator<V> &rhs) const { return v == rhs.v && i == rhs.i; }
0138     Vc_ALWAYS_INLINE bool operator!=(const Iterator<V> &rhs) const { return v == rhs.v && i != rhs.i; }
0139     Vc_ALWAYS_INLINE bool operator< (const Iterator<V> &rhs) const { return v == rhs.v && i <  rhs.i; }
0140     Vc_ALWAYS_INLINE bool operator<=(const Iterator<V> &rhs) const { return v == rhs.v && i <= rhs.i; }
0141     Vc_ALWAYS_INLINE bool operator> (const Iterator<V> &rhs) const { return v == rhs.v && i >  rhs.i; }
0142     Vc_ALWAYS_INLINE bool operator>=(const Iterator<V> &rhs) const { return v == rhs.v && i >= rhs.i; }
0143
0144 private:
0145     V *v = nullptr;
0146     difference_type i = 0;
0147 };/*}}}*/
0148
0149 template <typename V> using ConstIterator = Iterator<const V>;
0150
0151     class BitmaskIterator/*{{{*/
0152     {
0153 #ifdef Vc_MSVC
0154         unsigned long mask;
0155         unsigned long bit;
0156 #else
0157         size_t mask;
0158         size_t bit;
0159 #endif
0160
0161         void nextBit()
0162         {
0163 #ifdef Vc_GNU_ASM
0164             bit = __builtin_ctzl(mask);
0165 #elif defined(Vc_MSVC)
0166             _BitScanForward(&bit, mask);
0167 #else
0168 #error "Not implemented yet. Please contact vc-devel@compeng.uni-frankfurt.de"
0169 #endif
0170         }
0171         void resetLsb()
0172         {
0173             // 01100100 - 1 = 01100011
0174             mask &= (mask - 1);
0175             /*
0176 #ifdef Vc_GNU_ASM
0177             __asm__("btr %1,%0" : "+r"(mask) : "r"(bit));
0178 #elif defined(_WIN64)
0179             _bittestandreset64(&mask, bit);
0180 #elif defined(_WIN32)
0181             _bittestandreset(&mask, bit);
0182 #else
0183 #error "Not implemented yet. Please contact vc-devel@compeng.uni-frankfurt.de"
0184 #endif
0185             */
0186         }
0187     public:
0188         BitmaskIterator(decltype(mask) m) : mask(m) { nextBit(); }
0189         BitmaskIterator(const BitmaskIterator &) = default;
0190         BitmaskIterator(BitmaskIterator &&) = default;
0191
0192         Vc_ALWAYS_INLINE size_t operator->() const { return bit; }
0193         Vc_ALWAYS_INLINE size_t operator*() const { return bit; }
0194
0195         Vc_ALWAYS_INLINE BitmaskIterator &operator++()    { resetLsb(); nextBit(); return *this; }
0196         Vc_ALWAYS_INLINE BitmaskIterator  operator++(int) { BitmaskIterator tmp = *this; resetLsb(); nextBit(); return tmp; }
0197
0198         Vc_ALWAYS_INLINE bool operator==(const BitmaskIterator &rhs) const { return mask == rhs.mask; }
0199         Vc_ALWAYS_INLINE bool operator!=(const BitmaskIterator &rhs) const { return mask != rhs.mask; }
0200     };/*}}}*/
0201
0202 template <typename T>
0203 Vc_ALWAYS_INLINE
0204     enable_if<Traits::is_simd_vector<T>::value || Traits::is_simd_mask<T>::value,
0205               Iterator<typename std::remove_reference<T>::type>>
0206     begin(T &&x)
0207 {
0208     return {std::forward<T>(x), 0};
0209 }
0210
0211 template <typename T>
0212 Vc_ALWAYS_INLINE
0213     enable_if<Traits::is_simd_vector<T>::value || Traits::is_simd_mask<T>::value,
0214               Iterator<typename std::remove_reference<T>::type>>
0215     end(T &&x)
0216 {
0217     using TT = typename std::decay<T>::type;
0218     return {std::forward<T>(x), int(TT::size())};
0219 }
0220
0221 template <typename T>
0222 Vc_ALWAYS_INLINE enable_if<
0223     Traits::is_simd_mask<T>::value || Traits::is_simd_vector<T>::value, ConstIterator<T>>
0224 cbegin(const T &v)
0225 {
0226     return {v, 0};
0227 }
0228
0229 template <typename T>
0230 Vc_ALWAYS_INLINE enable_if<
0231     Traits::is_simd_mask<T>::value || Traits::is_simd_vector<T>::value, ConstIterator<T>>
0232 cend(const T &v)
0233 {
0234     return {v, int(T::size())};
0235 }
0236
0237 template<typename M> Vc_ALWAYS_INLINE BitmaskIterator begin(const WhereImpl::WhereMask<M> &w)
0238 {
0239     return w.mask.toInt();
0240 }
0241
0242 template<typename M> Vc_ALWAYS_INLINE BitmaskIterator end(const WhereImpl::WhereMask<M> &)
0243 {
0244     return 0;
0245 }
0246
0247 template<typename V, typename Flags, typename T> Vc_ALWAYS_INLINE MemoryVectorIterator<V, Flags>
0248     makeIterator(T *mem, Flags)
0249 {
0250     return new(mem) MemoryVector<V, Flags>;
0251 }
0252
0253 template<typename V, typename Flags, typename T> Vc_ALWAYS_INLINE MemoryVectorIterator<const V, Flags>
0254     makeIterator(const T *mem, Flags)
0255 {
0256     return new(const_cast<T *>(mem)) MemoryVector<const V, Flags>;
0257 }
0258
0259 template<typename V, typename Flags, typename FlagsX> Vc_ALWAYS_INLINE MemoryVectorIterator<V, Flags>
0260     makeIterator(MemoryVector<V, FlagsX> &mv, Flags)
0261 {
0262     return new(&mv) MemoryVector<V, Flags>;
0263 }
0264
0265 template<typename V, typename Flags, typename FlagsX> Vc_ALWAYS_INLINE MemoryVectorIterator<const V, Flags>
0266     makeIterator(MemoryVector<const V, FlagsX> &mv, Flags)
0267 {
0268     return new(&mv) MemoryVector<const V, Flags>;
0269 }
0270
0271 }  // namespace Common
0272
0273 using Common::begin;
0274 using Common::end;
0275 using Common::cbegin;
0276 using Common::cend;
0277 using Common::makeIterator;
0278 }  // namespace Vc
0279
0280 #endif // VC_COMMON_ITERATORS_H_
0281
0282 // vim: foldmethod=marker