common/alspan.h

   1 #ifndef AL_SPAN_H
   2 #define AL_SPAN_H
   3
   4 #include <cassert>
   5 #include <cstddef>
   6 #include <iterator>
   7 #include <stdexcept>
   8 #include <tuple>
   9 #include <type_traits>
  10 #include <utility>
  11
  12 #include "alassert.h"
  13 #include "almalloc.h"
  14 #include "altraits.h"
  15
  16 namespace al {
  17
  18 /* This is here primarily to help ensure proper behavior for span's iterators,
  19  * being an actual object with member functions instead of a raw pointer (which
  20  * has requirements like + and - working with ptrdiff_t). This also helps
  21  * silence clang-tidy's pointer arithmetic warnings for span and FlexArray
  22  * iterators. It otherwise behaves like a plain pointer and should optimize
  23  * accordingly.
  24  *
  25  * Shouldn't be needed once we use std::span in C++20.
  26  */
  27 template<typename T>
  28 class ptr_wrapper {
  29     static_assert(std::is_pointer_v<T>);
  30     T mPointer{};
  31
  32 public:
  33     using value_type = std::remove_pointer_t<T>;
  34     using size_type = std::size_t;
  35     using difference_type = std::ptrdiff_t;
  36     using pointer = value_type*;
  37     using reference = value_type&;
  38     using iterator_category = std::random_access_iterator_tag;
  39
  40     explicit constexpr ptr_wrapper(T ptr) : mPointer{ptr} { }
  41
  42     /* NOLINTBEGIN(cppcoreguidelines-pro-bounds-pointer-arithmetic) */
  43     constexpr auto operator++() noexcept -> ptr_wrapper& { ++mPointer; return *this; }
  44     constexpr auto operator--() noexcept -> ptr_wrapper& { --mPointer; return *this; }
  45     constexpr auto operator++(int) noexcept -> ptr_wrapper
  46     {
  47         auto temp = *this;
  48         ++*this;
  49         return temp;
  50     }
  51     constexpr auto operator--(int) noexcept -> ptr_wrapper
  52     {
  53         auto temp = *this;
  54         --*this;
  55         return temp;
  56     }
  57
  58     constexpr
  59     auto operator+=(std::ptrdiff_t n) noexcept -> ptr_wrapper& { mPointer += n; return *this; }
  60     constexpr
  61     auto operator-=(std::ptrdiff_t n) noexcept -> ptr_wrapper& { mPointer -= n; return *this; }
  62
  63     [[nodiscard]] constexpr auto operator*() const noexcept -> value_type& { return *mPointer; }
  64     [[nodiscard]] constexpr auto operator->() const noexcept -> value_type* { return mPointer; }
  65     [[nodiscard]] constexpr
  66     auto operator[](std::size_t idx) const noexcept -> value_type& {return mPointer[idx];}
  67
  68     [[nodiscard]] friend constexpr
  69     auto operator+(const ptr_wrapper &lhs, std::ptrdiff_t n) noexcept -> ptr_wrapper
  70     { return ptr_wrapper{lhs.mPointer + n}; }
  71     [[nodiscard]] friend constexpr
  72     auto operator+(std::ptrdiff_t n, const ptr_wrapper &rhs) noexcept -> ptr_wrapper
  73     { return ptr_wrapper{n + rhs.mPointer}; }
  74     [[nodiscard]] friend constexpr
  75     auto operator-(const ptr_wrapper &lhs, std::ptrdiff_t n) noexcept -> ptr_wrapper
  76     { return ptr_wrapper{lhs.mPointer - n}; }
  77
  78     [[nodiscard]] friend constexpr
  79     auto operator-(const ptr_wrapper &lhs, const ptr_wrapper &rhs)noexcept->std::ptrdiff_t
  80     { return lhs.mPointer - rhs.mPointer; }
  81
  82     [[nodiscard]] friend constexpr
  83     auto operator==(const ptr_wrapper &lhs, const ptr_wrapper &rhs) noexcept -> bool
  84     { return lhs.mPointer == rhs.mPointer; }
  85     [[nodiscard]] friend constexpr
  86     auto operator!=(const ptr_wrapper &lhs, const ptr_wrapper &rhs) noexcept -> bool
  87     { return lhs.mPointer != rhs.mPointer; }
  88     [[nodiscard]] friend constexpr
  89     auto operator<=(const ptr_wrapper &lhs, const ptr_wrapper &rhs) noexcept -> bool
  90     { return lhs.mPointer <= rhs.mPointer; }
  91     [[nodiscard]] friend constexpr
  92     auto operator>=(const ptr_wrapper &lhs, const ptr_wrapper &rhs) noexcept -> bool
  93     { return lhs.mPointer >= rhs.mPointer; }
  94     [[nodiscard]] friend constexpr
  95     auto operator<(const ptr_wrapper &lhs, const ptr_wrapper &rhs) noexcept -> bool
  96     { return lhs.mPointer < rhs.mPointer; }
  97     [[nodiscard]] friend constexpr
  98     auto operator>(const ptr_wrapper &lhs, const ptr_wrapper &rhs) noexcept -> bool
  99     { return lhs.mPointer > rhs.mPointer; }
 100     /* NOLINTEND(cppcoreguidelines-pro-bounds-pointer-arithmetic) */
 101 };
 102
 103
 104 inline constexpr std::size_t dynamic_extent{static_cast<std::size_t>(-1)};
 105
 106 template<typename T, std::size_t E=dynamic_extent>
 107 class span;
 108
 109 namespace detail_ {
 110     template<typename T>
 111     struct is_span_ : std::false_type { };
 112     template<typename T, std::size_t E>
 113     struct is_span_<span<T,E>> : std::true_type { };
 114     template<typename T>
 115     inline constexpr bool is_span_v = is_span_<std::remove_cv_t<T>>::value;
 116
 117     template<typename T>
 118     struct is_std_array_ : std::false_type { };
 119     template<typename T, std::size_t N>
 120     struct is_std_array_<std::array<T,N>> : std::true_type { };
 121     template<typename T>
 122     inline constexpr bool is_std_array_v = is_std_array_<std::remove_cv_t<T>>::value;
 123
 124     template<typename T, typename = void>
 125     inline constexpr bool has_size_and_data = false;
 126     template<typename T>
 127     inline constexpr bool has_size_and_data<T,
 128         std::void_t<decltype(std::size(std::declval<T>())),decltype(std::data(std::declval<T>()))>>
 129         = true;
 130
 131     template<typename C>
 132     inline constexpr bool is_valid_container_type = !is_span_v<C> && !is_std_array_v<C>
 133         && !std::is_array<C>::value && has_size_and_data<C>;
 134
 135     template<typename T, typename U>
 136     inline constexpr bool is_array_compatible = std::is_convertible<T(*)[],U(*)[]>::value; /* NOLINT(*-avoid-c-arrays) */
 137
 138     template<typename C, typename T>
 139     inline constexpr bool is_valid_container = is_valid_container_type<C>
 140         && is_array_compatible<std::remove_pointer_t<decltype(std::data(std::declval<C&>()))>,T>;
 141 } // namespace detail_
 142
 143 #define REQUIRES(...) std::enable_if_t<(__VA_ARGS__),bool> = true
 144
 145 template<typename T, std::size_t E>
 146 class span {
 147 public:
 148     using element_type = T;
 149     using value_type = std::remove_cv_t<T>;
 150     using size_type = std::size_t;
 151     using difference_type = std::ptrdiff_t;
 152
 153     using pointer = T*;
 154     using const_pointer = const T*;
 155     using reference = T&;
 156     using const_reference = const T&;
 157
 158     using iterator = ptr_wrapper<pointer>;
 159     using const_iterator = ptr_wrapper<const_pointer>;
 160     using reverse_iterator = std::reverse_iterator<iterator>;
 161     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 162
 163     static constexpr std::size_t extent{E};
 164
 165     template<bool is0=(extent == 0), REQUIRES(is0)>
 166     constexpr span() noexcept { }
 167     template<typename U>
 168     constexpr explicit span(U iter, size_type size_) : mData{::al::to_address(iter)}
 169     { alassert(size_ == extent); }
 170     template<typename U, typename V, REQUIRES(!std::is_convertible<V,std::size_t>::value)>
 171     constexpr explicit span(U first, V last) : mData{::al::to_address(first)}
 172     { alassert(static_cast<std::size_t>(last-first) == extent); }
 173
 174     template<std::size_t N>
 175     constexpr span(type_identity_t<element_type> (&arr)[N]) noexcept /* NOLINT(*-avoid-c-arrays) */
 176         : mData{std::data(arr)}
 177     { static_assert(N == extent); }
 178     template<std::size_t N>
 179     constexpr span(std::array<value_type,N> &arr) noexcept : mData{std::data(arr)}
 180     { static_assert(N == extent); }
 181     template<typename U=T, std::size_t N, REQUIRES(std::is_const<U>::value)>
 182     constexpr span(const std::array<value_type,N> &arr) noexcept : mData{std::data(arr)}
 183     { static_assert(N == extent); }
 184
 185     template<typename U, REQUIRES(detail_::is_valid_container<U, element_type>)>
 186     constexpr explicit span(U&& cont) : span{std::data(cont), std::size(cont)} { }
 187
 188     template<typename U, std::size_t N, REQUIRES(!std::is_same<element_type,U>::value
 189         && detail_::is_array_compatible<U,element_type> && N == dynamic_extent)>
 190     constexpr explicit span(const span<U,N> &span_) noexcept : mData{std::data(span_)}
 191     { alassert(std::size(span_) == extent); }
 192     template<typename U, std::size_t N, REQUIRES(!std::is_same<element_type,U>::value
 193         && detail_::is_array_compatible<U,element_type> && N == extent)>
 194     constexpr span(const span<U,N> &span_) noexcept : mData{std::data(span_)} { }
 195     constexpr span(const span&) noexcept = default;
 196
 197     constexpr span& operator=(const span &rhs) noexcept = default;
 198
 199     [[nodiscard]] constexpr auto front() const -> reference { return mData[0]; }
 200     [[nodiscard]] constexpr auto back() const -> reference { return mData[E-1]; }
 201     [[nodiscard]] constexpr auto operator[](size_type idx) const -> reference { return mData[idx]; }
 202     [[nodiscard]] constexpr auto data() const noexcept -> pointer { return mData; }
 203
 204     [[nodiscard]] constexpr auto size() const noexcept -> size_type { return E; }
 205     [[nodiscard]] constexpr auto size_bytes() const noexcept -> size_type { return E * sizeof(value_type); }
 206     [[nodiscard]] constexpr auto empty() const noexcept -> bool { return E == 0; }
 207
 208     [[nodiscard]] constexpr auto begin() const noexcept -> iterator { return iterator{mData}; }
 209     [[nodiscard]] constexpr auto end() const noexcept -> iterator { return iterator{mData+E}; }
 210     [[nodiscard]] constexpr
 211     auto cbegin() const noexcept -> const_iterator { return const_iterator{mData}; }
 212     [[nodiscard]] constexpr
 213     auto cend() const noexcept -> const_iterator { return const_iterator{mData+E}; }
 214
 215     [[nodiscard]] constexpr
 216     auto rbegin() const noexcept -> reverse_iterator { return reverse_iterator{end()}; }
 217     [[nodiscard]] constexpr
 218     auto rend() const noexcept -> reverse_iterator { return reverse_iterator{begin()}; }
 219     [[nodiscard]] constexpr
 220     auto crbegin() const noexcept -> const_reverse_iterator { return cend(); }
 221     [[nodiscard]] constexpr
 222     auto crend() const noexcept -> const_reverse_iterator { return cbegin(); }
 223
 224     template<std::size_t C>
 225     [[nodiscard]] constexpr auto first() const noexcept -> span<element_type,C>
 226     {
 227         static_assert(E >= C, "New size exceeds original capacity");
 228         return span<element_type,C>{mData, C};
 229     }
 230
 231     template<std::size_t C>
 232     [[nodiscard]] constexpr auto last() const noexcept -> span<element_type,C>
 233     {
 234         static_assert(E >= C, "New size exceeds original capacity");
 235         return span<element_type,C>{mData+(E-C), C};
 236     }
 237
 238     template<std::size_t O, std::size_t C>
 239     [[nodiscard]] constexpr
 240     auto subspan() const noexcept -> std::enable_if_t<C!=dynamic_extent,span<element_type,C>>
 241     {
 242         static_assert(E >= O, "Offset exceeds extent");
 243         static_assert(E-O >= C, "New size exceeds original capacity");
 244         return span<element_type,C>{mData+O, C};
 245     }
 246
 247     template<std::size_t O, std::size_t C=dynamic_extent>
 248     [[nodiscard]] constexpr
 249     auto subspan() const noexcept -> std::enable_if_t<C==dynamic_extent,span<element_type,E-O>>
 250     {
 251         static_assert(E >= O, "Offset exceeds extent");
 252         return span<element_type,E-O>{mData+O, E-O};
 253     }
 254
 255     /* NOTE: Can't declare objects of a specialized template class prior to
 256      * defining the specialization. As a result, these methods need to be
 257      * defined later.
 258      */
 259     [[nodiscard]] constexpr
 260     auto first(std::size_t count) const noexcept -> span<element_type,dynamic_extent>;
 261     [[nodiscard]] constexpr
 262     auto last(std::size_t count) const noexcept -> span<element_type,dynamic_extent>;
 263     [[nodiscard]] constexpr
 264     auto subspan(std::size_t offset, std::size_t count=dynamic_extent) const noexcept
 265         -> span<element_type,dynamic_extent>;
 266
 267 private:
 268     pointer mData{nullptr};
 269 };
 270
 271 template<typename T>
 272 class span<T,dynamic_extent> {
 273 public:
 274     using element_type = T;
 275     using value_type = std::remove_cv_t<T>;
 276     using size_type = std::size_t;
 277     using difference_type = ptrdiff_t;
 278
 279     using pointer = T*;
 280     using const_pointer = const T*;
 281     using reference = T&;
 282     using const_reference = const T&;
 283
 284     using iterator = ptr_wrapper<pointer>;
 285     using const_iterator = ptr_wrapper<const_pointer>;
 286     using reverse_iterator = std::reverse_iterator<iterator>;
 287     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 288
 289     static constexpr std::size_t extent{dynamic_extent};
 290
 291     constexpr span() noexcept = default;
 292     template<typename U>
 293     constexpr span(U iter, size_type count) : mData{::al::to_address(iter)}, mDataLength{count}
 294     { }
 295     template<typename U, typename V, REQUIRES(!std::is_convertible<V,std::size_t>::value)>
 296     constexpr span(U first, V last)
 297         : span{::al::to_address(first), static_cast<std::size_t>(last-first)}
 298     { }
 299
 300     template<std::size_t N>
 301     constexpr span(type_identity_t<element_type> (&arr)[N]) noexcept /* NOLINT(*-avoid-c-arrays) */
 302         : mData{std::data(arr)}, mDataLength{std::size(arr)}
 303     { }
 304     template<std::size_t N>
 305     constexpr span(std::array<value_type,N> &arr) noexcept
 306         : mData{std::data(arr)}, mDataLength{std::size(arr)}
 307     { }
 308     template<std::size_t N, typename U=T, REQUIRES(std::is_const<U>::value)>
 309     constexpr span(const std::array<value_type,N> &arr) noexcept
 310         : mData{std::data(arr)}, mDataLength{std::size(arr)}
 311     { }
 312
 313     template<typename U, REQUIRES(detail_::is_valid_container<U, element_type>)>
 314     constexpr span(U&& cont) : span{std::data(cont), std::size(cont)} { }
 315
 316     template<typename U, std::size_t N, REQUIRES(detail_::is_array_compatible<U,element_type>
 317         && (!std::is_same<element_type,U>::value || extent != N))>
 318     constexpr span(const span<U,N> &span_) noexcept : span{std::data(span_), std::size(span_)} { }
 319     constexpr span(const span&) noexcept = default;
 320
 321     constexpr span& operator=(const span &rhs) noexcept = default;
 322
 323     [[nodiscard]] constexpr auto front() const -> reference { return mData[0]; }
 324     [[nodiscard]] constexpr auto back() const -> reference { return mData[mDataLength-1]; }
 325     [[nodiscard]] constexpr auto operator[](size_type idx) const -> reference {return mData[idx];}
 326     [[nodiscard]] constexpr auto data() const noexcept -> pointer { return mData; }
 327
 328     [[nodiscard]] constexpr auto size() const noexcept -> size_type { return mDataLength; }
 329     [[nodiscard]] constexpr
 330     auto size_bytes() const noexcept -> size_type { return mDataLength * sizeof(value_type); }
 331     [[nodiscard]] constexpr auto empty() const noexcept -> bool { return mDataLength == 0; }
 332
 333     [[nodiscard]] constexpr auto begin() const noexcept -> iterator { return iterator{mData}; }
 334     [[nodiscard]] constexpr
 335     auto end() const noexcept -> iterator { return iterator{mData+mDataLength}; }
 336     [[nodiscard]] constexpr
 337     auto cbegin() const noexcept -> const_iterator { return const_iterator{mData}; }
 338     [[nodiscard]] constexpr
 339     auto cend() const noexcept -> const_iterator { return const_iterator{mData+mDataLength}; }
 340
 341     [[nodiscard]] constexpr
 342     auto rbegin() const noexcept -> reverse_iterator { return reverse_iterator{end()}; }
 343     [[nodiscard]] constexpr
 344     auto rend() const noexcept -> reverse_iterator { return reverse_iterator{begin()}; }
 345     [[nodiscard]] constexpr
 346     auto crbegin() const noexcept -> const_reverse_iterator { return cend(); }
 347     [[nodiscard]] constexpr
 348     auto crend() const noexcept -> const_reverse_iterator { return cbegin(); }
 349
 350     template<std::size_t C>
 351     [[nodiscard]] constexpr auto first() const noexcept -> span<element_type,C>
 352     {
 353         assert(C <= mDataLength);
 354         return span<element_type,C>{mData, C};
 355     }
 356
 357     [[nodiscard]] constexpr auto first(std::size_t count) const noexcept -> span
 358     {
 359         assert(count <= mDataLength);
 360         return span{mData, count};
 361     }
 362
 363     template<std::size_t C>
 364     [[nodiscard]] constexpr auto last() const noexcept -> span<element_type,C>
 365     {
 366         assert(C <= mDataLength);
 367         return span<element_type,C>{mData+mDataLength-C, C};
 368     }
 369
 370     [[nodiscard]] constexpr auto last(std::size_t count) const noexcept -> span
 371     {
 372         assert(count <= mDataLength);
 373         return span{mData+mDataLength-count, count};
 374     }
 375
 376     template<std::size_t O, std::size_t C>
 377     [[nodiscard]] constexpr
 378     auto subspan() const noexcept -> std::enable_if_t<C!=dynamic_extent,span<element_type,C>>
 379     {
 380         assert(O <= mDataLength);
 381         assert(C <= mDataLength-O);
 382         return span<element_type,C>{mData+O, C};
 383     }
 384
 385     template<std::size_t O, std::size_t C=dynamic_extent>
 386     [[nodiscard]] constexpr
 387     auto subspan() const noexcept -> std::enable_if_t<C==dynamic_extent,span<element_type,C>>
 388     {
 389         assert(O <= mDataLength);
 390         return span<element_type,C>{mData+O, mDataLength-O};
 391     }
 392
 393     [[nodiscard]] constexpr
 394     auto subspan(std::size_t offset, std::size_t count=dynamic_extent) const noexcept -> span
 395     {
 396         assert(offset <= mDataLength);
 397         if(count != dynamic_extent)
 398         {
 399             assert(count <= mDataLength-offset);
 400             return span{mData+offset, count};
 401         }
 402         return span{mData+offset, mDataLength-offset};
 403     }
 404
 405 private:
 406     pointer mData{nullptr};
 407     size_type mDataLength{0};
 408 };
 409
 410 template<typename T, std::size_t E>
 411 [[nodiscard]] constexpr
 412 auto span<T,E>::first(std::size_t count) const noexcept -> span<element_type,dynamic_extent>
 413 {
 414     assert(count <= size());
 415     return span<element_type>{mData, count};
 416 }
 417
 418 template<typename T, std::size_t E>
 419 [[nodiscard]] constexpr
 420 auto span<T,E>::last(std::size_t count) const noexcept -> span<element_type,dynamic_extent>
 421 {
 422     assert(count <= size());
 423     return span<element_type>{mData+size()-count, count};
 424 }
 425
 426 template<typename T, std::size_t E>
 427 [[nodiscard]] constexpr
 428 auto span<T,E>::subspan(std::size_t offset, std::size_t count) const noexcept
 429     -> span<element_type,dynamic_extent>
 430 {
 431     assert(offset <= size());
 432     if(count != dynamic_extent)
 433     {
 434         assert(count <= size()-offset);
 435         return span<element_type>{mData+offset, count};
 436     }
 437     return span<element_type>{mData+offset, size()-offset};
 438 }
 439
 440
 441 template<typename T, typename EndOrSize>
 442 span(T, EndOrSize) -> span<std::remove_reference_t<decltype(*std::declval<T&>())>>;
 443
 444 template<typename T, std::size_t N>
 445 span(T (&)[N]) -> span<T, N>; /* NOLINT(*-avoid-c-arrays) */
 446
 447 template<typename T, std::size_t N>
 448 span(std::array<T, N>&) -> span<T, N>;
 449
 450 template<typename T, std::size_t N>
 451 span(const std::array<T, N>&) -> span<const T, N>;
 452
 453 template<typename C, REQUIRES(detail_::is_valid_container_type<C>)>
 454 span(C&&) -> span<std::remove_pointer_t<decltype(std::data(std::declval<C&>()))>>;
 455
 456 #undef REQUIRES
 457
 458 } // namespace al
 459
 460 #endif /* AL_SPAN_H */