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