1
2 /*
3 This is an implementation of C++20's std::span
4 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/n4820.pdf
5 */
6
7 // Copyright Tristan Brindle 2018.
8 // Distributed under the Boost Software License, Version 1.0.
9 // (See accompanying file ../../LICENSE_1_0.txt or copy at
10 // https://www.boost.org/LICENSE_1_0.txt)
11
12 #ifndef TCB_SPAN_HPP_INCLUDED
13 #define TCB_SPAN_HPP_INCLUDED
14
15 #include <array>
16 #include <cstddef>
17 #include <cstdint>
18 #include <type_traits>
19
20 #ifndef TCB_SPAN_NO_EXCEPTIONS
21 // Attempt to discover whether we're being compiled with exception support
22 #if !(defined(__cpp_exceptions) || defined(__EXCEPTIONS) || defined(_CPPUNWIND))
23 #define TCB_SPAN_NO_EXCEPTIONS
24 #endif
25 #endif
26
27 #ifndef TCB_SPAN_NO_EXCEPTIONS
28 #include <cstdio>
29 #include <stdexcept>
30 #endif
31
32 // Various feature test macros
33
34 #ifndef TCB_SPAN_NAMESPACE_NAME
35 #define TCB_SPAN_NAMESPACE_NAME tcb
36 #endif
37
38 #if __cplusplus >= 201703L || (defined(_MSVC_LANG) && _MSVC_LANG >= 201703L)
39 #define TCB_SPAN_HAVE_CPP17
40 #endif
41
42 #if __cplusplus >= 201402L || (defined(_MSVC_LANG) && _MSVC_LANG >= 201402L)
43 #define TCB_SPAN_HAVE_CPP14
44 #endif
45
46 namespace TCB_SPAN_NAMESPACE_NAME {
47
48 // Establish default contract checking behavior
49 #if !defined(TCB_SPAN_THROW_ON_CONTRACT_VIOLATION) && \
50 !defined(TCB_SPAN_TERMINATE_ON_CONTRACT_VIOLATION) && \
51 !defined(TCB_SPAN_NO_CONTRACT_CHECKING)
52 #if defined(NDEBUG) || !defined(TCB_SPAN_HAVE_CPP14)
53 #define TCB_SPAN_NO_CONTRACT_CHECKING
54 #else
55 #define TCB_SPAN_TERMINATE_ON_CONTRACT_VIOLATION
56 #endif
57 #endif
58
59 #if defined(TCB_SPAN_THROW_ON_CONTRACT_VIOLATION)
60 struct contract_violation_error : std::logic_error {
contract_violation_errorTCB_SPAN_NAMESPACE_NAME::contract_violation_error61 explicit contract_violation_error(const char* msg) : std::logic_error(msg)
62 {}
63 };
64
contract_violation(const char * msg)65 inline void contract_violation(const char* msg)
66 {
67 throw contract_violation_error(msg);
68 }
69
70 #elif defined(TCB_SPAN_TERMINATE_ON_CONTRACT_VIOLATION)
71 [[noreturn]] inline void contract_violation(const char* /*unused*/)
72 {
73 std::terminate();
74 }
75 #endif
76
77 #if !defined(TCB_SPAN_NO_CONTRACT_CHECKING)
78 #define TCB_SPAN_STRINGIFY(cond) #cond
79 #define TCB_SPAN_EXPECT(cond) \
80 cond ? (void) 0 : contract_violation("Expected " TCB_SPAN_STRINGIFY(cond))
81 #else
82 #define TCB_SPAN_EXPECT(cond)
83 #endif
84
85 #if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_inline_variables)
86 #define TCB_SPAN_INLINE_VAR inline
87 #else
88 #define TCB_SPAN_INLINE_VAR
89 #endif
90
91 #if defined(TCB_SPAN_HAVE_CPP14) || \
92 (defined(__cpp_constexpr) && __cpp_constexpr >= 201304)
93 #define TCB_SPAN_HAVE_CPP14_CONSTEXPR
94 #endif
95
96 #if defined(TCB_SPAN_HAVE_CPP14_CONSTEXPR)
97 #define TCB_SPAN_CONSTEXPR14 constexpr
98 #else
99 #define TCB_SPAN_CONSTEXPR14
100 #endif
101
102 #if defined(TCB_SPAN_HAVE_CPP14_CONSTEXPR) && \
103 (!defined(_MSC_VER) || _MSC_VER > 1900)
104 #define TCB_SPAN_CONSTEXPR_ASSIGN constexpr
105 #else
106 #define TCB_SPAN_CONSTEXPR_ASSIGN
107 #endif
108
109 #if defined(TCB_SPAN_NO_CONTRACT_CHECKING)
110 #define TCB_SPAN_CONSTEXPR11 constexpr
111 #else
112 #define TCB_SPAN_CONSTEXPR11 TCB_SPAN_CONSTEXPR14
113 #endif
114
115 #if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_deduction_guides)
116 #define TCB_SPAN_HAVE_DEDUCTION_GUIDES
117 #endif
118
119 #if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_lib_byte)
120 #define TCB_SPAN_HAVE_STD_BYTE
121 #endif
122
123 #if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_lib_array_constexpr)
124 #define TCB_SPAN_HAVE_CONSTEXPR_STD_ARRAY_ETC
125 #endif
126
127 #if defined(TCB_SPAN_HAVE_CONSTEXPR_STD_ARRAY_ETC)
128 #define TCB_SPAN_ARRAY_CONSTEXPR constexpr
129 #else
130 #define TCB_SPAN_ARRAY_CONSTEXPR
131 #endif
132
133 #ifdef TCB_SPAN_HAVE_STD_BYTE
134 using byte = std::byte;
135 #else
136 using byte = unsigned char;
137 #endif
138
139 #if defined(TCB_SPAN_HAVE_CPP17)
140 #define TCB_SPAN_NODISCARD [[nodiscard]]
141 #else
142 #define TCB_SPAN_NODISCARD
143 #endif
144
145 TCB_SPAN_INLINE_VAR constexpr std::size_t dynamic_extent = SIZE_MAX;
146
147 template <typename ElementType, std::size_t Extent = dynamic_extent>
148 class span;
149
150 namespace detail {
151
152 template <typename E, std::size_t S>
153 struct span_storage {
154 constexpr span_storage() noexcept = default;
155
span_storageTCB_SPAN_NAMESPACE_NAME::detail::span_storage156 constexpr span_storage(E* p_ptr, std::size_t /*unused*/) noexcept
157 : ptr(p_ptr)
158 {}
159
160 E* ptr = nullptr;
161 static constexpr std::size_t size = S;
162 };
163
164 template <typename E>
165 struct span_storage<E, dynamic_extent> {
166 constexpr span_storage() noexcept = default;
167
span_storageTCB_SPAN_NAMESPACE_NAME::detail::span_storage168 constexpr span_storage(E* p_ptr, std::size_t p_size) noexcept
169 : ptr(p_ptr), size(p_size)
170 {}
171
172 E* ptr = nullptr;
173 std::size_t size = 0;
174 };
175
176 // Reimplementation of C++17 std::size() and std::data()
177 #if defined(TCB_SPAN_HAVE_CPP17) || \
178 defined(__cpp_lib_nonmember_container_access)
179 using std::data;
180 using std::size;
181 #else
182 template <class C>
size(const C & c)183 constexpr auto size(const C& c) -> decltype(c.size())
184 {
185 return c.size();
186 }
187
188 template <class T, std::size_t N>
size(const T (&)[N])189 constexpr std::size_t size(const T (&)[N]) noexcept
190 {
191 return N;
192 }
193
194 template <class C>
data(C & c)195 constexpr auto data(C& c) -> decltype(c.data())
196 {
197 return c.data();
198 }
199
200 template <class C>
data(const C & c)201 constexpr auto data(const C& c) -> decltype(c.data())
202 {
203 return c.data();
204 }
205
206 template <class T, std::size_t N>
data(T (& array)[N])207 constexpr T* data(T (&array)[N]) noexcept
208 {
209 return array;
210 }
211
212 template <class E>
data(std::initializer_list<E> il)213 constexpr const E* data(std::initializer_list<E> il) noexcept
214 {
215 return il.begin();
216 }
217 #endif // TCB_SPAN_HAVE_CPP17
218
219 #if defined(TCB_SPAN_HAVE_CPP17) || defined(__cpp_lib_void_t)
220 using std::void_t;
221 #else
222 template <typename...>
223 using void_t = void;
224 #endif
225
226 template <typename T>
227 using uncvref_t =
228 typename std::remove_cv<typename std::remove_reference<T>::type>::type;
229
230 template <typename>
231 struct is_span : std::false_type {};
232
233 template <typename T, std::size_t S>
234 struct is_span<span<T, S>> : std::true_type {};
235
236 template <typename>
237 struct is_std_array : std::false_type {};
238
239 template <typename T, std::size_t N>
240 struct is_std_array<std::array<T, N>> : std::true_type {};
241
242 template <typename, typename = void>
243 struct has_size_and_data : std::false_type {};
244
245 template <typename T>
246 struct has_size_and_data<T, void_t<decltype(detail::size(std::declval<T>())),
247 decltype(detail::data(std::declval<T>()))>>
248 : std::true_type {};
249
250 template <typename C, typename U = uncvref_t<C>>
251 struct is_container {
252 static constexpr bool value =
253 !is_span<U>::value && !is_std_array<U>::value &&
254 !std::is_array<U>::value && has_size_and_data<C>::value;
255 };
256
257 template <typename T>
258 using remove_pointer_t = typename std::remove_pointer<T>::type;
259
260 template <typename, typename, typename = void>
261 struct is_container_element_type_compatible : std::false_type {};
262
263 template <typename T, typename E>
264 struct is_container_element_type_compatible<
265 T, E,
266 typename std::enable_if<
267 !std::is_same<typename std::remove_cv<decltype(
268 detail::data(std::declval<T>()))>::type,
269 void>::value>::type>
270 : std::is_convertible<
271 remove_pointer_t<decltype(detail::data(std::declval<T>()))> (*)[],
272 E (*)[]> {};
273
274 template <typename, typename = size_t>
275 struct is_complete : std::false_type {};
276
277 template <typename T>
278 struct is_complete<T, decltype(sizeof(T))> : std::true_type {};
279
280 } // namespace detail
281
282 template <typename ElementType, std::size_t Extent>
283 class span {
284 static_assert(std::is_object<ElementType>::value,
285 "A span's ElementType must be an object type (not a "
286 "reference type or void)");
287 static_assert(detail::is_complete<ElementType>::value,
288 "A span's ElementType must be a complete type (not a forward "
289 "declaration)");
290 static_assert(!std::is_abstract<ElementType>::value,
291 "A span's ElementType cannot be an abstract class type");
292
293 using storage_type = detail::span_storage<ElementType, Extent>;
294
295 public:
296 // constants and types
297 using element_type = ElementType;
298 using value_type = typename std::remove_cv<ElementType>::type;
299 using size_type = std::size_t;
300 using difference_type = std::ptrdiff_t;
301 using pointer = element_type*;
302 using const_pointer = const element_type*;
303 using reference = element_type&;
304 using iterator = pointer;
305 using const_iterator = const_pointer;
306 using reverse_iterator = std::reverse_iterator<iterator>;
307 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
308
309 static constexpr size_type extent = Extent;
310
311 // [span.cons], span constructors, copy, assignment, and destructor
312 template <
313 std::size_t E = Extent,
314 typename std::enable_if<(E == dynamic_extent || E <= 0), int>::type = 0>
span()315 constexpr span() noexcept
316 {}
317
span(pointer ptr,size_type count)318 TCB_SPAN_CONSTEXPR11 span(pointer ptr, size_type count)
319 : storage_(ptr, count)
320 {
321 TCB_SPAN_EXPECT(extent == dynamic_extent || count == extent);
322 }
323
span(pointer first_elem,pointer last_elem)324 TCB_SPAN_CONSTEXPR11 span(pointer first_elem, pointer last_elem)
325 : storage_(first_elem, last_elem - first_elem)
326 {
327 TCB_SPAN_EXPECT(extent == dynamic_extent ||
328 last_elem - first_elem ==
329 static_cast<std::ptrdiff_t>(extent));
330 }
331
332 template <std::size_t N, std::size_t E = Extent,
333 typename std::enable_if<
334 (E == dynamic_extent || N == E) &&
335 detail::is_container_element_type_compatible<
336 element_type (&)[N], ElementType>::value,
337 int>::type = 0>
span(element_type (& arr)[N])338 constexpr span(element_type (&arr)[N]) noexcept : storage_(arr, N)
339 {}
340
341 template <std::size_t N, std::size_t E = Extent,
342 typename std::enable_if<
343 (E == dynamic_extent || N == E) &&
344 detail::is_container_element_type_compatible<
345 std::array<value_type, N>&, ElementType>::value,
346 int>::type = 0>
span(std::array<value_type,N> & arr)347 TCB_SPAN_ARRAY_CONSTEXPR span(std::array<value_type, N>& arr) noexcept
348 : storage_(arr.data(), N)
349 {}
350
351 template <std::size_t N, std::size_t E = Extent,
352 typename std::enable_if<
353 (E == dynamic_extent || N == E) &&
354 detail::is_container_element_type_compatible<
355 const std::array<value_type, N>&, ElementType>::value,
356 int>::type = 0>
span(const std::array<value_type,N> & arr)357 TCB_SPAN_ARRAY_CONSTEXPR span(const std::array<value_type, N>& arr) noexcept
358 : storage_(arr.data(), N)
359 {}
360
361 template <
362 typename Container, std::size_t E = Extent,
363 typename std::enable_if<
364 E == dynamic_extent && detail::is_container<Container>::value &&
365 detail::is_container_element_type_compatible<
366 Container&, ElementType>::value,
367 int>::type = 0>
span(Container & cont)368 constexpr span(Container& cont)
369 : storage_(detail::data(cont), detail::size(cont))
370 {}
371
372 template <
373 typename Container, std::size_t E = Extent,
374 typename std::enable_if<
375 E == dynamic_extent && detail::is_container<Container>::value &&
376 detail::is_container_element_type_compatible<
377 const Container&, ElementType>::value,
378 int>::type = 0>
span(const Container & cont)379 constexpr span(const Container& cont)
380 : storage_(detail::data(cont), detail::size(cont))
381 {}
382
383 constexpr span(const span& other) noexcept = default;
384
385 template <typename OtherElementType, std::size_t OtherExtent,
386 typename std::enable_if<
387 (Extent == OtherExtent || Extent == dynamic_extent) &&
388 std::is_convertible<OtherElementType (*)[],
389 ElementType (*)[]>::value,
390 int>::type = 0>
span(const span<OtherElementType,OtherExtent> & other)391 constexpr span(const span<OtherElementType, OtherExtent>& other) noexcept
392 : storage_(other.data(), other.size())
393 {}
394
395 ~span() noexcept = default;
396
397 TCB_SPAN_CONSTEXPR_ASSIGN span&
398 operator=(const span& other) noexcept = default;
399
400 // [span.sub], span subviews
401 template <std::size_t Count>
first() const402 TCB_SPAN_CONSTEXPR11 span<element_type, Count> first() const
403 {
404 TCB_SPAN_EXPECT(Count <= size());
405 return {data(), Count};
406 }
407
408 template <std::size_t Count>
last() const409 TCB_SPAN_CONSTEXPR11 span<element_type, Count> last() const
410 {
411 TCB_SPAN_EXPECT(Count <= size());
412 return {data() + (size() - Count), Count};
413 }
414
415 template <std::size_t Offset, std::size_t Count = dynamic_extent>
416 using subspan_return_t =
417 span<ElementType, Count != dynamic_extent
418 ? Count
419 : (Extent != dynamic_extent ? Extent - Offset
420 : dynamic_extent)>;
421
422 template <std::size_t Offset, std::size_t Count = dynamic_extent>
subspan() const423 TCB_SPAN_CONSTEXPR11 subspan_return_t<Offset, Count> subspan() const
424 {
425 TCB_SPAN_EXPECT(Offset <= size() &&
426 (Count == dynamic_extent || Offset + Count <= size()));
427 return {data() + Offset,
428 Count != dynamic_extent ? Count : size() - Offset};
429 }
430
431 TCB_SPAN_CONSTEXPR11 span<element_type, dynamic_extent>
first(size_type count) const432 first(size_type count) const
433 {
434 TCB_SPAN_EXPECT(count <= size());
435 return {data(), count};
436 }
437
438 TCB_SPAN_CONSTEXPR11 span<element_type, dynamic_extent>
last(size_type count) const439 last(size_type count) const
440 {
441 TCB_SPAN_EXPECT(count <= size());
442 return {data() + (size() - count), count};
443 }
444
445 TCB_SPAN_CONSTEXPR11 span<element_type, dynamic_extent>
subspan(size_type offset,size_type count=dynamic_extent) const446 subspan(size_type offset, size_type count = dynamic_extent) const
447 {
448 TCB_SPAN_EXPECT(offset <= size() &&
449 (count == dynamic_extent || offset + count <= size()));
450 return {data() + offset,
451 count == dynamic_extent ? size() - offset : count};
452 }
453
454 // [span.obs], span observers
size() const455 constexpr size_type size() const noexcept { return storage_.size; }
456
size_bytes() const457 constexpr size_type size_bytes() const noexcept
458 {
459 return size() * sizeof(element_type);
460 }
461
empty() const462 TCB_SPAN_NODISCARD constexpr bool empty() const noexcept
463 {
464 return size() == 0;
465 }
466
467 // [span.elem], span element access
operator [](size_type idx) const468 TCB_SPAN_CONSTEXPR11 reference operator[](size_type idx) const
469 {
470 TCB_SPAN_EXPECT(idx < size());
471 return *(data() + idx);
472 }
473
front() const474 TCB_SPAN_CONSTEXPR11 reference front() const
475 {
476 TCB_SPAN_EXPECT(!empty());
477 return *data();
478 }
479
back() const480 TCB_SPAN_CONSTEXPR11 reference back() const
481 {
482 TCB_SPAN_EXPECT(!empty());
483 return *(data() + (size() - 1));
484 }
485
data() const486 constexpr pointer data() const noexcept { return storage_.ptr; }
487
488 // [span.iterators], span iterator support
begin() const489 constexpr iterator begin() const noexcept { return data(); }
490
end() const491 constexpr iterator end() const noexcept { return data() + size(); }
492
cbegin() const493 constexpr const_iterator cbegin() const noexcept { return begin(); }
494
cend() const495 constexpr const_iterator cend() const noexcept { return end(); }
496
rbegin() const497 TCB_SPAN_ARRAY_CONSTEXPR reverse_iterator rbegin() const noexcept
498 {
499 return reverse_iterator(end());
500 }
501
rend() const502 TCB_SPAN_ARRAY_CONSTEXPR reverse_iterator rend() const noexcept
503 {
504 return reverse_iterator(begin());
505 }
506
crbegin() const507 TCB_SPAN_ARRAY_CONSTEXPR const_reverse_iterator crbegin() const noexcept
508 {
509 return const_reverse_iterator(cend());
510 }
511
crend() const512 TCB_SPAN_ARRAY_CONSTEXPR const_reverse_iterator crend() const noexcept
513 {
514 return const_reverse_iterator(cbegin());
515 }
516
begin(span s)517 friend constexpr iterator begin(span s) noexcept { return s.begin(); }
518
end(span s)519 friend constexpr iterator end(span s) noexcept { return s.end(); }
520
521 private:
522 storage_type storage_{};
523 };
524
525 #ifdef TCB_SPAN_HAVE_DEDUCTION_GUIDES
526
527 /* Deduction Guides */
528 template <class T, size_t N>
529 span(T (&)[N])->span<T, N>;
530
531 template <class T, size_t N>
532 span(std::array<T, N>&)->span<T, N>;
533
534 template <class T, size_t N>
535 span(const std::array<T, N>&)->span<const T, N>;
536
537 template <class Container>
538 span(Container&)->span<typename Container::value_type>;
539
540 template <class Container>
541 span(const Container&)->span<const typename Container::value_type>;
542
543 #endif // TCB_HAVE_DEDUCTION_GUIDES
544
545 template <typename ElementType, std::size_t Extent>
546 constexpr span<ElementType, Extent>
make_span(span<ElementType,Extent> s)547 make_span(span<ElementType, Extent> s) noexcept
548 {
549 return s;
550 }
551
552 template <typename T, std::size_t N>
make_span(T (& arr)[N])553 constexpr span<T, N> make_span(T (&arr)[N]) noexcept
554 {
555 return {arr};
556 }
557
558 template <typename T, std::size_t N>
make_span(std::array<T,N> & arr)559 TCB_SPAN_ARRAY_CONSTEXPR span<T, N> make_span(std::array<T, N>& arr) noexcept
560 {
561 return {arr};
562 }
563
564 template <typename T, std::size_t N>
565 TCB_SPAN_ARRAY_CONSTEXPR span<const T, N>
make_span(const std::array<T,N> & arr)566 make_span(const std::array<T, N>& arr) noexcept
567 {
568 return {arr};
569 }
570
571 template <typename Container>
make_span(Container & cont)572 constexpr span<typename Container::value_type> make_span(Container& cont)
573 {
574 return {cont};
575 }
576
577 template <typename Container>
578 constexpr span<const typename Container::value_type>
make_span(const Container & cont)579 make_span(const Container& cont)
580 {
581 return {cont};
582 }
583
584 template <typename ElementType, std::size_t Extent>
585 span<const byte, ((Extent == dynamic_extent) ? dynamic_extent
586 : sizeof(ElementType) * Extent)>
as_bytes(span<ElementType,Extent> s)587 as_bytes(span<ElementType, Extent> s) noexcept
588 {
589 return {reinterpret_cast<const byte*>(s.data()), s.size_bytes()};
590 }
591
592 template <
593 class ElementType, size_t Extent,
594 typename std::enable_if<!std::is_const<ElementType>::value, int>::type = 0>
595 span<byte, ((Extent == dynamic_extent) ? dynamic_extent
596 : sizeof(ElementType) * Extent)>
as_writable_bytes(span<ElementType,Extent> s)597 as_writable_bytes(span<ElementType, Extent> s) noexcept
598 {
599 return {reinterpret_cast<byte*>(s.data()), s.size_bytes()};
600 }
601
602 template <std::size_t N, typename E, std::size_t S>
get(span<E,S> s)603 constexpr auto get(span<E, S> s) -> decltype(s[N])
604 {
605 return s[N];
606 }
607
608 } // namespace TCB_SPAN_NAMESPACE_NAME
609
610 namespace std {
611
612 template <typename ElementType, size_t Extent>
613 class tuple_size<TCB_SPAN_NAMESPACE_NAME::span<ElementType, Extent>>
614 : public integral_constant<size_t, Extent> {};
615
616 template <typename ElementType>
617 class tuple_size<TCB_SPAN_NAMESPACE_NAME::span<
618 ElementType, TCB_SPAN_NAMESPACE_NAME::dynamic_extent>>; // not defined
619
620 template <size_t I, typename ElementType, size_t Extent>
621 class tuple_element<I, TCB_SPAN_NAMESPACE_NAME::span<ElementType, Extent>> {
622 public:
623 static_assert(Extent != TCB_SPAN_NAMESPACE_NAME::dynamic_extent &&
624 I < Extent,
625 "");
626 using type = ElementType;
627 };
628
629 } // end namespace std
630
631 #endif // TCB_SPAN_HPP_INCLUDED
632