1 /* 2 * Copyright 2019 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef SkZip_DEFINED 9 #define SkZip_DEFINED 10 11 #include <iterator> 12 #include <tuple> 13 #include <type_traits> 14 15 #include "include/core/SkTypes.h" 16 #include "include/private/SkTemplates.h" 17 #include "include/private/SkTo.h" 18 #include "src/core/SkSpan.h" 19 20 // Take a list of things that can be pointers, and use them all in parallel. The iterators and 21 // accessor operator[] for the class produce a tuple of the items. 22 template<typename... Ts> 23 class SkZip { 24 using ReturnTuple = std::tuple<Ts&...>; 25 26 class Iterator { 27 public: 28 using value_type = ReturnTuple; 29 using difference_type = ptrdiff_t; 30 using pointer = value_type*; 31 using reference = value_type; 32 using iterator_category = std::input_iterator_tag; Iterator(const SkZip * zip,size_t index)33 constexpr Iterator(const SkZip* zip, size_t index) : fZip{zip}, fIndex{index} { } Iterator(const Iterator & that)34 constexpr Iterator(const Iterator& that) : Iterator{ that.fZip, that.fIndex } { } 35 constexpr Iterator& operator++() { ++fIndex; return *this; } 36 constexpr Iterator operator++(int) { Iterator tmp(*this); operator++(); return tmp; } 37 constexpr bool operator==(const Iterator& rhs) const { return fIndex == rhs.fIndex; } 38 constexpr bool operator!=(const Iterator& rhs) const { return fIndex != rhs.fIndex; } 39 constexpr reference operator*() { return (*fZip)[fIndex]; } 40 friend constexpr difference_type operator-(Iterator lhs, Iterator rhs) { 41 return lhs.fIndex - rhs.fIndex; 42 } 43 44 private: 45 const SkZip* const fZip = nullptr; 46 size_t fIndex = 0; 47 }; 48 49 template<typename T> 50 static constexpr T* nullify = nullptr; 51 52 public: SkZip()53 constexpr SkZip() : fPointers{nullify<Ts>...}, fSize{0} {} 54 constexpr SkZip(size_t) = delete; SkZip(size_t size,Ts * ...ts)55 constexpr SkZip(size_t size, Ts*... ts) 56 : fPointers{ts...} 57 , fSize{size} {} 58 constexpr SkZip(const SkZip& that) = default; 59 60 // Check to see if U can be used for const T or is the same as T 61 template <typename U, typename T> 62 using CanConvertToConst = typename std::integral_constant<bool, 63 std::is_convertible<U*, T*>::value && sizeof(U) == sizeof(T)>::type; 64 65 // Allow SkZip<const T> to be constructed from SkZip<T>. 66 template<typename... Us, 67 typename = std::enable_if<skstd::conjunction<CanConvertToConst<Us, Ts>...>::value>> SkZip(const SkZip<Us...> & that)68 constexpr SkZip(const SkZip<Us...>& that) 69 : fPointers(that.data()) 70 , fSize{that.size()} { } 71 72 constexpr ReturnTuple operator[](size_t i) const { return this->index(i);} size()73 constexpr size_t size() const { return fSize; } empty()74 constexpr bool empty() const { return this->size() == 0; } front()75 constexpr ReturnTuple front() const { return this->index(0); } back()76 constexpr ReturnTuple back() const { return this->index(this->size() - 1); } begin()77 constexpr Iterator begin() const { return Iterator{this, 0}; } end()78 constexpr Iterator end() const { return Iterator{this, this->size()}; } get()79 template<size_t I> constexpr auto get() const { 80 return SkMakeSpan(std::get<I>(fPointers), fSize); 81 } data()82 constexpr std::tuple<Ts*...> data() const { return fPointers; } first(size_t n)83 constexpr SkZip first(size_t n) const { 84 SkASSERT(n <= this->size()); 85 if (n == 0) { return SkZip(); } 86 return SkZip{n, fPointers}; 87 } last(size_t n)88 constexpr SkZip last(size_t n) const { 89 SkASSERT(n <= this->size()); 90 if (n == 0) { return SkZip(); } 91 return SkZip{n, this->pointersAt(fSize - n)}; 92 } subspan(size_t offset,size_t count)93 constexpr SkZip subspan(size_t offset, size_t count) const { 94 SkASSERT(offset < this->size()); 95 SkASSERT(count <= this->size() - offset); 96 if (count == 0) { return SkZip(); } 97 return SkZip(count, pointersAt(offset)); 98 } 99 100 private: SkZip(size_t n,const std::tuple<Ts * ...> & pointers)101 constexpr SkZip(size_t n, const std::tuple<Ts*...>& pointers) 102 : fPointers{pointers} 103 , fSize{n} {} 104 index(size_t i)105 constexpr ReturnTuple index(size_t i) const { 106 SkASSERT(this->size() > 0); 107 SkASSERT(i < this->size()); 108 return indexDetail(i, skstd::make_index_sequence<sizeof...(Ts)>{}); 109 } 110 111 template<std::size_t... Is> indexDetail(size_t i,skstd::index_sequence<Is...>)112 constexpr ReturnTuple indexDetail(size_t i, skstd::index_sequence<Is...>) const { 113 return ReturnTuple((std::get<Is>(fPointers))[i]...); 114 } 115 pointersAt(size_t i)116 std::tuple<Ts*...> pointersAt(size_t i) const { 117 SkASSERT(this->size() > 0); 118 SkASSERT(i < this->size()); 119 return pointersAtDetail(i, skstd::make_index_sequence<sizeof...(Ts)>{}); 120 } 121 122 template<std::size_t... Is> pointersAtDetail(size_t i,skstd::index_sequence<Is...>)123 constexpr std::tuple<Ts*...> pointersAtDetail(size_t i, skstd::index_sequence<Is...>) const { 124 return std::tuple<Ts*...>{&(std::get<Is>(fPointers))[i]...}; 125 } 126 127 std::tuple<Ts*...> fPointers; 128 size_t fSize; 129 }; 130 131 class SkMakeZipDetail { 132 template<typename T> struct DecayPointer{ 133 using U = typename std::remove_cv<typename std::remove_reference<T>::type>::type; 134 using type = typename std::conditional<std::is_pointer<U>::value, U, T>::type; 135 }; 136 template<typename T> using DecayPointerT = typename DecayPointer<T>::type; 137 138 template<typename C> struct ContiguousMemory { }; 139 template<typename T> struct ContiguousMemory<T*> { 140 using value_type = T; 141 static constexpr value_type* Data(T* t) { return t; } 142 static constexpr size_t Size(T* s) { return SIZE_MAX; } 143 }; 144 template<typename T, size_t N> struct ContiguousMemory<T(&)[N]> { 145 using value_type = T; 146 static constexpr value_type* Data(T(&t)[N]) { return t; } 147 static constexpr size_t Size(T(&)[N]) { return N; } 148 }; 149 // In general, we don't want r-value collections, but SkSpans are ok, because they are a view 150 // onto an actual container. 151 template<typename T> struct ContiguousMemory<SkSpan<T>> { 152 using value_type = T; 153 static constexpr value_type* Data(SkSpan<T> s) { return s.data(); } 154 static constexpr size_t Size(SkSpan<T> s) { return s.size(); } 155 }; 156 // Only accept l-value references to collections. 157 template<typename C> struct ContiguousMemory<C&> { 158 using value_type = typename std::remove_pointer<decltype(std::declval<C>().data())>::type; 159 static constexpr value_type* Data(C& c) { return c.data(); } 160 static constexpr size_t Size(C& c) { return c.size(); } 161 }; 162 template<typename C> using Span = ContiguousMemory<DecayPointerT<C>>; 163 template<typename C> using ValueType = typename Span<C>::value_type; 164 165 template<typename C, typename... Ts> struct PickOneSize { }; 166 template <typename T, typename... Ts> struct PickOneSize<T*, Ts...> { 167 static constexpr size_t Size(T* t, Ts... ts) { 168 return PickOneSize<Ts...>::Size(std::forward<Ts>(ts)...); 169 } 170 }; 171 template <typename T, typename... Ts, size_t N> struct PickOneSize<T(&)[N], Ts...> { 172 static constexpr size_t Size(T(&)[N], Ts...) { return N; } 173 }; 174 template<typename T, typename... Ts> struct PickOneSize<SkSpan<T>, Ts...> { 175 static constexpr size_t Size(SkSpan<T> s, Ts...) { return s.size(); } 176 }; 177 template<typename C, typename... Ts> struct PickOneSize<C&, Ts...> { 178 static constexpr size_t Size(C& c, Ts...) { return c.size(); } 179 }; 180 181 public: 182 template<typename... Ts> 183 static constexpr auto MakeZip(Ts&& ... ts) { 184 185 // Pick the first collection that has a size, and use that for the size. 186 size_t size = PickOneSize<DecayPointerT<Ts>...>::Size(std::forward<Ts>(ts)...); 187 188 #ifdef SK_DEBUG 189 // Check that all sizes are the same. 190 size_t minSize = SIZE_MAX; 191 size_t maxSize = 0; 192 for (size_t s : {Span<Ts>::Size(std::forward<Ts>(ts))...}) { 193 if (s != SIZE_MAX) { 194 minSize = std::min(minSize, s); 195 maxSize = std::max(maxSize, s); 196 } 197 } 198 SkASSERT(minSize == maxSize); 199 #endif 200 201 return SkZip<ValueType<Ts>...>{size, Span<Ts>::Data(std::forward<Ts>(ts))...}; 202 } 203 }; 204 205 template<typename... Ts> 206 template<typename T> 207 constexpr T* SkZip<Ts...>::nullify; 208 209 template<typename... Ts> 210 inline constexpr auto SkMakeZip(Ts&& ... ts) { 211 return SkMakeZipDetail::MakeZip(std::forward<Ts>(ts)...); 212 } 213 #endif //SkZip_DEFINED 214