Bitcoin Core  27.99.0
P2P Digital Currency
span.h
Go to the documentation of this file.
1 // Copyright (c) 2018-2022 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 <algorithm>
9 #include <cassert>
10 #include <cstddef>
11 #include <span>
12 #include <type_traits>
13 
14 #ifdef DEBUG
15 #define CONSTEXPR_IF_NOT_DEBUG
16 #define ASSERT_IF_DEBUG(x) assert((x))
17 #else
18 #define CONSTEXPR_IF_NOT_DEBUG constexpr
19 #define ASSERT_IF_DEBUG(x)
20 #endif
21 
22 #if defined(__clang__)
23 #if __has_attribute(lifetimebound)
24 #define SPAN_ATTR_LIFETIMEBOUND [[clang::lifetimebound]]
25 #else
26 #define SPAN_ATTR_LIFETIMEBOUND
27 #endif
28 #else
29 #define SPAN_ATTR_LIFETIMEBOUND
30 #endif
31 
96 template<typename C>
97 class Span
98 {
99  C* m_data;
100  std::size_t m_size{0};
101 
102  template <class T>
103  struct is_Span_int : public std::false_type {};
104  template <class T>
105  struct is_Span_int<Span<T>> : public std::true_type {};
106  template <class T>
107  struct is_Span : public is_Span_int<typename std::remove_cv<T>::type>{};
108 
109 
110 public:
111  constexpr Span() noexcept : m_data(nullptr) {}
112 
118  template <typename T, typename std::enable_if<std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
119  constexpr Span(T* begin, std::size_t size) noexcept : m_data(begin), m_size(size) {}
120 
126  template <typename T, typename std::enable_if<std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
128  {
130  }
131 
140  template <typename O, typename std::enable_if<std::is_convertible<O (*)[], C (*)[]>::value, int>::type = 0>
141  constexpr Span(const Span<O>& other) noexcept : m_data(other.m_data), m_size(other.m_size) {}
142 
144  constexpr Span(const Span&) noexcept = default;
145 
147  Span& operator=(const Span& other) noexcept = default;
148 
150  template <int N>
151  constexpr Span(C (&a)[N]) noexcept : m_data(a), m_size(N) {}
152 
160  template <typename V>
161  constexpr Span(V& other SPAN_ATTR_LIFETIMEBOUND,
162  typename std::enable_if<!is_Span<V>::value &&
163  std::is_convertible<typename std::remove_pointer<decltype(std::declval<V&>().data())>::type (*)[], C (*)[]>::value &&
164  std::is_convertible<decltype(std::declval<V&>().size()), std::size_t>::value, std::nullptr_t>::type = nullptr)
165  : m_data(other.data()), m_size(other.size()){}
166 
167  template <typename V>
168  constexpr Span(const V& other SPAN_ATTR_LIFETIMEBOUND,
169  typename std::enable_if<!is_Span<V>::value &&
170  std::is_convertible<typename std::remove_pointer<decltype(std::declval<const V&>().data())>::type (*)[], C (*)[]>::value &&
171  std::is_convertible<decltype(std::declval<const V&>().size()), std::size_t>::value, std::nullptr_t>::type = nullptr)
172  : m_data(other.data()), m_size(other.size()){}
173 
174  constexpr C* data() const noexcept { return m_data; }
175  constexpr C* begin() const noexcept { return m_data; }
176  constexpr C* end() const noexcept { return m_data + m_size; }
177  CONSTEXPR_IF_NOT_DEBUG C& front() const noexcept
178  {
179  ASSERT_IF_DEBUG(size() > 0);
180  return m_data[0];
181  }
182  CONSTEXPR_IF_NOT_DEBUG C& back() const noexcept
183  {
184  ASSERT_IF_DEBUG(size() > 0);
185  return m_data[m_size - 1];
186  }
187  constexpr std::size_t size() const noexcept { return m_size; }
188  constexpr std::size_t size_bytes() const noexcept { return sizeof(C) * m_size; }
189  constexpr bool empty() const noexcept { return size() == 0; }
190  CONSTEXPR_IF_NOT_DEBUG C& operator[](std::size_t pos) const noexcept
191  {
192  ASSERT_IF_DEBUG(size() > pos);
193  return m_data[pos];
194  }
195  CONSTEXPR_IF_NOT_DEBUG Span<C> subspan(std::size_t offset) const noexcept
196  {
197  ASSERT_IF_DEBUG(size() >= offset);
198  return Span<C>(m_data + offset, m_size - offset);
199  }
200  CONSTEXPR_IF_NOT_DEBUG Span<C> subspan(std::size_t offset, std::size_t count) const noexcept
201  {
202  ASSERT_IF_DEBUG(size() >= offset + count);
203  return Span<C>(m_data + offset, count);
204  }
205  CONSTEXPR_IF_NOT_DEBUG Span<C> first(std::size_t count) const noexcept
206  {
207  ASSERT_IF_DEBUG(size() >= count);
208  return Span<C>(m_data, count);
209  }
210  CONSTEXPR_IF_NOT_DEBUG Span<C> last(std::size_t count) const noexcept
211  {
212  ASSERT_IF_DEBUG(size() >= count);
213  return Span<C>(m_data + m_size - count, count);
214  }
215 
216  friend constexpr bool operator==(const Span& a, const Span& b) noexcept { return a.size() == b.size() && std::equal(a.begin(), a.end(), b.begin()); }
217  friend constexpr bool operator!=(const Span& a, const Span& b) noexcept { return !(a == b); }
218  friend constexpr bool operator<(const Span& a, const Span& b) noexcept { return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end()); }
219  friend constexpr bool operator<=(const Span& a, const Span& b) noexcept { return !(b < a); }
220  friend constexpr bool operator>(const Span& a, const Span& b) noexcept { return (b < a); }
221  friend constexpr bool operator>=(const Span& a, const Span& b) noexcept { return !(a < b); }
222 
223  template <typename O> friend class Span;
224 };
225 
226 // Return result of calling .data() method on type T. This is used to be able to
227 // write template deduction guides for the single-parameter Span constructor
228 // below that will work if the value that is passed has a .data() method, and if
229 // the data method does not return a void pointer.
230 //
231 // It is important to check for the void type specifically below, so the
232 // deduction guides can be used in SFINAE contexts to check whether objects can
233 // be converted to spans. If the deduction guides did not explicitly check for
234 // void, and an object was passed that returned void* from data (like
235 // std::vector<bool>), the template deduction would succeed, but the Span<void>
236 // object instantiation would fail, resulting in a hard error, rather than a
237 // SFINAE error.
238 // https://stackoverflow.com/questions/68759148/sfinae-to-detect-the-explicitness-of-a-ctad-deduction-guide
239 // https://stackoverflow.com/questions/16568986/what-happens-when-you-call-data-on-a-stdvectorbool
240 template<typename T>
241 using DataResult = std::remove_pointer_t<decltype(std::declval<T&>().data())>;
242 
243 // Deduction guides for Span
244 // For the pointer/size based and iterator based constructor:
245 template <typename T, typename EndOrSize> Span(T*, EndOrSize) -> Span<T>;
246 // For the array constructor:
247 template <typename T, std::size_t N> Span(T (&)[N]) -> Span<T>;
248 // For the temporaries/rvalue references constructor, only supporting const output.
249 template <typename T> Span(T&&) -> Span<std::enable_if_t<!std::is_lvalue_reference_v<T> && !std::is_void_v<DataResult<T&&>>, const DataResult<T&&>>>;
250 // For (lvalue) references, supporting mutable output.
252 
254 template <typename T>
256 {
257  size_t size = span.size();
258  ASSERT_IF_DEBUG(size > 0);
259  T& back = span[size - 1];
260  span = Span<T>(span.data(), size - 1);
261  return back;
262 }
263 
264 // From C++20 as_bytes and as_writeable_bytes
265 template <typename T>
267 {
268  return {reinterpret_cast<const std::byte*>(s.data()), s.size_bytes()};
269 }
270 template <typename T>
272 {
273  return {reinterpret_cast<std::byte*>(s.data()), s.size_bytes()};
274 }
275 
276 template <typename V>
278 {
279  return AsBytes(Span{std::forward<V>(v)});
280 }
281 template <typename V>
283 {
284  return AsWritableBytes(Span{std::forward<V>(v)});
285 }
286 
287 // Helper functions to safely cast basic byte pointers to unsigned char pointers.
288 inline unsigned char* UCharCast(char* c) { return reinterpret_cast<unsigned char*>(c); }
289 inline unsigned char* UCharCast(unsigned char* c) { return c; }
290 inline unsigned char* UCharCast(signed char* c) { return reinterpret_cast<unsigned char*>(c); }
291 inline unsigned char* UCharCast(std::byte* c) { return reinterpret_cast<unsigned char*>(c); }
292 inline const unsigned char* UCharCast(const char* c) { return reinterpret_cast<const unsigned char*>(c); }
293 inline const unsigned char* UCharCast(const unsigned char* c) { return c; }
294 inline const unsigned char* UCharCast(const signed char* c) { return reinterpret_cast<const unsigned char*>(c); }
295 inline const unsigned char* UCharCast(const std::byte* c) { return reinterpret_cast<const unsigned char*>(c); }
296 // Helper concept for the basic byte types.
297 template <typename B>
298 concept BasicByte = requires { UCharCast(std::span<B>{}.data()); };
299 
300 // Helper function to safely convert a Span to a Span<[const] unsigned char>.
301 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()}; }
302 
304 template <typename V> constexpr auto MakeUCharSpan(V&& v) -> decltype(UCharSpanCast(Span{std::forward<V>(v)})) { return UCharSpanCast(Span{std::forward<V>(v)}); }
305 
306 #endif // BITCOIN_SPAN_H
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:98
constexpr std::size_t size() const noexcept
Definition: span.h:187
constexpr friend bool operator>=(const Span &a, const Span &b) noexcept
Definition: span.h:221
Span & operator=(const Span &other) noexcept=default
Default assignment operator.
constexpr friend bool operator>(const Span &a, const Span &b) noexcept
Definition: span.h:220
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset, std::size_t count) const noexcept
Definition: span.h:200
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)
Construct a Span for objects with .data() and .size() (std::string, std::array, std::vector,...
Definition: span.h:161
CONSTEXPR_IF_NOT_DEBUG C & back() const noexcept
Definition: span.h:182
constexpr Span(C(&a)[N]) noexcept
Construct a Span from an array.
Definition: span.h:151
constexpr Span() noexcept
Definition: span.h:111
std::size_t m_size
Definition: span.h:100
CONSTEXPR_IF_NOT_DEBUG C & front() const noexcept
Definition: span.h:177
constexpr C * data() const noexcept
Definition: span.h:174
constexpr Span(T *begin, std::size_t size) noexcept
Construct a span from a begin pointer and a size.
Definition: span.h:119
CONSTEXPR_IF_NOT_DEBUG Span(T *begin, T *end) noexcept
Construct a span from a begin and end pointer.
Definition: span.h:127
C * m_data
Definition: span.h:99
constexpr C * end() const noexcept
Definition: span.h:176
constexpr C * begin() const noexcept
Definition: span.h:175
constexpr Span(const Span &) noexcept=default
Default copy constructor.
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)
Definition: span.h:168
constexpr std::size_t size_bytes() const noexcept
Definition: span.h:188
CONSTEXPR_IF_NOT_DEBUG Span< C > last(std::size_t count) const noexcept
Definition: span.h:210
CONSTEXPR_IF_NOT_DEBUG Span< C > first(std::size_t count) const noexcept
Definition: span.h:205
CONSTEXPR_IF_NOT_DEBUG C & operator[](std::size_t pos) const noexcept
Definition: span.h:190
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset) const noexcept
Definition: span.h:195
constexpr bool empty() const noexcept
Definition: span.h:189
constexpr friend bool operator!=(const Span &a, const Span &b) noexcept
Definition: span.h:217
constexpr friend bool operator==(const Span &a, const Span &b) noexcept
Definition: span.h:216
constexpr Span(const Span< O > &other) noexcept
Implicit conversion of spans between compatible types.
Definition: span.h:141
constexpr friend bool operator<(const Span &a, const Span &b) noexcept
Definition: span.h:218
constexpr friend bool operator<=(const Span &a, const Span &b) noexcept
Definition: span.h:219
#define ASSERT_IF_DEBUG(x)
Definition: span.h:19
#define SPAN_ATTR_LIFETIMEBOUND
Definition: span.h:29
constexpr auto MakeUCharSpan(V &&v) -> decltype(UCharSpanCast(Span{std::forward< V >(v)}))
Like the Span constructor, but for (const) unsigned char member types only.
Definition: span.h:304
concept BasicByte
Definition: span.h:298
std::remove_pointer_t< decltype(std::declval< T & >().data())> DataResult
Definition: span.h:241
Span< std::byte > AsWritableBytes(Span< T > s) noexcept
Definition: span.h:271
unsigned char * UCharCast(char *c)
Definition: span.h:288
Span(T *, EndOrSize) -> Span< T >
constexpr auto UCharSpanCast(Span< T > s) -> Span< typename std::remove_pointer< decltype(UCharCast(s.data()))>::type >
Definition: span.h:301
Span< const std::byte > MakeByteSpan(V &&v) noexcept
Definition: span.h:277
Span< const std::byte > AsBytes(Span< T > s) noexcept
Definition: span.h:266
#define CONSTEXPR_IF_NOT_DEBUG
Definition: span.h:18
Span< std::byte > MakeWritableByteSpan(V &&v) noexcept
Definition: span.h:282
T & SpanPopBack(Span< T > &span)
Pop the last element off a span, and return a reference to that element.
Definition: span.h:255
static int count