1// Components for manipulating non-owning sequences of objects -*- C++ -*-
2
3// Copyright (C) 2019-2022 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#if __cplusplus > 201703L
40
41#include <array>
42#include <cstddef>
43#include <bits/stl_iterator.h>
44#include <bits/ranges_base.h>
45
46#if __cpp_lib_concepts
47namespace std _GLIBCXX_VISIBILITY(default)
48{
49_GLIBCXX_BEGIN_NAMESPACE_VERSION
50
51#define __cpp_lib_span 202002L
52
53  inline constexpr size_t dynamic_extent = static_cast<size_t>(-1);
54
55  template<typename _Type, size_t _Extent>
56    class span;
57
58  namespace __detail
59  {
60    template<typename _Tp>
61      inline constexpr bool __is_span = false;
62
63    template<typename _Tp, size_t _Num>
64      inline constexpr bool __is_span<span<_Tp, _Num>> = true;
65
66    template<typename _Tp>
67      inline constexpr bool __is_std_array = false;
68
69    template<typename _Tp, size_t _Num>
70      inline constexpr bool __is_std_array<std::array<_Tp, _Num>> = true;
71
72    template<size_t _Extent>
73      class __extent_storage
74      {
75      public:
76          constexpr
77          __extent_storage(size_t) noexcept
78          { }
79
80          static constexpr size_t
81          _M_extent() noexcept
82          { return _Extent; }
83      };
84
85    template<>
86      class __extent_storage<dynamic_extent>
87      {
88      public:
89          constexpr
90          __extent_storage(size_t __extent) noexcept
91          : _M_extent_value(__extent)
92          { }
93
94          constexpr size_t
95          _M_extent() const noexcept
96          { return this->_M_extent_value; }
97
98      private:
99          size_t _M_extent_value;
100      };
101  } // namespace __detail
102
103  template<typename _Type, size_t _Extent = dynamic_extent>
104    class span
105    {
106      template<size_t _Offset, size_t _Count>
107          static constexpr size_t
108          _S_subspan_extent()
109          {
110            if constexpr (_Count != dynamic_extent)
111              return _Count;
112            else if constexpr (extent != dynamic_extent)
113              return _Extent - _Offset;
114            else
115              return dynamic_extent;
116          }
117
118      // _GLIBCXX_RESOLVE_LIB_DEFECTS
119      // 3255. span's array constructor is too strict
120      template<typename _Tp, size_t _ArrayExtent>
121          requires (_Extent == dynamic_extent || _ArrayExtent == _Extent)
122          using __is_compatible_array = __is_array_convertible<_Type, _Tp>;
123
124      template<typename _Ref>
125          using __is_compatible_ref
126            = __is_array_convertible<_Type, remove_reference_t<_Ref>>;
127
128    public:
129      // member types
130      using element_type           = _Type;
131      using value_type             = remove_cv_t<_Type>;
132      using size_type              = size_t;
133      using difference_type        = ptrdiff_t;
134      using pointer                = _Type*;
135      using const_pointer          = const _Type*;
136      using reference              = element_type&;
137      using const_reference        = const element_type&;
138      using iterator = __gnu_cxx::__normal_iterator<pointer, span>;
139      using reverse_iterator       = std::reverse_iterator<iterator>;
140
141      // member constants
142      static constexpr size_t extent = _Extent;
143
144      // constructors, copy and assignment
145
146      constexpr
147      span() noexcept
148      requires ((_Extent + 1u) <= 1u)
149      : _M_ptr(nullptr), _M_extent(0)
150      { }
151
152      template<contiguous_iterator _It>
153          requires __is_compatible_ref<iter_reference_t<_It>>::value
154          constexpr explicit(extent != dynamic_extent)
155          span(_It __first, size_type __count)
156          noexcept
157          : _M_ptr(std::to_address(__first)), _M_extent(__count)
158          {
159            if constexpr (_Extent != dynamic_extent)
160              {
161                __glibcxx_assert(__count == _Extent);
162              }
163            __glibcxx_requires_valid_range(__first, __first + __count);
164          }
165
166      template<contiguous_iterator _It, sized_sentinel_for<_It> _End>
167          requires __is_compatible_ref<iter_reference_t<_It>>::value
168            && (!is_convertible_v<_End, size_type>)
169          constexpr explicit(extent != dynamic_extent)
170          span(_It __first, _End __last)
171          noexcept(noexcept(__last - __first))
172          : _M_ptr(std::to_address(__first)),
173            _M_extent(static_cast<size_type>(__last - __first))
174          {
175            if constexpr (_Extent != dynamic_extent)
176              {
177                __glibcxx_assert((__last - __first) == _Extent);
178              }
179            __glibcxx_requires_valid_range(__first, __last);
180          }
181
182      template<size_t _ArrayExtent>
183          requires (_Extent == dynamic_extent || _ArrayExtent == _Extent)
184          constexpr
185          span(type_identity_t<element_type> (&__arr)[_ArrayExtent]) noexcept
186          : span(static_cast<pointer>(__arr), _ArrayExtent)
187          { }
188
189      template<typename _Tp, size_t _ArrayExtent>
190          requires __is_compatible_array<_Tp, _ArrayExtent>::value
191          constexpr
192          span(array<_Tp, _ArrayExtent>& __arr) noexcept
193          : span(static_cast<pointer>(__arr.data()), _ArrayExtent)
194          { }
195
196      template<typename _Tp, size_t _ArrayExtent>
197          requires __is_compatible_array<const _Tp, _ArrayExtent>::value
198          constexpr
199          span(const array<_Tp, _ArrayExtent>& __arr) noexcept
200          : span(static_cast<pointer>(__arr.data()), _ArrayExtent)
201          { }
202
203      template<typename _Range>
204          requires (!__detail::__is_span<remove_cvref_t<_Range>>)
205            && (!__detail::__is_std_array<remove_cvref_t<_Range>>)
206            && (!is_array_v<remove_cvref_t<_Range>>)
207            && ranges::contiguous_range<_Range> && ranges::sized_range<_Range>
208            && (ranges::borrowed_range<_Range> || is_const_v<element_type>)
209            && __is_compatible_ref<ranges::range_reference_t<_Range>>::value
210          constexpr explicit(extent != dynamic_extent)
211          span(_Range&& __range)
212          noexcept(noexcept(ranges::data(__range))
213                      && noexcept(ranges::size(__range)))
214          : span(ranges::data(__range), ranges::size(__range))
215          {
216            if constexpr (extent != dynamic_extent)
217              {
218                __glibcxx_assert(ranges::size(__range) == extent);
219              }
220          }
221
222      constexpr
223      span(const span&) noexcept = default;
224
225      template<typename _OType, size_t _OExtent>
226          requires (_Extent == dynamic_extent || _OExtent == dynamic_extent
227                      || _Extent == _OExtent)
228            && (__is_array_convertible<_Type, _OType>::value)
229          constexpr
230          explicit(extent != dynamic_extent && _OExtent == dynamic_extent)
231          span(const span<_OType, _OExtent>& __s) noexcept
232          : _M_extent(__s.size()), _M_ptr(__s.data())
233          {
234            if constexpr (extent != dynamic_extent)
235              {
236                __glibcxx_assert(__s.size() == extent);
237              }
238          }
239
240      ~span() noexcept = default;
241
242      constexpr span&
243      operator=(const span&) noexcept = default;
244
245      // observers
246
247      constexpr size_type
248      size() const noexcept
249      { return this->_M_extent._M_extent(); }
250
251      constexpr size_type
252      size_bytes() const noexcept
253      { return this->_M_extent._M_extent() * sizeof(element_type); }
254
255      [[nodiscard]] constexpr bool
256      empty() const noexcept
257      { return size() == 0; }
258
259      // element access
260
261      constexpr reference
262      front() const noexcept
263      {
264          __glibcxx_assert(!empty());
265          return *this->_M_ptr;
266      }
267
268      constexpr reference
269      back() const noexcept
270      {
271          __glibcxx_assert(!empty());
272          return *(this->_M_ptr + (size() - 1));
273      }
274
275      constexpr reference
276      operator[](size_type __idx) const noexcept
277      {
278          __glibcxx_assert(__idx < size());
279          return *(this->_M_ptr + __idx);
280      }
281
282      constexpr pointer
283      data() const noexcept
284      { return this->_M_ptr; }
285
286      // iterator support
287
288      constexpr iterator
289      begin() const noexcept
290      { return iterator(this->_M_ptr); }
291
292      constexpr iterator
293      end() const noexcept
294      { return iterator(this->_M_ptr + this->size()); }
295
296      constexpr reverse_iterator
297      rbegin() const noexcept
298      { return reverse_iterator(this->end()); }
299
300      constexpr reverse_iterator
301      rend() const noexcept
302      { return reverse_iterator(this->begin()); }
303
304      // subviews
305
306      template<size_t _Count>
307          constexpr span<element_type, _Count>
308          first() const noexcept
309          {
310            if constexpr (_Extent == dynamic_extent)
311              __glibcxx_assert(_Count <= size());
312            else
313              static_assert(_Count <= extent);
314            using _Sp = span<element_type, _Count>;
315            return _Sp{ this->data(), _Count };
316          }
317
318      constexpr span<element_type, dynamic_extent>
319      first(size_type __count) const noexcept
320      {
321          __glibcxx_assert(__count <= size());
322          return { this->data(), __count };
323      }
324
325      template<size_t _Count>
326          constexpr span<element_type, _Count>
327          last() const noexcept
328          {
329            if constexpr (_Extent == dynamic_extent)
330              __glibcxx_assert(_Count <= size());
331            else
332              static_assert(_Count <= extent);
333            using _Sp = span<element_type, _Count>;
334            return _Sp{ this->data() + (this->size() - _Count), _Count };
335          }
336
337      constexpr span<element_type, dynamic_extent>
338      last(size_type __count) const noexcept
339      {
340          __glibcxx_assert(__count <= size());
341          return { this->data() + (this->size() - __count), __count };
342      }
343
344      template<size_t _Offset, size_t _Count = dynamic_extent>
345          constexpr auto
346          subspan() const noexcept
347          -> span<element_type, _S_subspan_extent<_Offset, _Count>()>
348          {
349            if constexpr (_Extent == dynamic_extent)
350              {
351                __glibcxx_assert(_Offset <= size());
352              }
353            else
354              static_assert(_Offset <= extent);
355
356            using _Sp = span<element_type, _S_subspan_extent<_Offset, _Count>()>;
357
358            if constexpr (_Count == dynamic_extent)
359              return _Sp{ this->data() + _Offset, this->size() - _Offset };
360            else
361              {
362                if constexpr (_Extent == dynamic_extent)
363                    {
364                      __glibcxx_assert(_Count <= size());
365                      __glibcxx_assert(_Count <= (size() - _Offset));
366                    }
367                else
368                    {
369                      static_assert(_Count <= extent);
370                      static_assert(_Count <= (extent - _Offset));
371                    }
372                return _Sp{ this->data() + _Offset, _Count };
373              }
374          }
375
376      constexpr span<element_type, dynamic_extent>
377      subspan(size_type __offset, size_type __count = dynamic_extent) const
378      noexcept
379      {
380          __glibcxx_assert(__offset <= size());
381          if (__count == dynamic_extent)
382            __count = this->size() - __offset;
383          else
384            {
385              __glibcxx_assert(__count <= size());
386              __glibcxx_assert(__offset + __count <= size());
387            }
388          return {this->data() + __offset, __count};
389      }
390
391    private:
392      pointer _M_ptr;
393      [[no_unique_address]] __detail::__extent_storage<extent> _M_extent;
394    };
395
396  // deduction guides
397
398  template<typename _Type, size_t _ArrayExtent>
399    span(_Type(&)[_ArrayExtent]) -> span<_Type, _ArrayExtent>;
400
401  template<typename _Type, size_t _ArrayExtent>
402    span(array<_Type, _ArrayExtent>&) -> span<_Type, _ArrayExtent>;
403
404  template<typename _Type, size_t _ArrayExtent>
405    span(const array<_Type, _ArrayExtent>&)
406      -> span<const _Type, _ArrayExtent>;
407
408  template<contiguous_iterator _Iter, typename _End>
409    span(_Iter, _End)
410      -> span<remove_reference_t<iter_reference_t<_Iter>>>;
411
412  template<ranges::contiguous_range _Range>
413    span(_Range &&)
414      -> span<remove_reference_t<ranges::range_reference_t<_Range&>>>;
415
416  template<typename _Type, size_t _Extent>
417    inline
418    span<const byte, _Extent == dynamic_extent
419          ? dynamic_extent : _Extent * sizeof(_Type)>
420    as_bytes(span<_Type, _Extent> __sp) noexcept
421    {
422      auto data = reinterpret_cast<const byte*>(__sp.data());
423      auto size = __sp.size_bytes();
424      constexpr auto extent = _Extent == dynamic_extent
425          ? dynamic_extent : _Extent * sizeof(_Type);
426      return span<const byte, extent>{data, size};
427    }
428
429  template<typename _Type, size_t _Extent>
430    requires (!is_const_v<_Type>)
431    inline
432    span<byte, _Extent == dynamic_extent
433       ? dynamic_extent : _Extent * sizeof(_Type)>
434    as_writable_bytes(span<_Type, _Extent> __sp) noexcept
435    {
436      auto data = reinterpret_cast<byte*>(__sp.data());
437      auto size = __sp.size_bytes();
438      constexpr auto extent = _Extent == dynamic_extent
439          ? dynamic_extent : _Extent * sizeof(_Type);
440      return span<byte, extent>{data, size};
441    }
442
443  namespace ranges
444  {
445    // Opt-in to borrowed_range concept
446    template<typename _ElementType, size_t _Extent>
447      inline constexpr bool
448          enable_borrowed_range<span<_ElementType, _Extent>> = true;
449
450    // Opt-in to view concept
451    template<typename _ElementType, size_t _Extent>
452      inline constexpr bool
453          enable_view<span<_ElementType, _Extent>> = true;
454  }
455_GLIBCXX_END_NAMESPACE_VERSION
456} // namespace std
457#endif // concepts
458#endif // C++20
459#endif // _GLIBCXX_SPAN
460