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 auto rbegin() const noexcept -> reverse_iterator { return end(); }
 216     [[nodiscard]] constexpr auto rend() const noexcept -> reverse_iterator { return begin(); }
 217     [[nodiscard]] constexpr
 218     auto crbegin() const noexcept -> const_reverse_iterator { return cend(); }
 219     [[nodiscard]] constexpr
 220     auto crend() const noexcept -> const_reverse_iterator { return cbegin(); }
 221
 222     template<std::size_t C>
 223     [[nodiscard]] constexpr auto first() const noexcept -> span<element_type,C>
 224     {
 225         static_assert(E >= C, "New size exceeds original capacity");
 226         return span<element_type,C>{mData, C};
 227     }
 228
 229     template<std::size_t C>
 230     [[nodiscard]] constexpr auto last() const noexcept -> span<element_type,C>
 231     {
 232         static_assert(E >= C, "New size exceeds original capacity");
 233         return span<element_type,C>{mData+(E-C), C};
 234     }
 235
 236     template<std::size_t O, std::size_t C>
 237     [[nodiscard]] constexpr
 238     auto subspan() const noexcept -> std::enable_if_t<C!=dynamic_extent,span<element_type,C>>
 239     {
 240         static_assert(E >= O, "Offset exceeds extent");
 241         static_assert(E-O >= C, "New size exceeds original capacity");
 242         return span<element_type,C>{mData+O, C};
 243     }
 244
 245     template<std::size_t O, std::size_t C=dynamic_extent>
 246     [[nodiscard]] constexpr
 247     auto subspan() const noexcept -> std::enable_if_t<C==dynamic_extent,span<element_type,E-O>>
 248     {
 249         static_assert(E >= O, "Offset exceeds extent");
 250         return span<element_type,E-O>{mData+O, E-O};
 251     }
 252
 253     /* NOTE: Can't declare objects of a specialized template class prior to
 254      * defining the specialization. As a result, these methods need to be
 255      * defined later.
 256      */
 257     [[nodiscard]] constexpr
 258     auto first(std::size_t count) const noexcept -> span<element_type,dynamic_extent>;
 259     [[nodiscard]] constexpr
 260     auto last(std::size_t count) const noexcept -> span<element_type,dynamic_extent>;
 261     [[nodiscard]] constexpr
 262     auto subspan(std::size_t offset, std::size_t count=dynamic_extent) const noexcept
 263         -> span<element_type,dynamic_extent>;
 264
 265 private:
 266     pointer mData{nullptr};
 267 };
 268
 269 template<typename T>
 270 class span<T,dynamic_extent> {
 271 public:
 272     using element_type = T;
 273     using value_type = std::remove_cv_t<T>;
 274     using size_type = std::size_t;
 275     using difference_type = ptrdiff_t;
 276
 277     using pointer = T*;
 278     using const_pointer = const T*;
 279     using reference = T&;
 280     using const_reference = const T&;
 281
 282     using iterator = ptr_wrapper<pointer>;
 283     using const_iterator = ptr_wrapper<const_pointer>;
 284     using reverse_iterator = std::reverse_iterator<iterator>;
 285     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 286
 287     static constexpr std::size_t extent{dynamic_extent};
 288
 289     constexpr span() noexcept = default;
 290     template<typename U>
 291     constexpr span(U iter, size_type count) : mData{::al::to_address(iter)}, mDataLength{count}
 292     { }
 293     template<typename U, typename V, REQUIRES(!std::is_convertible<V,std::size_t>::value)>
 294     constexpr span(U first, V last)
 295         : span{::al::to_address(first), static_cast<std::size_t>(last-first)}
 296     { }
 297
 298     template<std::size_t N>
 299     constexpr span(type_identity_t<element_type> (&arr)[N]) noexcept /* NOLINT(*-avoid-c-arrays) */
 300         : mData{std::data(arr)}, mDataLength{std::size(arr)}
 301     { }
 302     template<std::size_t N>
 303     constexpr span(std::array<value_type,N> &arr) noexcept
 304         : mData{std::data(arr)}, mDataLength{std::size(arr)}
 305     { }
 306     template<std::size_t N, typename U=T, REQUIRES(std::is_const<U>::value)>
 307     constexpr span(const std::array<value_type,N> &arr) noexcept
 308         : mData{std::data(arr)}, mDataLength{std::size(arr)}
 309     { }
 310
 311     template<typename U, REQUIRES(detail_::is_valid_container<U, element_type>)>
 312     constexpr span(U&& cont) : span{std::data(cont), std::size(cont)} { }
 313
 314     template<typename U, std::size_t N, REQUIRES(detail_::is_array_compatible<U,element_type>
 315         && (!std::is_same<element_type,U>::value || extent != N))>
 316     constexpr span(const span<U,N> &span_) noexcept : span{std::data(span_), std::size(span_)} { }
 317     constexpr span(const span&) noexcept = default;
 318
 319     constexpr span& operator=(const span &rhs) noexcept = default;
 320
 321     [[nodiscard]] constexpr auto front() const -> reference { return mData[0]; }
 322     [[nodiscard]] constexpr auto back() const -> reference { return mData[mDataLength-1]; }
 323     [[nodiscard]] constexpr auto operator[](size_type idx) const -> reference {return mData[idx];}
 324     [[nodiscard]] constexpr auto data() const noexcept -> pointer { return mData; }
 325
 326     [[nodiscard]] constexpr auto size() const noexcept -> size_type { return mDataLength; }
 327     [[nodiscard]] constexpr
 328     auto size_bytes() const noexcept -> size_type { return mDataLength * sizeof(value_type); }
 329     [[nodiscard]] constexpr auto empty() const noexcept -> bool { return mDataLength == 0; }
 330
 331     [[nodiscard]] constexpr auto begin() const noexcept -> iterator { return iterator{mData}; }
 332     [[nodiscard]] constexpr
 333     auto end() const noexcept -> iterator { return iterator{mData+mDataLength}; }
 334     [[nodiscard]] constexpr
 335     auto cbegin() const noexcept -> const_iterator { return const_iterator{mData}; }
 336     [[nodiscard]] constexpr
 337     auto cend() const noexcept -> const_iterator { return const_iterator{mData+mDataLength}; }
 338
 339     [[nodiscard]] constexpr auto rbegin() const noexcept -> reverse_iterator { return end(); }
 340     [[nodiscard]] constexpr auto rend() const noexcept -> reverse_iterator { return begin(); }
 341     [[nodiscard]] constexpr
 342     auto crbegin() const noexcept -> const_reverse_iterator { return cend(); }
 343     [[nodiscard]] constexpr
 344     auto crend() const noexcept -> const_reverse_iterator { return cbegin(); }
 345
 346     template<std::size_t C>
 347     [[nodiscard]] constexpr auto first() const noexcept -> span<element_type,C>
 348     {
 349         assert(C <= mDataLength);
 350         return span<element_type,C>{mData, C};
 351     }
 352
 353     [[nodiscard]] constexpr auto first(std::size_t count) const noexcept -> span
 354     {
 355         assert(count <= mDataLength);
 356         return span{mData, count};
 357     }
 358
 359     template<std::size_t C>
 360     [[nodiscard]] constexpr auto last() const noexcept -> span<element_type,C>
 361     {
 362         assert(C <= mDataLength);
 363         return span<element_type,C>{mData+mDataLength-C, C};
 364     }
 365
 366     [[nodiscard]] constexpr auto last(std::size_t count) const noexcept -> span
 367     {
 368         assert(count <= mDataLength);
 369         return span{mData+mDataLength-count, count};
 370     }
 371
 372     template<std::size_t O, std::size_t C>
 373     [[nodiscard]] constexpr
 374     auto subspan() const noexcept -> std::enable_if_t<C!=dynamic_extent,span<element_type,C>>
 375     {
 376         assert(O <= mDataLength);
 377         assert(C <= mDataLength-O);
 378         return span<element_type,C>{mData+O, C};
 379     }
 380
 381     template<std::size_t O, std::size_t C=dynamic_extent>
 382     [[nodiscard]] constexpr
 383     auto subspan() const noexcept -> std::enable_if_t<C==dynamic_extent,span<element_type,C>>
 384     {
 385         assert(O <= mDataLength);
 386         return span<element_type,C>{mData+O, mDataLength-O};
 387     }
 388
 389     [[nodiscard]] constexpr
 390     auto subspan(std::size_t offset, std::size_t count=dynamic_extent) const noexcept -> span
 391     {
 392         assert(offset <= mDataLength);
 393         if(count != dynamic_extent)
 394         {
 395             assert(count <= mDataLength-offset);
 396             return span{mData+offset, count};
 397         }
 398         return span{mData+offset, mDataLength-offset};
 399     }
 400
 401 private:
 402     pointer mData{nullptr};
 403     size_type mDataLength{0};
 404 };
 405
 406 template<typename T, std::size_t E>
 407 [[nodiscard]] constexpr
 408 auto span<T,E>::first(std::size_t count) const noexcept -> span<element_type,dynamic_extent>
 409 {
 410     assert(count <= size());
 411     return span<element_type>{mData, count};
 412 }
 413
 414 template<typename T, std::size_t E>
 415 [[nodiscard]] constexpr
 416 auto span<T,E>::last(std::size_t count) const noexcept -> span<element_type,dynamic_extent>
 417 {
 418     assert(count <= size());
 419     return span<element_type>{mData+size()-count, count};
 420 }
 421
 422 template<typename T, std::size_t E>
 423 [[nodiscard]] constexpr
 424 auto span<T,E>::subspan(std::size_t offset, std::size_t count) const noexcept
 425     -> span<element_type,dynamic_extent>
 426 {
 427     assert(offset <= size());
 428     if(count != dynamic_extent)
 429     {
 430         assert(count <= size()-offset);
 431         return span<element_type>{mData+offset, count};
 432     }
 433     return span<element_type>{mData+offset, size()-offset};
 434 }
 435
 436
 437 template<typename T, typename EndOrSize>
 438 span(T, EndOrSize) -> span<std::remove_reference_t<decltype(*std::declval<T&>())>>;
 439
 440 template<typename T, std::size_t N>
 441 span(T (&)[N]) -> span<T, N>; /* NOLINT(*-avoid-c-arrays) */
 442
 443 template<typename T, std::size_t N>
 444 span(std::array<T, N>&) -> span<T, N>;
 445
 446 template<typename T, std::size_t N>
 447 span(const std::array<T, N>&) -> span<const T, N>;
 448
 449 template<typename C, REQUIRES(detail_::is_valid_container_type<C>)>
 450 span(C&&) -> span<std::remove_pointer_t<decltype(std::data(std::declval<C&>()))>>;
 451
 452 #undef REQUIRES
 453
 454 } // namespace al
 455
 456 #endif /* AL_SPAN_H */