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