common/alspan.h

   1 #ifndef AL_SPAN_H
   2 #define AL_SPAN_H
   3
   4 #include <array>
   5 #include <cstddef>
   6 #include <initializer_list>
   7 #include <iterator>
   8 #include <type_traits>
   9
  10 #include "almalloc.h"
  11 #include "altraits.h"
  12
  13 namespace al {
  14
  15 template<typename T>
  16 constexpr auto size(const T &cont) noexcept(noexcept(cont.size())) -> decltype(cont.size())
  17 { return cont.size(); }
  18
  19 template<typename T, size_t N>
  20 constexpr size_t size(const T (&)[N]) noexcept
  21 { return N; }
  22
  23
  24 template<typename T>
  25 constexpr auto data(T &cont) noexcept(noexcept(cont.data())) -> decltype(cont.data())
  26 { return cont.data(); }
  27
  28 template<typename T>
  29 constexpr auto data(const T &cont) noexcept(noexcept(cont.data())) -> decltype(cont.data())
  30 { return cont.data(); }
  31
  32 template<typename T, size_t N>
  33 constexpr T* data(T (&arr)[N]) noexcept
  34 { return arr; }
  35
  36 template<typename T>
  37 constexpr const T* data(std::initializer_list<T> list) noexcept
  38 { return list.begin(); }
  39
  40
  41 constexpr size_t dynamic_extent{static_cast<size_t>(-1)};
  42
  43 template<typename T, size_t E=dynamic_extent>
  44 class span;
  45
  46 namespace detail_ {
  47     template<typename... Ts>
  48     using void_t = void;
  49
  50     template<typename T>
  51     struct is_span_ : std::false_type { };
  52     template<typename T, size_t E>
  53     struct is_span_<span<T,E>> : std::true_type { };
  54     template<typename T>
  55     constexpr bool is_span_v = is_span_<std::remove_cv_t<T>>::value;
  56
  57     template<typename T>
  58     struct is_std_array_ : std::false_type { };
  59     template<typename T, size_t N>
  60     struct is_std_array_<std::array<T,N>> : std::true_type { };
  61     template<typename T>
  62     constexpr bool is_std_array_v = is_std_array_<std::remove_cv_t<T>>::value;
  63
  64     template<typename T, typename = void>
  65     constexpr bool has_size_and_data = false;
  66     template<typename T>
  67     constexpr bool has_size_and_data<T,
  68         void_t<decltype(al::size(std::declval<T>())), decltype(al::data(std::declval<T>()))>>
  69         = true;
  70
  71     template<typename T, typename U>
  72     constexpr bool is_array_compatible = std::is_convertible<T(*)[],U(*)[]>::value;
  73
  74     template<typename C, typename T>
  75     constexpr bool is_valid_container = !is_span_v<C> && !is_std_array_v<C>
  76         && !std::is_array<C>::value && has_size_and_data<C>
  77         && is_array_compatible<std::remove_pointer_t<decltype(al::data(std::declval<C&>()))>,T>;
  78 } // namespace detail_
  79
  80 #define REQUIRES(...) std::enable_if_t<(__VA_ARGS__),bool> = true
  81
  82 template<typename T, size_t E>
  83 class span {
  84 public:
  85     using element_type = T;
  86     using value_type = std::remove_cv_t<T>;
  87     using index_type = size_t;
  88     using difference_type = ptrdiff_t;
  89
  90     using pointer = T*;
  91     using const_pointer = const T*;
  92     using reference = T&;
  93     using const_reference = const T&;
  94
  95     using iterator = pointer;
  96     using const_iterator = const_pointer;
  97     using reverse_iterator = std::reverse_iterator<iterator>;
  98     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
  99
 100     static constexpr size_t extent{E};
 101
 102     template<bool is0=(extent == 0), REQUIRES(is0)>
 103     constexpr span() noexcept { }
 104     template<typename U>
 105     constexpr explicit span(U iter, index_type) : mData{to_address(iter)} { }
 106     template<typename U, typename V, REQUIRES(!std::is_convertible<V,size_t>::value)>
 107     constexpr explicit span(U first, V) : mData{to_address(first)} { }
 108
 109     constexpr span(type_identity_t<element_type> (&arr)[E]) noexcept
 110         : span{al::data(arr), al::size(arr)}
 111     { }
 112     constexpr span(std::array<value_type,E> &arr) noexcept : span{al::data(arr), al::size(arr)} { }
 113     template<typename U=T, REQUIRES(std::is_const<U>::value)>
 114     constexpr span(const std::array<value_type,E> &arr) noexcept
 115       : span{al::data(arr), al::size(arr)}
 116     { }
 117
 118     template<typename U, REQUIRES(detail_::is_valid_container<U, element_type>)>
 119     constexpr explicit span(U&& cont) : span{al::data(cont), al::size(cont)} { }
 120
 121     template<typename U, index_type N, REQUIRES(!std::is_same<element_type,U>::value
 122         && detail_::is_array_compatible<U,element_type> && N == dynamic_extent)>
 123     constexpr explicit span(const span<U,N> &span_) noexcept
 124         : span{al::data(span_), al::size(span_)}
 125     { }
 126     template<typename U, index_type N, REQUIRES(!std::is_same<element_type,U>::value
 127         && detail_::is_array_compatible<U,element_type> && N == extent)>
 128     constexpr span(const span<U,N> &span_) noexcept : span{al::data(span_), al::size(span_)} { }
 129     constexpr span(const span&) noexcept = default;
 130
 131     constexpr span& operator=(const span &rhs) noexcept = default;
 132
 133     constexpr reference front() const { return *mData; }
 134     constexpr reference back() const { return *(mData+E-1); }
 135     constexpr reference operator[](index_type idx) const { return mData[idx]; }
 136     constexpr pointer data() const noexcept { return mData; }
 137
 138     constexpr index_type size() const noexcept { return E; }
 139     constexpr index_type size_bytes() const noexcept { return E * sizeof(value_type); }
 140     constexpr bool empty() const noexcept { return E == 0; }
 141
 142     constexpr iterator begin() const noexcept { return mData; }
 143     constexpr iterator end() const noexcept { return mData+E; }
 144     constexpr const_iterator cbegin() const noexcept { return mData; }
 145     constexpr const_iterator cend() const noexcept { return mData+E; }
 146
 147     constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; }
 148     constexpr reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; }
 149     constexpr const_reverse_iterator crbegin() const noexcept
 150     { return const_reverse_iterator{cend()}; }
 151     constexpr const_reverse_iterator crend() const noexcept
 152     { return const_reverse_iterator{cbegin()}; }
 153
 154     template<size_t C>
 155     constexpr span<element_type,C> first() const
 156     {
 157         static_assert(E >= C, "New size exceeds original capacity");
 158         return span<element_type,C>{mData, C};
 159     }
 160
 161     template<size_t C>
 162     constexpr span<element_type,C> last() const
 163     {
 164         static_assert(E >= C, "New size exceeds original capacity");
 165         return span<element_type,C>{mData+(E-C), C};
 166     }
 167
 168     template<size_t O, size_t C>
 169     constexpr auto subspan() const -> std::enable_if_t<C!=dynamic_extent,span<element_type,C>>
 170     {
 171         static_assert(E >= O, "Offset exceeds extent");
 172         static_assert(E-O >= C, "New size exceeds original capacity");
 173         return span<element_type,C>{mData+O, C};
 174     }
 175
 176     template<size_t O, size_t C=dynamic_extent>
 177     constexpr auto subspan() const -> std::enable_if_t<C==dynamic_extent,span<element_type,E-O>>
 178     {
 179         static_assert(E >= O, "Offset exceeds extent");
 180         return span<element_type,E-O>{mData+O, E-O};
 181     }
 182
 183     /* NOTE: Can't declare objects of a specialized template class prior to
 184      * defining the specialization. As a result, these methods need to be
 185      * defined later.
 186      */
 187     constexpr span<element_type,dynamic_extent> first(size_t count) const;
 188     constexpr span<element_type,dynamic_extent> last(size_t count) const;
 189     constexpr span<element_type,dynamic_extent> subspan(size_t offset,
 190         size_t count=dynamic_extent) const;
 191
 192 private:
 193     pointer mData{nullptr};
 194 };
 195
 196 template<typename T>
 197 class span<T,dynamic_extent> {
 198 public:
 199     using element_type = T;
 200     using value_type = std::remove_cv_t<T>;
 201     using index_type = size_t;
 202     using difference_type = ptrdiff_t;
 203
 204     using pointer = T*;
 205     using const_pointer = const T*;
 206     using reference = T&;
 207     using const_reference = const T&;
 208
 209     using iterator = pointer;
 210     using const_iterator = const_pointer;
 211     using reverse_iterator = std::reverse_iterator<iterator>;
 212     using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 213
 214     static constexpr size_t extent{dynamic_extent};
 215
 216     constexpr span() noexcept = default;
 217     template<typename U>
 218     constexpr span(U iter, index_type count)
 219         : mData{to_address(iter)}, mDataEnd{to_address(iter)+count}
 220     { }
 221     template<typename U, typename V, REQUIRES(!std::is_convertible<V,size_t>::value)>
 222     constexpr span(U first, V last) : span{to_address(first), static_cast<size_t>(last-first)}
 223     { }
 224
 225     template<size_t N>
 226     constexpr span(type_identity_t<element_type> (&arr)[N]) noexcept
 227         : span{al::data(arr), al::size(arr)}
 228     { }
 229     template<size_t N>
 230     constexpr span(std::array<value_type,N> &arr) noexcept : span{al::data(arr), al::size(arr)} { }
 231     template<size_t N, typename U=T, REQUIRES(std::is_const<U>::value)>
 232     constexpr span(const std::array<value_type,N> &arr) noexcept
 233       : span{al::data(arr), al::size(arr)}
 234     { }
 235
 236     template<typename U, REQUIRES(detail_::is_valid_container<U, element_type>)>
 237     constexpr span(U&& cont) : span{al::data(cont), al::size(cont)} { }
 238
 239     template<typename U, size_t N, REQUIRES((!std::is_same<element_type,U>::value || extent != N)
 240         && detail_::is_array_compatible<U,element_type>)>
 241     constexpr span(const span<U,N> &span_) noexcept : span{al::data(span_), al::size(span_)} { }
 242     constexpr span(const span&) noexcept = default;
 243
 244     constexpr span& operator=(const span &rhs) noexcept = default;
 245
 246     constexpr reference front() const { return *mData; }
 247     constexpr reference back() const { return *(mDataEnd-1); }
 248     constexpr reference operator[](index_type idx) const { return mData[idx]; }
 249     constexpr pointer data() const noexcept { return mData; }
 250
 251     constexpr index_type size() const noexcept { return static_cast<index_type>(mDataEnd-mData); }
 252     constexpr index_type size_bytes() const noexcept
 253     { return static_cast<index_type>(mDataEnd-mData) * sizeof(value_type); }
 254     constexpr bool empty() const noexcept { return mData == mDataEnd; }
 255
 256     constexpr iterator begin() const noexcept { return mData; }
 257     constexpr iterator end() const noexcept { return mDataEnd; }
 258     constexpr const_iterator cbegin() const noexcept { return mData; }
 259     constexpr const_iterator cend() const noexcept { return mDataEnd; }
 260
 261     constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; }
 262     constexpr reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; }
 263     constexpr const_reverse_iterator crbegin() const noexcept
 264     { return const_reverse_iterator{cend()}; }
 265     constexpr const_reverse_iterator crend() const noexcept
 266     { return const_reverse_iterator{cbegin()}; }
 267
 268     template<size_t C>
 269     constexpr span<element_type,C> first() const
 270     { return span<element_type,C>{mData, C}; }
 271
 272     constexpr span first(size_t count) const
 273     { return (count >= size()) ? *this : span{mData, mData+count}; }
 274
 275     template<size_t C>
 276     constexpr span<element_type,C> last() const
 277     { return span<element_type,C>{mDataEnd-C, C}; }
 278
 279     constexpr span last(size_t count) const
 280     { return (count >= size()) ? *this : span{mDataEnd-count, mDataEnd}; }
 281
 282     template<size_t O, size_t C>
 283     constexpr auto subspan() const -> std::enable_if_t<C!=dynamic_extent,span<element_type,C>>
 284     { return span<element_type,C>{mData+O, C}; }
 285
 286     template<size_t O, size_t C=dynamic_extent>
 287     constexpr auto subspan() const -> std::enable_if_t<C==dynamic_extent,span<element_type,C>>
 288     { return span<element_type,C>{mData+O, mDataEnd}; }
 289
 290     constexpr span subspan(size_t offset, size_t count=dynamic_extent) const
 291     {
 292         return (offset > size()) ? span{} :
 293             (count >= size()-offset) ? span{mData+offset, mDataEnd} :
 294             span{mData+offset, mData+offset+count};
 295     }
 296
 297 private:
 298     pointer mData{nullptr};
 299     pointer mDataEnd{nullptr};
 300 };
 301
 302 template<typename T, size_t E>
 303 constexpr inline auto span<T,E>::first(size_t count) const -> span<element_type,dynamic_extent>
 304 {
 305     return (count >= size()) ? span<element_type>{mData, extent} :
 306         span<element_type>{mData, count};
 307 }
 308
 309 template<typename T, size_t E>
 310 constexpr inline auto span<T,E>::last(size_t count) const -> span<element_type,dynamic_extent>
 311 {
 312     return (count >= size()) ? span<element_type>{mData, extent} :
 313         span<element_type>{mData+extent-count, count};
 314 }
 315
 316 template<typename T, size_t E>
 317 constexpr inline auto span<T,E>::subspan(size_t offset, size_t count) const
 318     -> span<element_type,dynamic_extent>
 319 {
 320     return (offset > size()) ? span<element_type>{} :
 321         (count >= size()-offset) ? span<element_type>{mData+offset, mData+extent} :
 322         span<element_type>{mData+offset, mData+offset+count};
 323 }
 324
 325 /* Helpers to deal with the lack of user-defined deduction guides (C++17). */
 326 template<typename T, typename U>
 327 constexpr auto as_span(T ptr, U count_or_end)
 328 {
 329     using value_type = typename std::pointer_traits<T>::element_type;
 330     return span<value_type>{ptr, count_or_end};
 331 }
 332 template<typename T, size_t N>
 333 constexpr auto as_span(T (&arr)[N]) noexcept { return span<T,N>{al::data(arr), al::size(arr)}; }
 334 template<typename T, size_t N>
 335 constexpr auto as_span(std::array<T,N> &arr) noexcept
 336 { return span<T,N>{al::data(arr), al::size(arr)}; }
 337 template<typename T, size_t N>
 338 constexpr auto as_span(const std::array<T,N> &arr) noexcept
 339 { return span<std::add_const_t<T>,N>{al::data(arr), al::size(arr)}; }
 340 template<typename U, REQUIRES(!detail_::is_span_v<U> && !detail_::is_std_array_v<U>
 341     && !std::is_array<U>::value && detail_::has_size_and_data<U>)>
 342 constexpr auto as_span(U&& cont)
 343 {
 344     using value_type = std::remove_pointer_t<decltype(al::data(std::declval<U&>()))>;
 345     return span<value_type>{al::data(cont), al::size(cont)};
 346 }
 347 template<typename T, size_t N>
 348 constexpr auto as_span(span<T,N> span_) noexcept { return span_; }
 349
 350 #undef REQUIRES
 351
 352 } // namespace al
 353
 354 #endif /* AL_SPAN_H */