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