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