span.h

Go to the documentation of this file.

// Copyright (c) 2018 The Bitcoin Core developers
// Distributed under the MIT software license, see the accompanying
// file COPYING or http://www.opensource.org/licenses/mit-license.php.
 
#ifndef BITCOIN_SPAN_H
#define BITCOIN_SPAN_H
 
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <type_traits>
 
#ifdef DEBUG
#define CONSTEXPR_IF_NOT_DEBUG
#define ASSERT_IF_DEBUG(x) assert((x))
#else
#define CONSTEXPR_IF_NOT_DEBUG constexpr
#define ASSERT_IF_DEBUG(x)
#endif
 
#if defined(__clang__)
#if __has_attribute(lifetimebound)
#define SPAN_ATTR_LIFETIMEBOUND [[clang::lifetimebound]]
#else
#define SPAN_ATTR_LIFETIMEBOUND
#endif
#else
#define SPAN_ATTR_LIFETIMEBOUND
#endif
 
template <typename C> class Span {
    C *m_data;
    std::size_t m_size;
 
    template <class T> struct is_Span_int : public std::false_type {};
    template <class T> struct is_Span_int<Span<T>> : public std::true_type {};
    template <class T>
    struct is_Span : public is_Span_int<typename std::remove_cv<T>::type> {};
 
public:
    constexpr Span() noexcept : m_data(nullptr), m_size(0) {}
 
    template <typename T,
              typename std::enable_if<
                  std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
    constexpr Span(T *begin, std::size_t size) noexcept
        : m_data(begin), m_size(size) {}
 
    template <typename T,
              typename std::enable_if<
                  std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
    CONSTEXPR_IF_NOT_DEBUG Span(T *begin, T *end) noexcept
        : m_data(begin), m_size(end - begin) {
        ASSERT_IF_DEBUG(end >= begin);
    }
 
    template <typename O,
              typename std::enable_if<
                  std::is_convertible<O (*)[], C (*)[]>::value, int>::type = 0>
    constexpr Span(const Span<O> &other) noexcept
        : m_data(other.m_data), m_size(other.m_size) {}
 
    constexpr Span(const Span &) noexcept = default;
 
    Span &operator=(const Span &other) noexcept = default;
 
    template <int N>
    constexpr Span(C (&a)[N]) noexcept : m_data(a), m_size(N) {}
 
    template <typename V>
    constexpr Span(
        V &other SPAN_ATTR_LIFETIMEBOUND,
        typename std::enable_if<
            !is_Span<V>::value &&
                std::is_convertible<
                    typename std::remove_pointer<
                        decltype(std::declval<V &>().data())>::type (*)[],
                    C (*)[]>::value &&
                std::is_convertible<decltype(std::declval<V &>().size()),
                                    std::size_t>::value,
            std::nullptr_t>::type = nullptr)
        : m_data(other.data()), m_size(other.size()) {}
 
    template <typename V>
    constexpr Span(
        const V &other SPAN_ATTR_LIFETIMEBOUND,
        typename std::enable_if<
            !is_Span<V>::value &&
                std::is_convertible<
                    typename std::remove_pointer<
                        decltype(std::declval<const V &>().data())>::type (*)[],
                    C (*)[]>::value &&
                std::is_convertible<decltype(std::declval<const V &>().size()),
                                    std::size_t>::value,
            std::nullptr_t>::type = nullptr)
        : m_data(other.data()), m_size(other.size()) {}
 
    constexpr C *data() const noexcept { return m_data; }
    constexpr C *begin() const noexcept { return m_data; }
    constexpr C *end() const noexcept { return m_data + m_size; }
    CONSTEXPR_IF_NOT_DEBUG C &front() const noexcept {
        ASSERT_IF_DEBUG(size() > 0);
        return m_data[0];
    }
    CONSTEXPR_IF_NOT_DEBUG C &back() const noexcept {
        ASSERT_IF_DEBUG(size() > 0);
        return m_data[m_size - 1];
    }
    constexpr std::size_t size() const noexcept { return m_size; }
    constexpr bool empty() const noexcept { return size() == 0; }
    CONSTEXPR_IF_NOT_DEBUG C &operator[](std::size_t pos) const noexcept {
        ASSERT_IF_DEBUG(size() > pos);
        return m_data[pos];
    }
    CONSTEXPR_IF_NOT_DEBUG Span<C> subspan(std::size_t offset) const noexcept {
        ASSERT_IF_DEBUG(size() >= offset);
        return Span<C>(m_data + offset, m_size - offset);
    }
    CONSTEXPR_IF_NOT_DEBUG Span<C> subspan(std::size_t offset,
                                           std::size_t count) const noexcept {
        ASSERT_IF_DEBUG(size() >= offset + count);
        return Span<C>(m_data + offset, count);
    }
    CONSTEXPR_IF_NOT_DEBUG Span<C> first(std::size_t count) const noexcept {
        ASSERT_IF_DEBUG(size() >= count);
        return Span<C>(m_data, count);
    }
    CONSTEXPR_IF_NOT_DEBUG Span<C> last(std::size_t count) const noexcept {
        ASSERT_IF_DEBUG(size() >= count);
        return Span<C>(m_data + m_size - count, count);
    }
 
    friend constexpr bool operator==(const Span &a, const Span &b) noexcept {
        return a.size() == b.size() &&
               std::equal(a.begin(), a.end(), b.begin());
    }
    friend constexpr bool operator!=(const Span &a, const Span &b) noexcept {
        return !(a == b);
    }
    friend constexpr bool operator<(const Span &a, const Span &b) noexcept {
        return std::lexicographical_compare(a.begin(), a.end(), b.begin(),
                                            b.end());
    }
    friend constexpr bool operator<=(const Span &a, const Span &b) noexcept {
        return !(b < a);
    }
    friend constexpr bool operator>(const Span &a, const Span &b) noexcept {
        return (b < a);
    }
    friend constexpr bool operator>=(const Span &a, const Span &b) noexcept {
        return !(a < b);
    }
 
    template <typename O> friend class Span;
};
 
