• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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