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 inline 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 constexpr SkZip& operator=(const SkZip &that) = default; 61 62 // Check to see if U can be used for const T or is the same as T 63 template <typename U, typename T> 64 using CanConvertToConst = typename std::integral_constant<bool, 65 std::is_convertible<U*, T*>::value && sizeof(U) == sizeof(T)>::type; 66 67 // Allow SkZip<const T> to be constructed from SkZip<T>. 68 template<typename... Us, 69 typename = std::enable_if<skstd::conjunction<CanConvertToConst<Us, Ts>...>::value>> SkZip(const SkZip<Us...> & that)70 constexpr SkZip(const SkZip<Us...>& that) 71 : fPointers(that.data()) 72 , fSize{that.size()} { } 73 74 constexpr ReturnTuple operator[](size_t i) const { return this->index(i);} size()75 constexpr size_t size() const { return fSize; } empty()76 constexpr bool empty() const { return this->size() == 0; } front()77 constexpr ReturnTuple front() const { return this->index(0); } back()78 constexpr ReturnTuple back() const { return this->index(this->size() - 1); } begin()79 constexpr Iterator begin() const { return Iterator{this, 0}; } end()80 constexpr Iterator end() const { return Iterator{this, this->size()}; } get()81 template<size_t I> constexpr auto get() const { 82 return SkMakeSpan(std::get<I>(fPointers), fSize); 83 } data()84 constexpr std::tuple<Ts*...> data() const { return fPointers; } first(size_t n)85 constexpr SkZip first(size_t n) const { 86 SkASSERT(n <= this->size()); 87 if (n == 0) { return SkZip(); } 88 return SkZip{n, fPointers}; 89 } last(size_t n)90 constexpr SkZip last(size_t n) const { 91 SkASSERT(n <= this->size()); 92 if (n == 0) { return SkZip(); } 93 return SkZip{n, this->pointersAt(fSize - n)}; 94 } subspan(size_t offset,size_t count)95 constexpr SkZip subspan(size_t offset, size_t count) const { 96 SkASSERT(offset < this->size()); 97 SkASSERT(count <= this->size() - offset); 98 if (count == 0) { return SkZip(); } 99 return SkZip(count, pointersAt(offset)); 100 } 101 102 private: SkZip(size_t n,const std::tuple<Ts * ...> & pointers)103 constexpr SkZip(size_t n, const std::tuple<Ts*...>& pointers) 104 : fPointers{pointers} 105 , fSize{n} {} 106 index(size_t i)107 constexpr ReturnTuple index(size_t i) const { 108 SkASSERT(this->size() > 0); 109 SkASSERT(i < this->size()); 110 return indexDetail(i, std::make_index_sequence<sizeof...(Ts)>{}); 111 } 112 113 template<std::size_t... Is> indexDetail(size_t i,std::index_sequence<Is...>)114 constexpr ReturnTuple indexDetail(size_t i, std::index_sequence<Is...>) const { 115 return ReturnTuple((std::get<Is>(fPointers))[i]...); 116 } 117 pointersAt(size_t i)118 std::tuple<Ts*...> pointersAt(size_t i) const { 119 SkASSERT(this->size() > 0); 120 SkASSERT(i < this->size()); 121 return pointersAtDetail(i, std::make_index_sequence<sizeof...(Ts)>{}); 122 } 123 124 template<std::size_t... Is> pointersAtDetail(size_t i,std::index_sequence<Is...>)125 constexpr std::tuple<Ts*...> pointersAtDetail(size_t i, std::index_sequence<Is...>) const { 126 return std::tuple<Ts*...>{&(std::get<Is>(fPointers))[i]...}; 127 } 128 129 std::tuple<Ts*...> fPointers; 130 size_t fSize; 131 }; 132 133 class SkMakeZipDetail { 134 template<typename T> struct DecayPointer{ 135 using U = typename std::remove_cv<typename std::remove_reference<T>::type>::type; 136 using type = typename std::conditional<std::is_pointer<U>::value, U, T>::type; 137 }; 138 template<typename T> using DecayPointerT = typename DecayPointer<T>::type; 139 140 template<typename C> struct ContiguousMemory { }; 141 template<typename T> struct ContiguousMemory<T*> { 142 using value_type = T; 143 static constexpr value_type* Data(T* t) { return t; } 144 static constexpr size_t Size(T* s) { return SIZE_MAX; } 145 }; 146 template<typename T, size_t N> struct ContiguousMemory<T(&)[N]> { 147 using value_type = T; 148 static constexpr value_type* Data(T(&t)[N]) { return t; } 149 static constexpr size_t Size(T(&)[N]) { return N; } 150 }; 151 // In general, we don't want r-value collections, but SkSpans are ok, because they are a view 152 // onto an actual container. 153 template<typename T> struct ContiguousMemory<SkSpan<T>> { 154 using value_type = T; 155 static constexpr value_type* Data(SkSpan<T> s) { return s.data(); } 156 static constexpr size_t Size(SkSpan<T> s) { return s.size(); } 157 }; 158 // Only accept l-value references to collections. 159 template<typename C> struct ContiguousMemory<C&> { 160 using value_type = typename std::remove_pointer<decltype(std::declval<C>().data())>::type; 161 static constexpr value_type* Data(C& c) { return c.data(); } 162 static constexpr size_t Size(C& c) { return c.size(); } 163 }; 164 template<typename C> using Span = ContiguousMemory<DecayPointerT<C>>; 165 template<typename C> using ValueType = typename Span<C>::value_type; 166 167 template<typename C, typename... Ts> struct PickOneSize { }; 168 template <typename T, typename... Ts> struct PickOneSize<T*, Ts...> { 169 static constexpr size_t Size(T* t, Ts... ts) { 170 return PickOneSize<Ts...>::Size(std::forward<Ts>(ts)...); 171 } 172 }; 173 template <typename T, typename... Ts, size_t N> struct PickOneSize<T(&)[N], Ts...> { 174 static constexpr size_t Size(T(&)[N], Ts...) { return N; } 175 }; 176 template<typename T, typename... Ts> struct PickOneSize<SkSpan<T>, Ts...> { 177 static constexpr size_t Size(SkSpan<T> s, Ts...) { return s.size(); } 178 }; 179 template<typename C, typename... Ts> struct PickOneSize<C&, Ts...> { 180 static constexpr size_t Size(C& c, Ts...) { return c.size(); } 181 }; 182 183 public: 184 template<typename... Ts> 185 static constexpr auto MakeZip(Ts&& ... ts) { 186 187 // Pick the first collection that has a size, and use that for the size. 188 size_t size = PickOneSize<DecayPointerT<Ts>...>::Size(std::forward<Ts>(ts)...); 189 190 #ifdef SK_DEBUG 191 // Check that all sizes are the same. 192 size_t minSize = SIZE_MAX; 193 size_t maxSize = 0; 194 for (size_t s : {Span<Ts>::Size(std::forward<Ts>(ts))...}) { 195 if (s != SIZE_MAX) { 196 minSize = std::min(minSize, s); 197 maxSize = std::max(maxSize, s); 198 } 199 } 200 SkASSERT(minSize == maxSize); 201 #endif 202 203 return SkZip<ValueType<Ts>...>{size, Span<Ts>::Data(std::forward<Ts>(ts))...}; 204 } 205 }; 206 207 template<typename... Ts> 208 inline constexpr auto SkMakeZip(Ts&& ... ts) { 209 return SkMakeZipDetail::MakeZip(std::forward<Ts>(ts)...); 210 } 211 #endif //SkZip_DEFINED 212