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 template<typename>
61 struct is_span : std::false_type {};
62 
63 template<typename T, size_t S>
64 struct is_span<span<T, S>> : std::true_type {};
65 
66 
67 template<typename>
68 struct is_std_array : std::false_type {};
69 
70 template<typename T, size_t N>
71 struct is_std_array<std::array<T, N>> : std::true_type {};
72 
73 
74 template<typename, typename = void>
75 struct has_size_and_data : std::false_type {};
76 
77 template<typename T>
79  std::void_t<decltype(std::size(std::declval<T>())),
80  decltype(std::data(std::declval<T>()))>>
81  : std::true_type {};
82 
83 
84 template<typename C, typename U = std::remove_cv_t<std::remove_reference_t<C>>>
86 {
87  static constexpr bool value = !is_span<U>::value &&
89  !std::is_array_v<U> &&
91 };
92 
93 
94 template<typename, typename, typename = void>
95 struct is_container_element_type_compatible : std::false_type {};
96 
97 template<typename T, typename E>
98 struct is_container_element_type_compatible<T, E, std::void_t<decltype(std::data(std::declval<T>()))>>
99  : std::is_convertible<std::remove_pointer_t<decltype(std::data(std::declval<T>()))> (*)[], E (*)[]>
100 {};
101 
102 
103 template<typename, typename = size_t>
104 struct is_complete : std::false_type {};
105 
106 template<typename T>
107 struct is_complete<T, decltype(sizeof(T))> : std::true_type {};
108 
109 
110 // 'calculate_byte_size' implementation (including comment) taken from:
111 // https://github.com/Microsoft/GSL/blob/master/include/gsl/span
112 // If we only supported compilers with good constexpr support then
113 // this pair of classes could collapse down to a constexpr function.
114 template<typename ElementType, size_t Extent>
116  : std::integral_constant<size_t, sizeof(ElementType) * Extent> {};
117 template<typename ElementType>
119  : std::integral_constant<size_t, dynamic_extent> {};
120 
121 } // namespace detail
122 
123 
124 template<typename ElementType, size_t Extent>
125 class span
126 {
127  static_assert(Extent == dynamic_extent || ptrdiff_t(Extent) >= 0,
128  "A span must have an extent greater than or equal to zero, "
129  "or a dynamic extent");
130  static_assert(std::is_object_v<ElementType>,
131  "A span's ElementType must be an object type (not a "
132  "reference type or void)");
134  "A span's ElementType must be a complete type (not a forward "
135  "declaration)");
136  static_assert(!std::is_abstract_v<ElementType>,
137  "A span's ElementType cannot be an abstract class type");
138 
139  using storage_type = detail::span_storage<ElementType, Extent>;
140 
141 public:
142  // constants and types
143  using element_type = ElementType;
144  using value_type = std::remove_cv_t<ElementType>;
145  using index_type = size_t;
146  using difference_type = ptrdiff_t;
147  using pointer = ElementType*;
148  using reference = ElementType&;
149  using iterator = pointer;
150  using const_iterator = const ElementType*;
151  using reverse_iterator = std::reverse_iterator<iterator>;
152  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
153 
154  static constexpr index_type extent = Extent;
155 
156  // [span.cons], span constructors, copy, assignment, and destructor
157  template<size_t E = Extent, std::enable_if_t<E <= 0, int> = 0>
158  constexpr span() noexcept
159  {
160  }
161 
162  constexpr span(pointer ptr, index_type count)
163  : storage(ptr, count)
164  {
165  assert(extent == dynamic_extent || count == extent);
166  }
167 
168  constexpr span(pointer first_elem, pointer last_elem)
169  : storage(first_elem, last_elem - first_elem)
170  {
171  assert(extent == dynamic_extent ||
172  static_cast<index_type>(last_elem - first_elem) == extent);
173  }
174 
175  template<size_t N,
176  size_t E = Extent,
177  std::enable_if_t<(E == dynamic_extent || N == E) &&
178  detail::is_container_element_type_compatible<element_type (&)[N],
179  ElementType>::value,
180  int> = 0>
181  constexpr span(element_type (&arr)[N]) noexcept
182  : storage(arr, N)
183  {
184  }
185 
186  template<size_t N,
187  size_t E = Extent,
188  std::enable_if_t<(E == dynamic_extent || N == E) &&
189  detail::is_container_element_type_compatible<std::array<value_type, N>&,
190  ElementType>::value,
191  int> = 0>
192  constexpr span(std::array<value_type, N>& arr) noexcept
193  : storage(arr.data(), N)
194  {
195  }
196 
197  template<size_t N,
198  size_t E = Extent,
199  std::enable_if_t<(E == dynamic_extent || N == E) &&
200  detail::is_container_element_type_compatible<const std::array<value_type, N>&,
201  ElementType>::value,
202  int> = 0>
203  constexpr span(const std::array<value_type, N>& arr) noexcept
204  : storage(arr.data(), N)
205  {
206  }
207 
208  template<typename Container,
209  std::enable_if_t<detail::is_container<Container>::value &&
211  int> = 0>
212  constexpr span(Container& cont)
213  : storage(std::data(cont), std::size(cont))
214  {
215  assert(extent == dynamic_extent || std::size(cont) == extent);
216  }
217 
218  template<typename Container,
219  std::enable_if_t<detail::is_container<Container>::value &&
221  int> = 0>
222  constexpr span(const Container& cont)
223  : storage(std::data(cont), std::size(cont))
224  {
225  assert(extent == dynamic_extent || std::size(cont) == extent);
226  }
227 
228  constexpr span(const span& other) noexcept = default;
229 
230  template<typename OtherElementType,
231  size_t OtherExtent,
232  std::enable_if_t<(Extent == OtherExtent || Extent == dynamic_extent) &&
233  std::is_convertible_v<OtherElementType (*)[], ElementType (*)[]>,
234  int> = 0>
235  constexpr span(const span<OtherElementType, OtherExtent>& other) noexcept
236  : storage(other.data(), other.size())
237  {
238  }
239 
240  ~span() noexcept = default;
241 
242  constexpr span& operator=(const span& other) noexcept = default;
243 
244  // [span.sub], span subviews
245  template<size_t Count>
246  [[nodiscard]] constexpr span<element_type, Count> first() const
247  {
248  assert(Count >= 0 && Count <= size());
249  return {data(), Count};
250  }
251 
252  template<size_t Count>
253  [[nodiscard]] constexpr span<element_type, Count> last() const
254  {
255  assert(Count >= 0 && Count <= size());
256  return {data() + (size() - Count), Count};
257  }
258 
259  template<ptrdiff_t Offset, size_t Count = dynamic_extent>
260  using subspan_return_t =
261  span<ElementType,
262  Count != dynamic_extent ? Count
263  : (Extent != dynamic_extent ? Extent - Offset : dynamic_extent)>;
264 
265  template<ptrdiff_t Offset, size_t Count = dynamic_extent>
266  [[nodiscard]] constexpr subspan_return_t<Offset, Count> subspan() const
267  {
268  assert((Offset >= 0 && Offset <= size()) &&
269  (Count == dynamic_extent || (Count >= 0 && Offset + Count <= size())));
270  return {data() + Offset,
271  Count != dynamic_extent ? Count
272  : (Extent != dynamic_extent ? Extent - Offset : size() - Offset)};
273  }
274 
275  [[nodiscard]] constexpr span<element_type, dynamic_extent> first(index_type count) const
276  {
277  assert(count >= 0 && count <= size());
278  return {data(), count};
279  }
280 
281  [[nodiscard]] constexpr span<element_type, dynamic_extent> last(index_type count) const
282  {
283  assert(count >= 0 && count <= size());
284  return {data() + (size() - count), count};
285  }
286 
287  [[nodiscard]] constexpr span<element_type, dynamic_extent> subspan(
288  index_type offset, index_type count = dynamic_extent) const
289  {
290  assert((offset >= 0 && offset <= size()) &&
291  (count == dynamic_extent || (count >= 0 && offset + count <= size())));
292  return {data() + offset, count == dynamic_extent ? size() - offset : count};
293  }
294 
295  // [span.obs], span observers
296  [[nodiscard]] constexpr index_type size() const noexcept { return storage.size; }
297 
298  [[nodiscard]] constexpr index_type size_bytes() const noexcept { return size() * sizeof(element_type); }
299 
300  [[nodiscard]] constexpr bool empty() const noexcept { return size() == 0; }
301 
302  // [span.elem], span element access
303  [[nodiscard]] constexpr reference operator[](index_type idx) const
304  {
305  assert(idx >= 0 && idx < size());
306  return *(data() + idx);
307  }
308 
309  // Extension: not in P0122
310  [[nodiscard]] constexpr reference front() const
311  {
312  assert(!empty());
313  return *data();
314  }
315 
316  // Extension: not in P0122
317  [[nodiscard]] constexpr reference back() const
318  {
319  assert(!empty());
320  return *(data() + (size() - 1));
321  }
322 
323  [[nodiscard]] constexpr pointer data() const noexcept { return storage.ptr; }
324 
325  // [span.iterators], span iterator support
326  [[nodiscard]] constexpr iterator begin() const noexcept { return data(); }
327  [[nodiscard]] constexpr iterator end() const noexcept { return data() + size(); }
328  [[nodiscard]] constexpr const_iterator cbegin() const noexcept { return begin(); }
329  [[nodiscard]] constexpr const_iterator cend() const noexcept { return end(); }
330 
331  [[nodiscard]] constexpr auto rbegin() const noexcept { return reverse_iterator(end()); }
332  [[nodiscard]] constexpr auto rend() const noexcept { return reverse_iterator(begin()); }
333  [[nodiscard]] constexpr auto crbegin() const noexcept { return const_reverse_iterator(cend()); }
334  [[nodiscard]] constexpr auto crend() const noexcept { return const_reverse_iterator(cbegin()); }
335 
336 private:
337  storage_type storage;
338 };
339 
340 template<typename ElementType, size_t Extent>
343 {
344  return {reinterpret_cast<const uint8_t*>(s.data()), s.size_bytes()};
345 }
346 
347 template<typename ElementType,
348  size_t Extent,
349  std::enable_if_t<!std::is_const_v<ElementType>, int> = 0>
352 {
353  return {reinterpret_cast<uint8_t*>(s.data()), s.size_bytes()};
354 }
355 
356 #endif
std::reverse_iterator< const_iterator > const_reverse_iterator
Definition: span.hh:152
std::remove_cv_t< const uint8_t > value_type
Definition: span.hh:144
constexpr span_storage(E *ptr_, size_t) noexcept
Definition: span.hh:43
const uint8_t & reference
Definition: span.hh:148
Definition: span.hh:34
pointer iterator
Definition: span.hh:149
Definition: stl_test.cc:7
STL namespace.
constexpr span_storage() noexcept=default
size_t size(std::string_view utf8)
Definition: join.hh:10
ptrdiff_t difference_type
Definition: span.hh:146
span< const uint8_t, detail::calculate_byte_size< ElementType, Extent >::value > as_bytes(span< ElementType, Extent > s) noexcept
Definition: span.hh:342
constexpr span_storage(E *ptr_, size_t size_) noexcept
Definition: span.hh:53
const uint8_t element_type
Definition: span.hh:143
ALWAYS_INLINE unsigned count(const uint8_t *pIn, const uint8_t *pMatch, const uint8_t *pInLimit)
Definition: lz4.cc:207
constexpr size_t dynamic_extent
Definition: span.hh:31
std::reverse_iterator< iterator > reverse_iterator
Definition: span.hh:151
span< uint8_t, detail::calculate_byte_size< ElementType, Extent >::value > as_writable_bytes(span< ElementType, Extent > s) noexcept
Definition: span.hh:351
static constexpr size_t size
Definition: span.hh:46
constexpr unsigned N
Definition: ResampleHQ.cc:224
const const uint8_t * const_iterator
Definition: span.hh:150
const uint8_t * pointer
Definition: span.hh:147