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