Bitcoin Core  22.99.0
P2P Digital Currency
span.h
Go to the documentation of this file.
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 
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 
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 
121  template <typename T, typename std::enable_if<std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
123  {
125  }
126 
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 
139  constexpr Span(const Span&) noexcept = default;
140 
142  Span& operator=(const Span& other) noexcept = default;
143 
145  template <int N>
146  constexpr Span(C (&a)[N]) noexcept : m_data(a), m_size(N) {}
147 
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.
222 template <typename A, int N> Span<A> constexpr MakeSpan(A (&a)[N]) { return Span<A>(a, N); }
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); }
226 template <typename V> constexpr auto MakeSpan(V& v SPAN_ATTR_LIFETIMEBOUND) -> Span<typename std::remove_pointer<decltype(v.data())>::type> { return v; }
227 
229 template <typename T>
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 
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
UCharSpanCast
constexpr auto UCharSpanCast(Span< T > s) -> Span< typename std::remove_pointer< decltype(UCharCast(s.data()))>::type >
Definition: span.h:246
Span::operator==
constexpr friend bool operator==(const Span &a, const Span &b) noexcept
Definition: span.h:210
Span::is_Span
Definition: span.h:102
Span::m_data
C * m_data
Definition: span.h:94
count
static int count
Definition: tests.c:41
Span::Span
constexpr Span(C(&a)[N]) noexcept
Construct a Span from an array.
Definition: span.h:146
SPAN_ATTR_LIFETIMEBOUND
#define SPAN_ATTR_LIFETIMEBOUND
Definition: span.h:28
MakeUCharSpan
constexpr auto MakeUCharSpan(V &&v) -> decltype(UCharSpanCast(MakeSpan(std::forward< V >(v))))
Like MakeSpan, but for (const) unsigned char member types only.
Definition: span.h:249
SpanPopBack
T & SpanPopBack(Span< T > &span)
Pop the last element off a span, and return a reference to that element.
Definition: span.h:230
Span::Span
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:156
Span::Span
constexpr Span(const Span< O > &other) noexcept
Implicit conversion of spans between compatible types.
Definition: span.h:136
Span::Span
constexpr Span(T *begin, std::size_t size) noexcept
Construct a span from a begin pointer and a size.
Definition: span.h:114
Span::operator[]
CONSTEXPR_IF_NOT_DEBUG C & operator[](std::size_t pos) const noexcept
Definition: span.h:184
Span::size
constexpr std::size_t size() const noexcept
Definition: span.h:182
Span
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:92
Span::Span
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:163
UCharCast
unsigned char * UCharCast(char *c)
Definition: span.h:240
CONSTEXPR_IF_NOT_DEBUG
#define CONSTEXPR_IF_NOT_DEBUG
Definition: span.h:17
Span::m_size
std::size_t m_size
Definition: span.h:95
Span::begin
constexpr C * begin() const noexcept
Definition: span.h:170
Span::Span
friend class Span
Definition: span.h:217
ASSERT_IF_DEBUG
#define ASSERT_IF_DEBUG(x)
Definition: span.h:18
Span::empty
constexpr bool empty() const noexcept
Definition: span.h:183
Span::front
CONSTEXPR_IF_NOT_DEBUG C & front() const noexcept
Definition: span.h:172
Span::is_Span_int
Definition: span.h:98
Span::operator<=
constexpr friend bool operator<=(const Span &a, const Span &b) noexcept
Definition: span.h:213
Span::operator>
constexpr friend bool operator>(const Span &a, const Span &b) noexcept
Definition: span.h:214
Span::data
constexpr C * data() const noexcept
Definition: span.h:169
Span::operator!=
constexpr friend bool operator!=(const Span &a, const Span &b) noexcept
Definition: span.h:211
Span::back
CONSTEXPR_IF_NOT_DEBUG C & back() const noexcept
Definition: span.h:177
Span::Span
constexpr Span() noexcept
Definition: span.h:106
Span::Span
CONSTEXPR_IF_NOT_DEBUG Span(T *begin, T *end) noexcept
Construct a span from a begin and end pointer.
Definition: span.h:122
Span::last
CONSTEXPR_IF_NOT_DEBUG Span< C > last(std::size_t count) const noexcept
Definition: span.h:204
Span::operator>=
constexpr friend bool operator>=(const Span &a, const Span &b) noexcept
Definition: span.h:215
Span::first
CONSTEXPR_IF_NOT_DEBUG Span< C > first(std::size_t count) const noexcept
Definition: span.h:199
Span::operator<
constexpr friend bool operator<(const Span &a, const Span &b) noexcept
Definition: span.h:212
MakeSpan
constexpr Span< A > MakeSpan(A(&a)[N])
MakeSpan for arrays:
Definition: span.h:222
Span::operator=
Span & operator=(const Span &other) noexcept=default
Default assignment operator.
Span::subspan
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset, std::size_t count) const noexcept
Definition: span.h:194
Span::end
constexpr C * end() const noexcept
Definition: span.h:171
Span::subspan
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset) const noexcept
Definition: span.h:189