Line data Source code
1 :
2 : /*
3 : This is an implementation of C++20's scipp::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 {
61 : explicit contract_violation_error(const char* msg) : std::logic_error(msg)
62 : {}
63 : };
64 :
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 0 : [[noreturn]] inline void contract_violation(const char* /*unused*/)
72 : {
73 0 : 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 :
156 : 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 7838861 : constexpr span_storage() noexcept = default;
167 :
168 59577753 : constexpr span_storage(E* p_ptr, std::size_t p_size) noexcept
169 59577753 : : ptr(p_ptr), size(p_size)
170 59577753 : {}
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>
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>
189 : constexpr std::size_t size(const T (&)[N]) noexcept
190 : {
191 : return N;
192 : }
193 :
194 : template <class C>
195 : constexpr auto data(C& c) -> decltype(c.data())
196 : {
197 : return c.data();
198 : }
199 :
200 : template <class 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>
207 : constexpr T* data(T (&array)[N]) noexcept
208 : {
209 : return array;
210 : }
211 :
212 : template <class E>
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 const_reference = const element_type&;
305 : using iterator = pointer;
306 : using reverse_iterator = std::reverse_iterator<iterator>;
307 :
308 : static constexpr size_type extent = Extent;
309 :
310 : // [span.cons], span constructors, copy, assignment, and destructor
311 : template <
312 : std::size_t E = Extent,
313 : typename std::enable_if<(E == dynamic_extent || E <= 0), int>::type = 0>
314 7838861 : constexpr span() noexcept
315 7838861 : {}
316 :
317 56637887 : TCB_SPAN_CONSTEXPR11 span(pointer ptr, size_type count)
318 56637887 : : storage_(ptr, count)
319 : {
320 : TCB_SPAN_EXPECT(extent == dynamic_extent || count == extent);
321 56637887 : }
322 :
323 2888717 : TCB_SPAN_CONSTEXPR11 span(pointer first_elem, pointer last_elem)
324 2888717 : : storage_(first_elem, last_elem - first_elem)
325 : {
326 : TCB_SPAN_EXPECT(extent == dynamic_extent ||
327 : last_elem - first_elem ==
328 : static_cast<std::ptrdiff_t>(extent));
329 2888717 : }
330 :
331 : template <std::size_t N, std::size_t E = Extent,
332 : typename std::enable_if<
333 : (E == dynamic_extent || N == E) &&
334 : detail::is_container_element_type_compatible<
335 : element_type (&)[N], ElementType>::value,
336 : int>::type = 0>
337 : constexpr span(element_type (&arr)[N]) noexcept : storage_(arr, N)
338 : {}
339 :
340 : template <std::size_t N, std::size_t E = Extent,
341 : typename std::enable_if<
342 : (E == dynamic_extent || N == E) &&
343 : detail::is_container_element_type_compatible<
344 : std::array<value_type, N>&, ElementType>::value,
345 : int>::type = 0>
346 : TCB_SPAN_ARRAY_CONSTEXPR span(std::array<value_type, N>& arr) noexcept
347 : : storage_(arr.data(), N)
348 : {}
349 :
350 : template <std::size_t N, std::size_t E = Extent,
351 : typename std::enable_if<
352 : (E == dynamic_extent || N == E) &&
353 : detail::is_container_element_type_compatible<
354 : const std::array<value_type, N>&, ElementType>::value,
355 : int>::type = 0>
356 : TCB_SPAN_ARRAY_CONSTEXPR span(const std::array<value_type, N>& arr) noexcept
357 : : storage_(arr.data(), N)
358 : {}
359 :
360 : template <
361 : typename Container, std::size_t E = Extent,
362 : typename std::enable_if<
363 : E == dynamic_extent && detail::is_container<Container>::value &&
364 : detail::is_container_element_type_compatible<
365 : Container&, ElementType>::value,
366 : int>::type = 0>
367 15667 : constexpr span(Container& cont)
368 15667 : : storage_(detail::data(cont), detail::size(cont))
369 15667 : {}
370 :
371 : template <
372 : typename Container, std::size_t E = Extent,
373 : typename std::enable_if<
374 : E == dynamic_extent && detail::is_container<Container>::value &&
375 : detail::is_container_element_type_compatible<
376 : const Container&, ElementType>::value,
377 : int>::type = 0>
378 35482 : constexpr span(const Container& cont)
379 35482 : : storage_(detail::data(cont), detail::size(cont))
380 35482 : {}
381 :
382 : constexpr span(const span& other) noexcept = default;
383 :
384 : template <typename OtherElementType, std::size_t OtherExtent,
385 : typename std::enable_if<
386 : (Extent == OtherExtent || Extent == dynamic_extent) &&
387 : std::is_convertible<OtherElementType (*)[],
388 : ElementType (*)[]>::value,
389 : int>::type = 0>
390 : constexpr span(const span<OtherElementType, OtherExtent>& other) noexcept
391 : : storage_(other.data(), other.size())
392 : {}
393 :
394 : ~span() noexcept = default;
395 :
396 : TCB_SPAN_CONSTEXPR_ASSIGN span&
397 : operator=(const span& other) noexcept = default;
398 :
399 : // [span.sub], span subviews
400 : template <std::size_t Count>
401 : TCB_SPAN_CONSTEXPR11 span<element_type, Count> first() const
402 : {
403 : TCB_SPAN_EXPECT(Count <= size());
404 : return {data(), Count};
405 : }
406 :
407 : template <std::size_t Count>
408 : TCB_SPAN_CONSTEXPR11 span<element_type, Count> last() const
409 : {
410 : TCB_SPAN_EXPECT(Count <= size());
411 : return {data() + (size() - Count), Count};
412 : }
413 :
414 : template <std::size_t Offset, std::size_t Count = dynamic_extent>
415 : using subspan_return_t =
416 : span<ElementType, Count != dynamic_extent
417 : ? Count
418 : : (Extent != dynamic_extent ? Extent - Offset
419 : : dynamic_extent)>;
420 :
421 : template <std::size_t Offset, std::size_t Count = dynamic_extent>
422 : TCB_SPAN_CONSTEXPR11 subspan_return_t<Offset, Count> subspan() const
423 : {
424 : TCB_SPAN_EXPECT(Offset <= size() &&
425 : (Count == dynamic_extent || Offset + Count <= size()));
426 : return {data() + Offset,
427 : Count != dynamic_extent ? Count : size() - Offset};
428 : }
429 :
430 : TCB_SPAN_CONSTEXPR11 span<element_type, dynamic_extent>
431 : first(size_type count) const
432 : {
433 : TCB_SPAN_EXPECT(count <= size());
434 : return {data(), count};
435 : }
436 :
437 : TCB_SPAN_CONSTEXPR11 span<element_type, dynamic_extent>
438 : last(size_type count) const
439 : {
440 : TCB_SPAN_EXPECT(count <= size());
441 : return {data() + (size() - count), count};
442 : }
443 :
444 : TCB_SPAN_CONSTEXPR11 span<element_type, dynamic_extent>
445 : subspan(size_type offset, size_type count = dynamic_extent) const
446 : {
447 : TCB_SPAN_EXPECT(offset <= size() &&
448 : (count == dynamic_extent || offset + count <= size()));
449 : return {data() + offset,
450 : count == dynamic_extent ? size() - offset : count};
451 : }
452 :
453 : // [span.obs], span observers
454 1322242600 : constexpr size_type size() const noexcept { return storage_.size; }
455 :
456 : constexpr size_type size_bytes() const noexcept
457 : {
458 : return size() * sizeof(element_type);
459 : }
460 :
461 131304921 : TCB_SPAN_NODISCARD constexpr bool empty() const noexcept
462 : {
463 131304921 : return size() == 0;
464 : }
465 :
466 : // [span.elem], span element access
467 1028029044 : TCB_SPAN_CONSTEXPR11 reference operator[](size_type idx) const
468 : {
469 1028029044 : TCB_SPAN_EXPECT(idx < size());
470 1028029044 : return *(data() + idx);
471 : }
472 :
473 76900307 : TCB_SPAN_CONSTEXPR11 reference front() const
474 : {
475 76900307 : TCB_SPAN_EXPECT(!empty());
476 76900307 : return *data();
477 : }
478 :
479 54293912 : TCB_SPAN_CONSTEXPR11 reference back() const
480 : {
481 54293912 : TCB_SPAN_EXPECT(!empty());
482 54293912 : return *(data() + (size() - 1));
483 : }
484 :
485 1300014803 : constexpr pointer data() const noexcept { return storage_.ptr; }
486 :
487 : // [span.iterators], span iterator support
488 74983523 : constexpr iterator begin() const noexcept { return data(); }
489 :
490 64706875 : constexpr iterator end() const noexcept { return data() + size(); }
491 :
492 2099 : TCB_SPAN_ARRAY_CONSTEXPR reverse_iterator rbegin() const noexcept
493 : {
494 2099 : return reverse_iterator(end());
495 : }
496 :
497 2099 : TCB_SPAN_ARRAY_CONSTEXPR reverse_iterator rend() const noexcept
498 : {
499 2099 : return reverse_iterator(begin());
500 : }
501 :
502 : private:
503 : storage_type storage_{};
504 : };
505 :
506 : #ifdef TCB_SPAN_HAVE_DEDUCTION_GUIDES
507 :
508 : /* Deduction Guides */
509 : template <class T, size_t N>
510 : span(T (&)[N])->span<T, N>;
511 :
512 : template <class T, size_t N>
513 : span(std::array<T, N>&)->span<T, N>;
514 :
515 : template <class T, size_t N>
516 : span(const std::array<T, N>&)->span<const T, N>;
517 :
518 : template <class Container>
519 : span(Container&)->span<typename Container::value_type>;
520 :
521 : template <class Container>
522 : span(const Container&)->span<const typename Container::value_type>;
523 :
524 : #endif // TCB_HAVE_DEDUCTION_GUIDES
525 :
526 : template <typename ElementType, std::size_t Extent>
527 : constexpr span<ElementType, Extent>
528 : make_span(span<ElementType, Extent> s) noexcept
529 : {
530 : return s;
531 : }
532 :
533 : template <typename T, std::size_t N>
534 : constexpr span<T, N> make_span(T (&arr)[N]) noexcept
535 : {
536 : return {arr};
537 : }
538 :
539 : template <typename T, std::size_t N>
540 : TCB_SPAN_ARRAY_CONSTEXPR span<T, N> make_span(std::array<T, N>& arr) noexcept
541 : {
542 : return {arr};
543 : }
544 :
545 : template <typename T, std::size_t N>
546 : TCB_SPAN_ARRAY_CONSTEXPR span<const T, N>
547 : make_span(const std::array<T, N>& arr) noexcept
548 : {
549 : return {arr};
550 : }
551 :
552 : template <typename Container>
553 : constexpr span<typename Container::value_type> make_span(Container& cont)
554 : {
555 : return {cont};
556 : }
557 :
558 : template <typename Container>
559 : constexpr span<const typename Container::value_type>
560 : make_span(const Container& cont)
561 : {
562 : return {cont};
563 : }
564 :
565 : template <typename ElementType, std::size_t Extent>
566 : span<const byte, ((Extent == dynamic_extent) ? dynamic_extent
567 : : sizeof(ElementType) * Extent)>
568 : as_bytes(span<ElementType, Extent> s) noexcept
569 : {
570 : return {reinterpret_cast<const byte*>(s.data()), s.size_bytes()};
571 : }
572 :
573 : template <
574 : class ElementType, size_t Extent,
575 : typename std::enable_if<!std::is_const<ElementType>::value, int>::type = 0>
576 : span<byte, ((Extent == dynamic_extent) ? dynamic_extent
577 : : sizeof(ElementType) * Extent)>
578 : as_writable_bytes(span<ElementType, Extent> s) noexcept
579 : {
580 : return {reinterpret_cast<byte*>(s.data()), s.size_bytes()};
581 : }
582 :
583 : template <std::size_t N, typename E, std::size_t S>
584 : constexpr auto get(span<E, S> s) -> decltype(s[N])
585 : {
586 : return s[N];
587 : }
588 :
589 : } // namespace TCB_SPAN_NAMESPACE_NAME
590 :
591 : namespace std {
592 :
593 : template <typename ElementType, size_t Extent>
594 : class tuple_size<TCB_SPAN_NAMESPACE_NAME::span<ElementType, Extent>>
595 : : public integral_constant<size_t, Extent> {};
596 :
597 : template <typename ElementType>
598 : class tuple_size<TCB_SPAN_NAMESPACE_NAME::span<
599 : ElementType, TCB_SPAN_NAMESPACE_NAME::dynamic_extent>>; // not defined
600 :
601 : template <size_t I, typename ElementType, size_t Extent>
602 : class tuple_element<I, TCB_SPAN_NAMESPACE_NAME::span<ElementType, Extent>> {
603 : public:
604 : static_assert(Extent != TCB_SPAN_NAMESPACE_NAME::dynamic_extent &&
605 : I < Extent,
606 : "");
607 : using type = ElementType;
608 : };
609 :
610 : } // end namespace std
611 :
612 : #endif // TCB_SPAN_HPP_INCLUDED
|