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/SkTypes.h" |
17 | #include "include/private/SkTemplates.h" |
18 | #include "include/private/SkTo.h" |
19 | #include "src/core/SkSpan.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; |
34 | constexpr Iterator(const SkZip* zip, size_t index) : fZip{zip}, fIndex{index} { } |
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: |
54 | constexpr SkZip() : fPointers{nullify<Ts>...}, fSize{0} {} |
55 | constexpr SkZip(size_t) = delete; |
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>> |
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);} |
74 | constexpr size_t size() const { return fSize; } |
75 | constexpr bool empty() const { return this->size() == 0; } |
76 | constexpr ReturnTuple front() const { return this->index(0); } |
77 | constexpr ReturnTuple back() const { return this->index(this->size() - 1); } |
78 | constexpr Iterator begin() const { return Iterator{this, 0}; } |
79 | constexpr Iterator end() const { return Iterator{this, this->size()}; } |
80 | template<size_t I> constexpr auto get() const { |
81 | return SkMakeSpan(std::get<I>(fPointers), fSize); |
82 | } |
83 | constexpr std::tuple<Ts*...> data() const { return fPointers; } |
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 | } |
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 | } |
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: |
102 | constexpr SkZip(size_t n, const std::tuple<Ts*...>& pointers) |
103 | : fPointers{pointers} |
104 | , fSize{n} {} |
105 | |
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> |
113 | constexpr ReturnTuple indexDetail(size_t i, std::index_sequence<Is...>) const { |
114 | return ReturnTuple((std::get<Is>(fPointers))[i]...); |
115 | } |
116 | |
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> |
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 | |