1 // Copyright (c) 2018-2020 The Bitcoin Core developers 2 // Distributed under the MIT software license, see the accompanying 3 // file COPYING or http://www.opensource.org/licenses/mit-license.php. 4 5 #ifndef BITCOIN_SPAN_H 6 #define BITCOIN_SPAN_H 7 8 #include <type_traits> 9 #include <cstddef> 10 #include <algorithm> 11 #include <assert.h> 12 13 #ifdef DEBUG 14 #define CONSTEXPR_IF_NOT_DEBUG 15 #define ASSERT_IF_DEBUG(x) assert((x)) 16 #else 17 #define CONSTEXPR_IF_NOT_DEBUG constexpr 18 #define ASSERT_IF_DEBUG(x) 19 #endif 20 21 #if defined(__clang__) 22 #if __has_attribute(lifetimebound) 23 #define SPAN_ATTR_LIFETIMEBOUND [[clang::lifetimebound]] 24 #else 25 #define SPAN_ATTR_LIFETIMEBOUND 26 #endif 27 #else 28 #define SPAN_ATTR_LIFETIMEBOUND 29 #endif 30 31 /** A Span is an object that can refer to a contiguous sequence of objects. 32 * 33 * It implements a subset of C++20's std::span. 34 * 35 * Things to be aware of when writing code that deals with Spans: 36 * 37 * - Similar to references themselves, Spans are subject to reference lifetime 38 * issues. The user is responsible for making sure the objects pointed to by 39 * a Span live as long as the Span is used. For example: 40 * 41 * std::vector<int> vec{1,2,3,4}; 42 * Span<int> sp(vec); 43 * vec.push_back(5); 44 * printf("%i\n", sp.front()); // UB! 45 * 46 * may exhibit undefined behavior, as increasing the size of a vector may 47 * invalidate references. 48 * 49 * - One particular pitfall is that Spans can be constructed from temporaries, 50 * but this is unsafe when the Span is stored in a variable, outliving the 51 * temporary. For example, this will compile, but exhibits undefined behavior: 52 * 53 * Span<const int> sp(std::vector<int>{1, 2, 3}); 54 * printf("%i\n", sp.front()); // UB! 55 * 56 * The lifetime of the vector ends when the statement it is created in ends. 57 * Thus the Span is left with a dangling reference, and using it is undefined. 58 * 59 * - Due to Span's automatic creation from range-like objects (arrays, and data 60 * types that expose a data() and size() member function), functions that 61 * accept a Span as input parameter can be called with any compatible 62 * range-like object. For example, this works: 63 * 64 * void Foo(Span<const int> arg); 65 * 66 * Foo(std::vector<int>{1, 2, 3}); // Works 67 * 68 * This is very useful in cases where a function truly does not care about the 69 * container, and only about having exactly a range of elements. However it 70 * may also be surprising to see automatic conversions in this case. 71 * 72 * When a function accepts a Span with a mutable element type, it will not 73 * accept temporaries; only variables or other references. For example: 74 * 75 * void FooMut(Span<int> arg); 76 * 77 * FooMut(std::vector<int>{1, 2, 3}); // Does not compile 78 * std::vector<int> baz{1, 2, 3}; 79 * FooMut(baz); // Works 80 * 81 * This is similar to how functions that take (non-const) lvalue references 82 * as input cannot accept temporaries. This does not work either: 83 * 84 * void FooVec(std::vector<int>& arg); 85 * FooVec(std::vector<int>{1, 2, 3}); // Does not compile 86 * 87 * The idea is that if a function accepts a mutable reference, a meaningful 88 * result will be present in that variable after the call. Passing a temporary 89 * is useless in that context. 90 */ 91 template<typename C> 92 class Span 93 { 94 C* m_data; 95 std::size_t m_size; 96 97 template <class T> 98 struct is_Span_int : public std::false_type {}; 99 template <class T> 100 struct is_Span_int<Span<T>> : public std::true_type {}; 101 template <class T> 102 struct is_Span : public is_Span_int<typename std::remove_cv<T>::type>{}; 103 104 105 public: 106 constexpr Span() noexcept : m_data(nullptr), m_size(0) {} 107 108 /** Construct a span from a begin pointer and a size. 109 * 110 * This implements a subset of the iterator-based std::span constructor in C++20, 111 * which is hard to implement without std::address_of. 112 */ 113 template <typename T, typename std::enable_if<std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0> 114 constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {} 115 116 /** Construct a span from a begin and end pointer. 117 * 118 * This implements a subset of the iterator-based std::span constructor in C++20, 119 * which is hard to implement without std::address_of. 120 */ 121 template <typename T, typename std::enable_if<std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0> 122 CONSTEXPR_IF_NOT_DEBUG Span(T* begin, T* end) noexcept : m_data(begin), m_size(end - begin) 123 { 124 ASSERT_IF_DEBUG(end >= begin); 125 } 126 127 /** Implicit conversion of spans between compatible types. 128 * 129 * Specifically, if a pointer to an array of type O can be implicitly converted to a pointer to an array of type 130 * C, then permit implicit conversion of Span<O> to Span<C>. This matches the behavior of the corresponding 131 * C++20 std::span constructor. 132 * 133 * For example this means that a Span<T> can be converted into a Span<const T>. 134 */ 135 template <typename O, typename std::enable_if<std::is_convertible<O (*)[], C (*)[]>::value, int>::type = 0> 136 constexpr Span(const Span<O>& other) noexcept : m_data(other.m_data), m_size(other.m_size) {} 137 138 /** Default copy constructor. */ 139 constexpr Span(const Span&) noexcept = default; 140 141 /** Default assignment operator. */ 142 Span& operator=(const Span& other) noexcept = default; 143 144 /** Construct a Span from an array. This matches the corresponding C++20 std::span constructor. */ 145 template <int N> 146 constexpr Span(C (&a)[N]) noexcept : m_data(a), m_size(N) {} 147 148 /** Construct a Span for objects with .data() and .size() (std::string, std::array, std::vector, ...). 149 * 150 * This implements a subset of the functionality provided by the C++20 std::span range-based constructor. 151 * 152 * To prevent surprises, only Spans for constant value types are supported when passing in temporaries. 153 * Note that this restriction does not exist when converting arrays or other Spans (see above). 154 */ 155 template <typename V> 156 constexpr Span(V& other SPAN_ATTR_LIFETIMEBOUND, 157 typename std::enable_if<!is_Span<V>::value && 158 std::is_convertible<typename std::remove_pointer<decltype(std::declval<V&>().data())>::type (*)[], C (*)[]>::value && 159 std::is_convertible<decltype(std::declval<V&>().size()), std::size_t>::value, std::nullptr_t>::type = nullptr) 160 : m_data(other.data()), m_size(other.size()){} 161 162 template <typename V> 163 constexpr Span(const V& other SPAN_ATTR_LIFETIMEBOUND, 164 typename std::enable_if<!is_Span<V>::value && 165 std::is_convertible<typename std::remove_pointer<decltype(std::declval<const V&>().data())>::type (*)[], C (*)[]>::value && 166 std::is_convertible<decltype(std::declval<const V&>().size()), std::size_t>::value, std::nullptr_t>::type = nullptr) 167 : m_data(other.data()), m_size(other.size()){} 168 169 constexpr C* data() const noexcept { return m_data; } 170 constexpr C* begin() const noexcept { return m_data; } 171 constexpr C* end() const noexcept { return m_data + m_size; } 172 CONSTEXPR_IF_NOT_DEBUG C& front() const noexcept 173 { 174 ASSERT_IF_DEBUG(size() > 0); 175 return m_data[0]; 176 } 177 CONSTEXPR_IF_NOT_DEBUG C& back() const noexcept 178 { 179 ASSERT_IF_DEBUG(size() > 0); 180 return m_data[m_size - 1]; 181 } 182 constexpr std::size_t size() const noexcept { return m_size; } 183 constexpr bool empty() const noexcept { return size() == 0; } 184 CONSTEXPR_IF_NOT_DEBUG C& operator[](std::size_t pos) const noexcept 185 { 186 ASSERT_IF_DEBUG(size() > pos); 187 return m_data[pos]; 188 } 189 CONSTEXPR_IF_NOT_DEBUG Span<C> subspan(std::size_t offset) const noexcept 190 { 191 ASSERT_IF_DEBUG(size() >= offset); 192 return Span<C>(m_data + offset, m_size - offset); 193 } 194 CONSTEXPR_IF_NOT_DEBUG Span<C> subspan(std::size_t offset, std::size_t count) const noexcept 195 { 196 ASSERT_IF_DEBUG(size() >= offset + count); 197 return Span<C>(m_data + offset, count); 198 } 199 CONSTEXPR_IF_NOT_DEBUG Span<C> first(std::size_t count) const noexcept 200 { 201 ASSERT_IF_DEBUG(size() >= count); 202 return Span<C>(m_data, count); 203 } 204 CONSTEXPR_IF_NOT_DEBUG Span<C> last(std::size_t count) const noexcept 205 { 206 ASSERT_IF_DEBUG(size() >= count); 207 return Span<C>(m_data + m_size - count, count); 208 } 209 210 friend constexpr bool operator==(const Span& a, const Span& b) noexcept { return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); } 211 friend constexpr bool operator!=(const Span& a, const Span& b) noexcept { return !(a == b); } 212 friend constexpr bool operator<(const Span& a, const Span& b) noexcept { return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); } 213 friend constexpr bool operator<=(const Span& a, const Span& b) noexcept { return !(b < a); } 214 friend constexpr bool operator>(const Span& a, const Span& b) noexcept { return (b < a); } 215 friend constexpr bool operator>=(const Span& a, const Span& b) noexcept { return !(a < b); } 216 217 template <typename O> friend class Span; 218 }; 219 220 // MakeSpan helps constructing a Span of the right type automatically. 221 /** MakeSpan for arrays: */ 222 template <typename A, int N> Span<A> constexpr MakeSpan(A (&a)[N]) { return Span<A>(a, N); } 223 /** MakeSpan for temporaries / rvalue references, only supporting const output. */ 224 template <typename V> constexpr auto MakeSpan(V&& v SPAN_ATTR_LIFETIMEBOUND) -> typename std::enable_if<!std::is_lvalue_reference<V>::value, Span<const typename std::remove_pointer<decltype(v.data())>::type>>::type { return std::forward<V>(v); } 225 /** MakeSpan for (lvalue) references, supporting mutable output. */ 226 template <typename V> constexpr auto MakeSpan(V& v SPAN_ATTR_LIFETIMEBOUND) -> Span<typename std::remove_pointer<decltype(v.data())>::type> { return v; } 227 228 /** Pop the last element off a span, and return a reference to that element. */ 229 template <typename T> 230 T& SpanPopBack(Span<T>& span) 231 { 232 size_t size = span.size(); 233 ASSERT_IF_DEBUG(size > 0); 234 T& back = span[size - 1]; 235 span = Span<T>(span.data(), size - 1); 236 return back; 237 } 238 239 // Helper functions to safely cast to unsigned char pointers. 240 inline unsigned char* UCharCast(char* c) { return (unsigned char*)c; } 241 inline unsigned char* UCharCast(unsigned char* c) { return c; } 242 inline const unsigned char* UCharCast(const char* c) { return (unsigned char*)c; } 243 inline const unsigned char* UCharCast(const unsigned char* c) { return c; } 244 245 // Helper function to safely convert a Span to a Span<[const] unsigned char>. 246 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()}; } 247 248 /** Like MakeSpan, but for (const) unsigned char member types only. Only works for (un)signed char containers. */ 249 template <typename V> constexpr auto MakeUCharSpan(V&& v) -> decltype(UCharSpanCast(MakeSpan(std::forward<V>(v)))) { return UCharSpanCast(MakeSpan(std::forward<V>(v))); } 250 251 #endif 252