// Deduction guides for Span
// For the pointer/size based and iterator based constructor:
template <typename T, typename EndOrSize> Span(T *, EndOrSize) -> Span<T>;
// For the array constructor:
template <typename T, std::size_t N> Span(T (&)[N]) -> Span<T>;
// For the temporaries/rvalue references constructor, only supporting const
// output.
template <typename T>
Span(T &&) -> Span<std::enable_if_t<
    !std::is_lvalue_reference_v<T>,
    const std::remove_pointer_t<decltype(std::declval<T &&>().data())>>>;
// For (lvalue) references, supporting mutable output.
template <typename T>
Span(T &) -> Span<std::remove_pointer_t<decltype(std::declval<T &>().data())>>;
 
template <typename T> T &SpanPopBack(Span<T> &span) {
    size_t size = span.size();
    ASSERT_IF_DEBUG(size > 0);
    T &back = span[size - 1];
    span = Span<T>(span.data(), size - 1);
    return back;
}
 
// Helper functions to safely cast to uint8_t pointers.
inline uint8_t *UCharCast(char *c) {
    return (uint8_t *)c;
}
inline uint8_t *UCharCast(uint8_t *c) {
    return c;
}
inline const uint8_t *UCharCast(const char *c) {
    return (uint8_t *)c;
}
inline const uint8_t *UCharCast(const uint8_t *c) {
    return c;
}
 
// Helper function to safely convert a Span to a Span<[const] uint8_t>.
template <typename T>
constexpr auto UCharSpanCast(Span<T> s)
    -> Span<typename std::remove_pointer<decltype(UCharCast(s.data()))>::type> {
    return {UCharCast(s.data()), s.size()};
}
 
template <typename V>
constexpr auto MakeUCharSpan(V &&v)
    -> decltype(UCharSpanCast(Span{std::forward<V>(v)})) {
    return UCharSpanCast(Span{std::forward<V>(v)});
}
 
#endif // BITCOIN_SPAN_H