Bitcoin ABC  0.26.3
P2P Digital Currency
span.h
Go to the documentation of this file.
1 // Copyright (c) 2018 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 <cstdint>
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 
93 template <typename C> class Span {
94  C *m_data;
95  std::size_t m_size;
96 
97  template <class T> struct is_Span_int : public std::false_type {};
98  template <class T> struct is_Span_int<Span<T>> : public std::true_type {};
99  template <class T>
100  struct is_Span : public is_Span_int<typename std::remove_cv<T>::type> {};
101 
102 public:
103  constexpr Span() noexcept : m_data(nullptr), m_size(0) {}
104 
111  template <typename T,
112  typename std::enable_if<
113  std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
114  constexpr Span(T *begin, std::size_t size) noexcept
115  : m_data(begin), m_size(size) {}
116 
123  template <typename T,
124  typename std::enable_if<
125  std::is_convertible<T (*)[], C (*)[]>::value, int>::type = 0>
127  : m_data(begin), m_size(end - begin) {
129  }
130 
142  template <typename O,
143  typename std::enable_if<
144  std::is_convertible<O (*)[], C (*)[]>::value, int>::type = 0>
145  constexpr Span(const Span<O> &other) noexcept
146  : m_data(other.m_data), m_size(other.m_size) {}
147 
149  constexpr Span(const Span &) noexcept = default;
150 
152  Span &operator=(const Span &other) noexcept = default;
153 
156  template <int N>
157  constexpr Span(C (&a)[N]) noexcept : m_data(a), m_size(N) {}
158 
170  template <typename V>
171  constexpr Span(
172  V &other SPAN_ATTR_LIFETIMEBOUND,
173  typename std::enable_if<
175  std::is_convertible<
176  typename std::remove_pointer<
177  decltype(std::declval<V &>().data())>::type (*)[],
178  C (*)[]>::value &&
179  std::is_convertible<decltype(std::declval<V &>().size()),
180  std::size_t>::value,
181  std::nullptr_t>::type = nullptr)
182  : m_data(other.data()), m_size(other.size()) {}
183 
184  template <typename V>
185  constexpr Span(
186  const V &other SPAN_ATTR_LIFETIMEBOUND,
187  typename std::enable_if<
189  std::is_convertible<
190  typename std::remove_pointer<
191  decltype(std::declval<const V &>().data())>::type (*)[],
192  C (*)[]>::value &&
193  std::is_convertible<decltype(std::declval<const V &>().size()),
194  std::size_t>::value,
195  std::nullptr_t>::type = nullptr)
196  : m_data(other.data()), m_size(other.size()) {}
197 
198  constexpr C *data() const noexcept { return m_data; }
199  constexpr C *begin() const noexcept { return m_data; }
200  constexpr C *end() const noexcept { return m_data + m_size; }
201  CONSTEXPR_IF_NOT_DEBUG C &front() const noexcept {
202  ASSERT_IF_DEBUG(size() > 0);
203  return m_data[0];
204  }
205  CONSTEXPR_IF_NOT_DEBUG C &back() const noexcept {
206  ASSERT_IF_DEBUG(size() > 0);
207  return m_data[m_size - 1];
208  }
209  constexpr std::size_t size() const noexcept { return m_size; }
210  constexpr bool empty() const noexcept { return size() == 0; }
211  CONSTEXPR_IF_NOT_DEBUG C &operator[](std::size_t pos) const noexcept {
212  ASSERT_IF_DEBUG(size() > pos);
213  return m_data[pos];
214  }
215  CONSTEXPR_IF_NOT_DEBUG Span<C> subspan(std::size_t offset) const noexcept {
216  ASSERT_IF_DEBUG(size() >= offset);
217  return Span<C>(m_data + offset, m_size - offset);
218  }
220  std::size_t count) const noexcept {
221  ASSERT_IF_DEBUG(size() >= offset + count);
222  return Span<C>(m_data + offset, count);
223  }
224  CONSTEXPR_IF_NOT_DEBUG Span<C> first(std::size_t count) const noexcept {
225  ASSERT_IF_DEBUG(size() >= count);
226  return Span<C>(m_data, count);
227  }
228  CONSTEXPR_IF_NOT_DEBUG Span<C> last(std::size_t count) const noexcept {
229  ASSERT_IF_DEBUG(size() >= count);
230  return Span<C>(m_data + m_size - count, count);
231  }
232 
233  friend constexpr bool operator==(const Span &a, const Span &b) noexcept {
234  return a.size() == b.size() &&
235  std::equal(a.begin(), a.end(), b.begin());
236  }
237  friend constexpr bool operator!=(const Span &a, const Span &b) noexcept {
238  return !(a == b);
239  }
240  friend constexpr bool operator<(const Span &a, const Span &b) noexcept {
241  return std::lexicographical_compare(a.begin(), a.end(), b.begin(),
242  b.end());
243  }
244  friend constexpr bool operator<=(const Span &a, const Span &b) noexcept {
245  return !(b < a);
246  }
247  friend constexpr bool operator>(const Span &a, const Span &b) noexcept {
248  return (b < a);
249  }
250  friend constexpr bool operator>=(const Span &a, const Span &b) noexcept {
251  return !(a < b);
252  }
253 
254  template <typename O> friend class Span;
255 };
256 
257 // MakeSpan helps constructing a Span of the right type automatically.
259 template <typename A, int N> Span<A> constexpr MakeSpan(A (&a)[N]) {
260  return Span<A>(a, N);
261 }
264 template <typename V>
265 constexpr auto
266 MakeSpan(V &&v SPAN_ATTR_LIFETIMEBOUND) -> typename std::enable_if<
267  !std::is_lvalue_reference<V>::value,
268  Span<const typename std::remove_pointer<decltype(v.data())>::type>>::type {
269  return std::forward<V>(v);
270 }
272 template <typename V>
273 constexpr auto MakeSpan(V &v SPAN_ATTR_LIFETIMEBOUND)
274  -> Span<typename std::remove_pointer<decltype(v.data())>::type> {
275  return v;
276 }
277 
279 template <typename T> T &SpanPopBack(Span<T> &span) {
280  size_t size = span.size();
281  ASSERT_IF_DEBUG(size > 0);
282  T &back = span[size - 1];
283  span = Span<T>(span.data(), size - 1);
284  return back;
285 }
286 
287 // Helper functions to safely cast to uint8_t pointers.
288 inline uint8_t *UCharCast(char *c) {
289  return (uint8_t *)c;
290 }
291 inline uint8_t *UCharCast(uint8_t *c) {
292  return c;
293 }
294 inline const uint8_t *UCharCast(const char *c) {
295  return (uint8_t *)c;
296 }
297 inline const uint8_t *UCharCast(const uint8_t *c) {
298  return c;
299 }
300 
301 // Helper function to safely convert a Span to a Span<[const] uint8_t>.
302 template <typename T>
303 constexpr auto UCharSpanCast(Span<T> s)
304  -> Span<typename std::remove_pointer<decltype(UCharCast(s.data()))>::type> {
305  return {UCharCast(s.data()), s.size()};
306 }
307 
310 template <typename V>
311 constexpr auto MakeUCharSpan(V &&v)
312  -> decltype(UCharSpanCast(MakeSpan(std::forward<V>(v)))) {
313  return UCharSpanCast(MakeSpan(std::forward<V>(v)));
314 }
315 
316 #endif // BITCOIN_SPAN_H
A Span is an object that can refer to a contiguous sequence of objects.
Definition: span.h:93
constexpr std::size_t size() const noexcept
Definition: span.h:209
constexpr friend bool operator>=(const Span &a, const Span &b) noexcept
Definition: span.h:250
Span & operator=(const Span &other) noexcept=default
Default assignment operator.
constexpr friend bool operator>(const Span &a, const Span &b) noexcept
Definition: span.h:247
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset, std::size_t count) const noexcept
Definition: span.h:219
CONSTEXPR_IF_NOT_DEBUG C & back() const noexcept
Definition: span.h:205
constexpr Span(C(&a)[N]) noexcept
Construct a Span from an array.
Definition: span.h:157
constexpr Span() noexcept
Definition: span.h:103
std::size_t m_size
Definition: span.h:95
CONSTEXPR_IF_NOT_DEBUG C & front() const noexcept
Definition: span.h:201
constexpr C * data() const noexcept
Definition: span.h:198
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:185
constexpr Span(T *begin, std::size_t size) noexcept
Construct a span from a begin pointer and a size.
Definition: span.h:114
CONSTEXPR_IF_NOT_DEBUG Span(T *begin, T *end) noexcept
Construct a span from a begin and end pointer.
Definition: span.h:126
C * m_data
Definition: span.h:94
constexpr C * end() const noexcept
Definition: span.h:200
constexpr C * begin() const noexcept
Definition: span.h:199
constexpr Span(const Span &) noexcept=default
Default copy constructor.
CONSTEXPR_IF_NOT_DEBUG Span< C > last(std::size_t count) const noexcept
Definition: span.h:228
CONSTEXPR_IF_NOT_DEBUG Span< C > first(std::size_t count) const noexcept
Definition: span.h:224
CONSTEXPR_IF_NOT_DEBUG C & operator[](std::size_t pos) const noexcept
Definition: span.h:211
CONSTEXPR_IF_NOT_DEBUG Span< C > subspan(std::size_t offset) const noexcept
Definition: span.h:215
constexpr bool empty() const noexcept
Definition: span.h:210
constexpr friend bool operator!=(const Span &a, const Span &b) noexcept
Definition: span.h:237
constexpr friend bool operator==(const Span &a, const Span &b) noexcept
Definition: span.h:233
constexpr Span(const Span< O > &other) noexcept
Implicit conversion of spans between compatible types.
Definition: span.h:145
constexpr friend bool operator<(const Span &a, const Span &b) noexcept
Definition: span.h:240
constexpr friend bool operator<=(const Span &a, const Span &b) noexcept
Definition: span.h:244
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:171
#define ASSERT_IF_DEBUG(x)
Definition: span.h:19
constexpr Span< A > MakeSpan(A(&a)[N])
MakeSpan for arrays:
Definition: span.h:259
#define SPAN_ATTR_LIFETIMEBOUND
Definition: span.h:29
constexpr auto UCharSpanCast(Span< T > s) -> Span< typename std::remove_pointer< decltype(UCharCast(s.data()))>::type >
Definition: span.h:303
#define CONSTEXPR_IF_NOT_DEBUG
Definition: span.h:18
T & SpanPopBack(Span< T > &span)
Pop the last element off a span, and return a reference to that element.
Definition: span.h:279
constexpr auto MakeUCharSpan(V &&v) -> decltype(UCharSpanCast(MakeSpan(std::forward< V >(v))))
Like MakeSpan, but for (const) uint8_t member types only.
Definition: span.h:311
uint8_t * UCharCast(char *c)
Definition: span.h:288
static int count
Definition: tests.c:31