openMSX
span.hh
Go to the documentation of this file.
1 // This implementation of 'span' is heavily based on
2 // https://github.com/tcbrindle/span
3 //
4 // I only simplified / stripped it down a bit:
5 // - Most extensions (compared to the std::span proposal) are removed.
6 // - Behavior on pre-condition violation is no longer configurable, this
7 // implementation simply uses assert().
8 // - I dropped pre-C++14 support.
9 //
10 // Original copyright notice:
11 //
12 // This is an implementation of std::span from P0122R7
13 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0122r7.pdf
14 //
15 // Copyright Tristan Brindle 2018.
16 // Distributed under the Boost Software License, Version 1.0.
17 // (See accompanying file ../../LICENSE_1_0.txt or copy at
18 // https://www.boost.org/LICENSE_1_0.txt)
19 
20 #ifndef SPAN_HH
21 #define SPAN_HH
22 
23 #include <algorithm>
24 #include <array>
25 #include <cassert>
26 #include <cstddef>
27 #include <cstdint>
28 #include <type_traits>
29 
30 
31 constexpr size_t dynamic_extent = size_t(-1);
32 
33 template<typename ElementType, size_t Extent = dynamic_extent>
34 class span;
35 
36 
37 namespace detail {
38 
39 template<typename E, size_t S>
41 {
42  constexpr span_storage() noexcept = default;
43  constexpr span_storage(E* ptr_, size_t /*unused*/) noexcept : ptr(ptr_) {}
44 
45  E* ptr = nullptr;
46  static constexpr size_t size = S;
47 };
48 
49 template<typename E>
51 {
52  constexpr span_storage() noexcept = default;
53  constexpr span_storage(E* ptr_, size_t size_) noexcept : ptr(ptr_), size(size_) {}
54 
55  E* ptr = nullptr;
56  size_t size = 0;
57 };
58 
59 
60 // Reimplementation of C++17 std::size() and std::data()
61 template<typename C>
62 constexpr auto size(const C& c) -> decltype(c.size()) { return c.size(); }
63 
64 template<typename T, size_t N>
65 constexpr auto size(const T (&)[N]) noexcept { return N; }
66 
67 
68 template<typename C>
69 constexpr auto data(C& c) -> decltype(c.data()) { return c.data(); }
70 
71 template<typename C>
72 constexpr auto data(const C& c) -> decltype(c.data()) { return c.data(); }
73 
74 template<typename T, size_t N>
75 constexpr T* data(T (&array)[N]) noexcept { return array; }
76 
77 template<typename E>
78 constexpr const E* data(std::initializer_list<E> il) noexcept { return il.begin(); }
79 
80 
81 // Reimplementation of C++17 std::void_t
82 template<typename...>
83 using void_t = void;
84 
85 
86 template<typename>
87 struct is_span : std::false_type {};
88 
89 template<typename T, size_t S>
90 struct is_span<span<T, S>> : std::true_type {};
91 
92 
93 template<typename>
94 struct is_std_array : std::false_type {};
95 
96 template<typename T, size_t N>
97 struct is_std_array<std::array<T, N>> : std::true_type {};
98 
99 
100 template<typename, typename = void>
101 struct has_size_and_data : std::false_type {};
102 
103 template<typename T>
105  void_t<decltype(detail::size(std::declval<T>())),
106  decltype(detail::data(std::declval<T>()))>>
107  : std::true_type {};
108 
109 
110 template<typename C, typename U = std::remove_cv_t<std::remove_reference_t<C>>>
112 {
113  static constexpr bool value = !is_span<U>::value &&
115  !std::is_array<U>::value &&
117 };
118 
119 
120 template<typename, typename, typename = void>
121 struct is_container_element_type_compatible : std::false_type {};
122 
123 template<typename T, typename E>
124 struct is_container_element_type_compatible<T, E, void_t<decltype(detail::data(std::declval<T>()))>>
125  : std::is_convertible<std::remove_pointer_t<decltype(detail::data(std::declval<T>()))> (*)[], E (*)[]>
126 {};
127 
128 
129 template<typename, typename = size_t>
130 struct is_complete : std::false_type {};
131 
132 template<typename T>
133 struct is_complete<T, decltype(sizeof(T))> : std::true_type {};
134 
135 
136 // 'calculate_byte_size' implementation (including comment) taken from:
137 // https://github.com/Microsoft/GSL/blob/master/include/gsl/span
138 // If we only supported compilers with good constexpr support then
139 // this pair of classes could collapse down to a constexpr function.
140 template<typename ElementType, size_t Extent>
142  : std::integral_constant<size_t, sizeof(ElementType) * Extent> {};
143 template<typename ElementType>
145  : std::integral_constant<size_t, dynamic_extent> {};
146 
147 } // namespace detail
148 
149 
150 template<typename ElementType, size_t Extent>
151 class span
152 {
153  static_assert(Extent == dynamic_extent || ptrdiff_t(Extent) >= 0,
154  "A span must have an extent greater than or equal to zero, "
155  "or a dynamic extent");
156  static_assert(std::is_object<ElementType>::value,
157  "A span's ElementType must be an object type (not a "
158  "reference type or void)");
160  "A span's ElementType must be a complete type (not a forward "
161  "declaration)");
162  static_assert(!std::is_abstract<ElementType>::value,
163  "A span's ElementType cannot be an abstract class type");
164 
165  using storage_type = detail::span_storage<ElementType, Extent>;
166 
167 public:
168  // constants and types
169  using element_type = ElementType;
170  using value_type = std::remove_cv_t<ElementType>;
171  using index_type = size_t;
172  using difference_type = ptrdiff_t;
173  using pointer = ElementType*;
174  using reference = ElementType&;
175  using iterator = pointer;
176  using const_iterator = const ElementType*;
177  using reverse_iterator = std::reverse_iterator<iterator>;
178  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
179 
180  static constexpr index_type extent = Extent;
181 
182  // [span.cons], span constructors, copy, assignment, and destructor
183  template<size_t E = Extent, std::enable_if_t<E <= 0, int> = 0>
184  constexpr span() noexcept
185  {
186  }
187 
188  constexpr span(pointer ptr, index_type count)
189  : storage(ptr, count)
190  {
191  assert(extent == dynamic_extent || count == extent);
192  }
193 
194  constexpr span(pointer first_elem, pointer last_elem)
195  : storage(first_elem, last_elem - first_elem)
196  {
197  assert(extent == dynamic_extent ||
198  static_cast<index_type>(last_elem - first_elem) == extent);
199  }
200 
201  template<size_t N,
202  size_t E = Extent,
203  std::enable_if_t<(E == dynamic_extent || N == E) &&
204  detail::is_container_element_type_compatible<element_type (&)[N],
205  ElementType>::value,
206  int> = 0>
207  constexpr span(element_type (&arr)[N]) noexcept
208  : storage(arr, N)
209  {
210  }
211 
212  template<size_t N,
213  size_t E = Extent,
214  std::enable_if_t<(E == dynamic_extent || N == E) &&
215  detail::is_container_element_type_compatible<std::array<value_type, N>&,
216  ElementType>::value,
217  int> = 0>
218  /*constexpr*/ span(std::array<value_type, N>& arr) noexcept
219  : storage(arr.data(), N)
220  {
221  }
222 
223  template<size_t N,
224  size_t E = Extent,
225  std::enable_if_t<(E == dynamic_extent || N == E) &&
226  detail::is_container_element_type_compatible<const std::array<value_type, N>&,
227  ElementType>::value,
228  int> = 0>
229  /*constexpr*/ span(const std::array<value_type, N>& arr) noexcept
230  : storage(arr.data(), N)
231  {
232  }
233 
234  template<typename Container,
235  std::enable_if_t<detail::is_container<Container>::value &&
237  int> = 0>
238  constexpr span(Container& cont)
239  : storage(detail::data(cont), detail::size(cont))
240  {
241  assert(extent == dynamic_extent || detail::size(cont) == extent);
242  }
243 
244  template<typename Container,
245  std::enable_if_t<detail::is_container<Container>::value &&
247  int> = 0>
248  constexpr span(const Container& cont)
249  : storage(detail::data(cont), detail::size(cont))
250  {
251  assert(extent == dynamic_extent || detail::size(cont) == extent);
252  }
253 
254  constexpr span(const span& other) noexcept = default;
255 
256  template<typename OtherElementType,
257  size_t OtherExtent,
258  std::enable_if_t<(Extent == OtherExtent || Extent == dynamic_extent) &&
259  std::is_convertible<OtherElementType (*)[], ElementType (*)[]>::value,
260  int> = 0>
261  constexpr span(const span<OtherElementType, OtherExtent>& other) noexcept
262  : storage(other.data(), other.size())
263  {
264  }
265 
266  ~span() noexcept = default;
267 
268  constexpr span& operator=(const span& other) noexcept = default;
269 
270  // [span.sub], span subviews
271  template<size_t Count>
272  constexpr span<element_type, Count> first() const
273  {
274  assert(Count >= 0 && Count <= size());
275  return {data(), Count};
276  }
277 
278  template<size_t Count>
279  constexpr span<element_type, Count> last() const
280  {
281  assert(Count >= 0 && Count <= size());
282  return {data() + (size() - Count), Count};
283  }
284 
285  template<ptrdiff_t Offset, size_t Count = dynamic_extent>
286  using subspan_return_t =
287  span<ElementType,
288  Count != dynamic_extent ? Count
289  : (Extent != dynamic_extent ? Extent - Offset : dynamic_extent)>;
290 
291  template<ptrdiff_t Offset, size_t Count = dynamic_extent>
292  constexpr subspan_return_t<Offset, Count> subspan() const
293  {
294  assert((Offset >= 0 && Offset <= size()) &&
295  (Count == dynamic_extent || (Count >= 0 && Offset + Count <= size())));
296  return {data() + Offset,
297  Count != dynamic_extent ? Count
298  : (Extent != dynamic_extent ? Extent - Offset : size() - Offset)};
299  }
300 
302  {
303  assert(count >= 0 && count <= size());
304  return {data(), count};
305  }
306 
307  constexpr span<element_type, dynamic_extent> last(index_type count) const
308  {
309  assert(count >= 0 && count <= size());
310  return {data() + (size() - count), count};
311  }
312 
313  constexpr span<element_type, dynamic_extent> subspan(index_type offset,
314  index_type count = dynamic_extent) const
315  {
316  assert((offset >= 0 && offset <= size()) &&
317  (count == dynamic_extent || (count >= 0 && offset + count <= size())));
318  return {data() + offset, count == dynamic_extent ? size() - offset : count};
319  }
320 
321  // [span.obs], span observers
322  constexpr index_type size() const noexcept { return storage.size; }
323 
324  constexpr index_type size_bytes() const noexcept { return size() * sizeof(element_type); }
325 
326  constexpr bool empty() const noexcept { return size() == 0; }
327 
328  // [span.elem], span element access
329  constexpr reference operator[](index_type idx) const
330  {
331  assert(idx >= 0 && idx < size());
332  return *(data() + idx);
333  }
334 
335  // Extension: not in P0122
336  constexpr reference front() const
337  {
338  assert(!empty());
339  return *data();
340  }
341 
342  // Extension: not in P0122
343  constexpr reference back() const
344  {
345  assert(!empty());
346  return *(data() + (size() - 1));
347  }
348 
349  constexpr pointer data() const noexcept { return storage.ptr; }
350 
351  // [span.iterators], span iterator support
352  constexpr iterator begin() const noexcept { return data(); }
353  constexpr iterator end() const noexcept { return data() + size(); }
354  constexpr const_iterator cbegin() const noexcept { return begin(); }
355  constexpr const_iterator cend() const noexcept { return end(); }
356 
357  /*constexpr*/ auto rbegin() const noexcept { return reverse_iterator(end()); }
358  /*constexpr*/ auto rend() const noexcept { return reverse_iterator(begin()); }
359  /*constexpr*/ auto crbegin() const noexcept { return const_reverse_iterator(cend()); }
360  /*constexpr*/ auto crend() const noexcept { return const_reverse_iterator(cbegin()); }
361 
362 private:
363  storage_type storage;
364 };
365 
366 template<typename ElementType, size_t Extent>
369 {
370  return {reinterpret_cast<const uint8_t*>(s.data()), s.size_bytes()};
371 }
372 
373 template<typename ElementType,
374  size_t Extent,
375  std::enable_if_t<!std::is_const<ElementType>::value, int> = 0>
378 {
379  return {reinterpret_cast<uint8_t*>(s.data()), s.size_bytes()};
380 }
381 
382 #endif
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: span.hh:178
std::remove_cv_t< ElementType > value_type
Definition: span.hh:170
constexpr span_storage(E *ptr_, size_t) noexcept
Definition: span.hh:43
void void_t
Definition: span.hh:83
ElementType & reference
Definition: span.hh:174
Definition: span.hh:34
pointer iterator
Definition: span.hh:175
Definition: stl_test.cc:7
STL namespace.
constexpr span_storage() noexcept=default
auto begin(const string_view &x)
Definition: string_view.hh:151
constexpr auto data(C &c) -> decltype(c.data())
Definition: span.hh:69
Definition: span.hh:37
ptrdiff_t difference_type
Definition: span.hh:172
span< const uint8_t, detail::calculate_byte_size< ElementType, Extent >::value > as_bytes(span< ElementType, Extent > s) noexcept
Definition: span.hh:368
constexpr span_storage(E *ptr_, size_t size_) noexcept
Definition: span.hh:53
ElementType element_type
Definition: span.hh:169
constexpr size_t dynamic_extent
Definition: span.hh:31
auto count(InputRange &&range, const T &value)
Definition: ranges.hh:197
std::reverse_iterator< iterator > reverse_iterator
Definition: span.hh:177
span< uint8_t, detail::calculate_byte_size< ElementType, Extent >::value > as_writable_bytes(span< ElementType, Extent > s) noexcept
Definition: span.hh:377
size_t index_type
Definition: span.hh:171
static constexpr size_t size
Definition: span.hh:46
const ElementType * const_iterator
Definition: span.hh:176
constexpr auto size(const C &c) -> decltype(c.size())
Definition: span.hh:62
ElementType * pointer
Definition: span.hh:173
auto end(const string_view &x)
Definition: string_view.hh:152