1 | // Components for manipulating non-owning sequences of objects -*- C++ -*- |
2 | |
3 | // Copyright (C) 2019-2024 Free Software Foundation, Inc. |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free |
6 | // software; you can redistribute it and/or modify it under the |
7 | // terms of the GNU General Public License as published by the |
8 | // Free Software Foundation; either version 3, or (at your option) |
9 | // any later version. |
10 | |
11 | // This library is distributed in the hope that it will be useful, |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | // GNU General Public License for more details. |
15 | |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version |
18 | // 3.1, as published by the Free Software Foundation. |
19 | |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
23 | // <http://www.gnu.org/licenses/>. |
24 | |
25 | /** @file span |
26 | * This is a Standard C++ Library header. |
27 | */ |
28 | |
29 | // |
30 | // P0122 span library |
31 | // Contributed by ThePhD |
32 | // |
33 | |
34 | #ifndef _GLIBCXX_SPAN |
35 | #define _GLIBCXX_SPAN 1 |
36 | |
37 | #pragma GCC system_header |
38 | |
39 | #define __glibcxx_want_span |
40 | #include <bits/version.h> |
41 | |
42 | #ifdef __cpp_lib_span // C++ >= 20 && concepts |
43 | #include <array> |
44 | #include <cstddef> |
45 | #include <bits/stl_iterator.h> |
46 | #include <bits/ranges_base.h> |
47 | namespace std _GLIBCXX_VISIBILITY(default) |
48 | { |
49 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
50 | |
51 | inline constexpr size_t dynamic_extent = static_cast<size_t>(-1); |
52 | |
53 | template<typename _Type, size_t _Extent> |
54 | class span; |
55 | |
56 | namespace __detail |
57 | { |
58 | template<typename _Tp> |
59 | inline constexpr bool __is_span = false; |
60 | |
61 | template<typename _Tp, size_t _Num> |
62 | inline constexpr bool __is_span<span<_Tp, _Num>> = true; |
63 | |
64 | template<typename _Tp> |
65 | inline constexpr bool __is_std_array = false; |
66 | |
67 | template<typename _Tp, size_t _Num> |
68 | inline constexpr bool __is_std_array<std::array<_Tp, _Num>> = true; |
69 | |
70 | template<size_t _Extent> |
71 | class __extent_storage |
72 | { |
73 | public: |
74 | constexpr |
75 | __extent_storage(size_t) noexcept |
76 | { } |
77 | |
78 | static constexpr size_t |
79 | _M_extent() noexcept |
80 | { return _Extent; } |
81 | }; |
82 | |
83 | template<> |
84 | class __extent_storage<dynamic_extent> |
85 | { |
86 | public: |
87 | constexpr |
88 | __extent_storage(size_t __extent) noexcept |
89 | : _M_extent_value(__extent) |
90 | { } |
91 | |
92 | constexpr size_t |
93 | _M_extent() const noexcept |
94 | { return this->_M_extent_value; } |
95 | |
96 | private: |
97 | size_t _M_extent_value; |
98 | }; |
99 | } // namespace __detail |
100 | |
101 | template<typename _Type, size_t _Extent = dynamic_extent> |
102 | class span |
103 | { |
104 | template<size_t _Offset, size_t _Count> |
105 | static constexpr size_t |
106 | _S_subspan_extent() |
107 | { |
108 | if constexpr (_Count != dynamic_extent) |
109 | return _Count; |
110 | else if constexpr (extent != dynamic_extent) |
111 | return _Extent - _Offset; |
112 | else |
113 | return dynamic_extent; |
114 | } |
115 | |
116 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
117 | // 3255. span's array constructor is too strict |
118 | template<typename _Tp, size_t _ArrayExtent> |
119 | requires (_Extent == dynamic_extent || _ArrayExtent == _Extent) |
120 | using __is_compatible_array = __is_array_convertible<_Type, _Tp>; |
121 | |
122 | template<typename _Ref> |
123 | using __is_compatible_ref |
124 | = __is_array_convertible<_Type, remove_reference_t<_Ref>>; |
125 | |
126 | public: |
127 | // member types |
128 | using element_type = _Type; |
129 | using value_type = remove_cv_t<_Type>; |
130 | using size_type = size_t; |
131 | using difference_type = ptrdiff_t; |
132 | using pointer = _Type*; |
133 | using const_pointer = const _Type*; |
134 | using reference = element_type&; |
135 | using const_reference = const element_type&; |
136 | using iterator = __gnu_cxx::__normal_iterator<pointer, span>; |
137 | using reverse_iterator = std::reverse_iterator<iterator>; |
138 | #if __cplusplus > 202002L |
139 | using const_iterator = std::const_iterator<iterator>; |
140 | using const_reverse_iterator = std::const_iterator<reverse_iterator>; |
141 | #endif |
142 | |
143 | // member constants |
144 | static constexpr size_t extent = _Extent; |
145 | |
146 | // constructors, copy and assignment |
147 | |
148 | constexpr |
149 | span() noexcept |
150 | requires (_Extent == dynamic_extent || _Extent == 0) |
151 | : _M_ptr(nullptr), _M_extent(0) |
152 | { } |
153 | |
154 | template<contiguous_iterator _It> |
155 | requires __is_compatible_ref<iter_reference_t<_It>>::value |
156 | constexpr explicit(extent != dynamic_extent) |
157 | span(_It __first, size_type __count) |
158 | noexcept |
159 | : _M_ptr(std::to_address(__first)), _M_extent(__count) |
160 | { |
161 | if constexpr (_Extent != dynamic_extent) |
162 | { |
163 | __glibcxx_assert(__count == _Extent); |
164 | } |
165 | __glibcxx_requires_valid_range(__first, __first + __count); |
166 | } |
167 | |
168 | template<contiguous_iterator _It, sized_sentinel_for<_It> _End> |
169 | requires __is_compatible_ref<iter_reference_t<_It>>::value |
170 | && (!is_convertible_v<_End, size_type>) |
171 | constexpr explicit(extent != dynamic_extent) |
172 | span(_It __first, _End __last) |
173 | noexcept(noexcept(__last - __first)) |
174 | : _M_ptr(std::to_address(__first)), |
175 | _M_extent(static_cast<size_type>(__last - __first)) |
176 | { |
177 | if constexpr (_Extent != dynamic_extent) |
178 | { |
179 | __glibcxx_assert((__last - __first) == _Extent); |
180 | } |
181 | __glibcxx_requires_valid_range(__first, __last); |
182 | } |
183 | |
184 | template<size_t _ArrayExtent> |
185 | requires (_Extent == dynamic_extent || _ArrayExtent == _Extent) |
186 | constexpr |
187 | span(type_identity_t<element_type> (&__arr)[_ArrayExtent]) noexcept |
188 | : span(static_cast<pointer>(__arr), _ArrayExtent) |
189 | { } |
190 | |
191 | template<typename _Tp, size_t _ArrayExtent> |
192 | requires __is_compatible_array<_Tp, _ArrayExtent>::value |
193 | constexpr |
194 | span(array<_Tp, _ArrayExtent>& __arr) noexcept |
195 | : span(static_cast<pointer>(__arr.data()), _ArrayExtent) |
196 | { } |
197 | |
198 | template<typename _Tp, size_t _ArrayExtent> |
199 | requires __is_compatible_array<const _Tp, _ArrayExtent>::value |
200 | constexpr |
201 | span(const array<_Tp, _ArrayExtent>& __arr) noexcept |
202 | : span(static_cast<pointer>(__arr.data()), _ArrayExtent) |
203 | { } |
204 | |
205 | template<typename _Range> |
206 | requires (!__detail::__is_span<remove_cvref_t<_Range>>) |
207 | && (!__detail::__is_std_array<remove_cvref_t<_Range>>) |
208 | && (!is_array_v<remove_cvref_t<_Range>>) |
209 | && ranges::contiguous_range<_Range> && ranges::sized_range<_Range> |
210 | && (ranges::borrowed_range<_Range> || is_const_v<element_type>) |
211 | && __is_compatible_ref<ranges::range_reference_t<_Range>>::value |
212 | constexpr explicit(extent != dynamic_extent) |
213 | span(_Range&& __range) |
214 | noexcept(noexcept(ranges::data(__range)) |
215 | && noexcept(ranges::size(__range))) |
216 | : span(ranges::data(__range), ranges::size(__range)) |
217 | { |
218 | if constexpr (extent != dynamic_extent) |
219 | { |
220 | __glibcxx_assert(ranges::size(__range) == extent); |
221 | } |
222 | } |
223 | |
224 | constexpr |
225 | span(const span&) noexcept = default; |
226 | |
227 | template<typename _OType, size_t _OExtent> |
228 | requires (_Extent == dynamic_extent || _OExtent == dynamic_extent |
229 | || _Extent == _OExtent) |
230 | && (__is_array_convertible<_Type, _OType>::value) |
231 | constexpr |
232 | explicit(extent != dynamic_extent && _OExtent == dynamic_extent) |
233 | span(const span<_OType, _OExtent>& __s) noexcept |
234 | : _M_extent(__s.size()), _M_ptr(__s.data()) |
235 | { |
236 | if constexpr (extent != dynamic_extent) |
237 | { |
238 | __glibcxx_assert(__s.size() == extent); |
239 | } |
240 | } |
241 | |
242 | ~span() noexcept = default; |
243 | |
244 | constexpr span& |
245 | operator=(const span&) noexcept = default; |
246 | |
247 | // observers |
248 | |
249 | [[nodiscard]] |
250 | constexpr size_type |
251 | size() const noexcept |
252 | { return this->_M_extent._M_extent(); } |
253 | |
254 | [[nodiscard]] |
255 | constexpr size_type |
256 | size_bytes() const noexcept |
257 | { return this->_M_extent._M_extent() * sizeof(element_type); } |
258 | |
259 | [[nodiscard]] |
260 | constexpr bool |
261 | empty() const noexcept |
262 | { return size() == 0; } |
263 | |
264 | // element access |
265 | |
266 | [[nodiscard]] |
267 | constexpr reference |
268 | front() const noexcept |
269 | { |
270 | __glibcxx_assert(!empty()); |
271 | return *this->_M_ptr; |
272 | } |
273 | |
274 | [[nodiscard]] |
275 | constexpr reference |
276 | back() const noexcept |
277 | { |
278 | __glibcxx_assert(!empty()); |
279 | return *(this->_M_ptr + (size() - 1)); |
280 | } |
281 | |
282 | [[nodiscard]] |
283 | constexpr reference |
284 | operator[](size_type __idx) const noexcept |
285 | { |
286 | __glibcxx_assert(__idx < size()); |
287 | return *(this->_M_ptr + __idx); |
288 | } |
289 | |
290 | #if __cpp_lib_span >= 202311L // >= C++26 |
291 | [[nodiscard]] |
292 | constexpr reference |
293 | at(size_type __idx) const |
294 | { |
295 | if (__idx >= size()) |
296 | __throw_out_of_range_fmt(__N("span::at(%zu) out-of-range for span " |
297 | "of size %zu" ), __idx, this->size()); |
298 | return *(this->_M_ptr + __idx); |
299 | } |
300 | #endif |
301 | |
302 | [[nodiscard]] |
303 | constexpr pointer |
304 | data() const noexcept |
305 | { return this->_M_ptr; } |
306 | |
307 | // iterator support |
308 | |
309 | [[nodiscard]] |
310 | constexpr iterator |
311 | begin() const noexcept |
312 | { return iterator(this->_M_ptr); } |
313 | |
314 | [[nodiscard]] |
315 | constexpr iterator |
316 | end() const noexcept |
317 | { return iterator(this->_M_ptr + this->size()); } |
318 | |
319 | [[nodiscard]] |
320 | constexpr reverse_iterator |
321 | rbegin() const noexcept |
322 | { return reverse_iterator(this->end()); } |
323 | |
324 | [[nodiscard]] |
325 | constexpr reverse_iterator |
326 | rend() const noexcept |
327 | { return reverse_iterator(this->begin()); } |
328 | |
329 | #if __cplusplus > 202002L |
330 | [[nodiscard]] |
331 | constexpr const_iterator |
332 | cbegin() const noexcept |
333 | { return begin(); } |
334 | |
335 | [[nodiscard]] |
336 | constexpr const_iterator |
337 | cend() const noexcept |
338 | { return end(); } |
339 | |
340 | [[nodiscard]] |
341 | constexpr const_reverse_iterator |
342 | crbegin() const noexcept |
343 | { return rbegin(); } |
344 | |
345 | [[nodiscard]] |
346 | constexpr const_reverse_iterator |
347 | crend() const noexcept |
348 | { return rend(); } |
349 | #endif |
350 | |
351 | // subviews |
352 | |
353 | template<size_t _Count> |
354 | [[nodiscard]] |
355 | constexpr span<element_type, _Count> |
356 | first() const noexcept |
357 | { |
358 | if constexpr (_Extent == dynamic_extent) |
359 | __glibcxx_assert(_Count <= size()); |
360 | else |
361 | static_assert(_Count <= extent); |
362 | using _Sp = span<element_type, _Count>; |
363 | return _Sp{ this->data(), _Count }; |
364 | } |
365 | |
366 | [[nodiscard]] |
367 | constexpr span<element_type, dynamic_extent> |
368 | first(size_type __count) const noexcept |
369 | { |
370 | __glibcxx_assert(__count <= size()); |
371 | return { this->data(), __count }; |
372 | } |
373 | |
374 | template<size_t _Count> |
375 | [[nodiscard]] |
376 | constexpr span<element_type, _Count> |
377 | last() const noexcept |
378 | { |
379 | if constexpr (_Extent == dynamic_extent) |
380 | __glibcxx_assert(_Count <= size()); |
381 | else |
382 | static_assert(_Count <= extent); |
383 | using _Sp = span<element_type, _Count>; |
384 | return _Sp{ this->data() + (this->size() - _Count), _Count }; |
385 | } |
386 | |
387 | [[nodiscard]] |
388 | constexpr span<element_type, dynamic_extent> |
389 | last(size_type __count) const noexcept |
390 | { |
391 | __glibcxx_assert(__count <= size()); |
392 | return { this->data() + (this->size() - __count), __count }; |
393 | } |
394 | |
395 | template<size_t _Offset, size_t _Count = dynamic_extent> |
396 | [[nodiscard]] |
397 | constexpr auto |
398 | subspan() const noexcept |
399 | -> span<element_type, _S_subspan_extent<_Offset, _Count>()> |
400 | { |
401 | if constexpr (_Extent == dynamic_extent) |
402 | { |
403 | __glibcxx_assert(_Offset <= size()); |
404 | } |
405 | else |
406 | static_assert(_Offset <= extent); |
407 | |
408 | using _Sp = span<element_type, _S_subspan_extent<_Offset, _Count>()>; |
409 | |
410 | if constexpr (_Count == dynamic_extent) |
411 | return _Sp{ this->data() + _Offset, this->size() - _Offset }; |
412 | else |
413 | { |
414 | if constexpr (_Extent == dynamic_extent) |
415 | { |
416 | __glibcxx_assert(_Count <= size()); |
417 | __glibcxx_assert(_Count <= (size() - _Offset)); |
418 | } |
419 | else |
420 | { |
421 | static_assert(_Count <= extent); |
422 | static_assert(_Count <= (extent - _Offset)); |
423 | } |
424 | return _Sp{ this->data() + _Offset, _Count }; |
425 | } |
426 | } |
427 | |
428 | [[nodiscard]] |
429 | constexpr span<element_type, dynamic_extent> |
430 | subspan(size_type __offset, size_type __count = dynamic_extent) const |
431 | noexcept |
432 | { |
433 | __glibcxx_assert(__offset <= size()); |
434 | if (__count == dynamic_extent) |
435 | __count = this->size() - __offset; |
436 | else |
437 | { |
438 | __glibcxx_assert(__count <= size()); |
439 | __glibcxx_assert(__offset + __count <= size()); |
440 | } |
441 | return {this->data() + __offset, __count}; |
442 | } |
443 | |
444 | private: |
445 | pointer _M_ptr; |
446 | [[no_unique_address]] __detail::__extent_storage<extent> _M_extent; |
447 | }; |
448 | |
449 | // deduction guides |
450 | |
451 | template<typename _Type, size_t _ArrayExtent> |
452 | span(_Type(&)[_ArrayExtent]) -> span<_Type, _ArrayExtent>; |
453 | |
454 | template<typename _Type, size_t _ArrayExtent> |
455 | span(array<_Type, _ArrayExtent>&) -> span<_Type, _ArrayExtent>; |
456 | |
457 | template<typename _Type, size_t _ArrayExtent> |
458 | span(const array<_Type, _ArrayExtent>&) |
459 | -> span<const _Type, _ArrayExtent>; |
460 | |
461 | template<contiguous_iterator _Iter, typename _End> |
462 | span(_Iter, _End) |
463 | -> span<remove_reference_t<iter_reference_t<_Iter>>>; |
464 | |
465 | template<ranges::contiguous_range _Range> |
466 | span(_Range &&) |
467 | -> span<remove_reference_t<ranges::range_reference_t<_Range&>>>; |
468 | |
469 | template<typename _Type, size_t _Extent> |
470 | [[nodiscard]] |
471 | inline |
472 | span<const byte, _Extent == dynamic_extent |
473 | ? dynamic_extent : _Extent * sizeof(_Type)> |
474 | as_bytes(span<_Type, _Extent> __sp) noexcept |
475 | { |
476 | auto data = reinterpret_cast<const byte*>(__sp.data()); |
477 | auto size = __sp.size_bytes(); |
478 | constexpr auto extent = _Extent == dynamic_extent |
479 | ? dynamic_extent : _Extent * sizeof(_Type); |
480 | return span<const byte, extent>{data, size}; |
481 | } |
482 | |
483 | template<typename _Type, size_t _Extent> |
484 | requires (!is_const_v<_Type>) |
485 | inline |
486 | span<byte, _Extent == dynamic_extent |
487 | ? dynamic_extent : _Extent * sizeof(_Type)> |
488 | as_writable_bytes [[nodiscard]] (span<_Type, _Extent> __sp) noexcept |
489 | { |
490 | auto data = reinterpret_cast<byte*>(__sp.data()); |
491 | auto size = __sp.size_bytes(); |
492 | constexpr auto extent = _Extent == dynamic_extent |
493 | ? dynamic_extent : _Extent * sizeof(_Type); |
494 | return span<byte, extent>{data, size}; |
495 | } |
496 | |
497 | namespace ranges |
498 | { |
499 | // Opt-in to borrowed_range concept |
500 | template<typename _ElementType, size_t _Extent> |
501 | inline constexpr bool |
502 | enable_borrowed_range<span<_ElementType, _Extent>> = true; |
503 | |
504 | // Opt-in to view concept |
505 | template<typename _ElementType, size_t _Extent> |
506 | inline constexpr bool |
507 | enable_view<span<_ElementType, _Extent>> = true; |
508 | } |
509 | _GLIBCXX_END_NAMESPACE_VERSION |
510 | } // namespace std |
511 | #endif // __cpp_lib_span |
512 | #endif // _GLIBCXX_SPAN |
513 | |