• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2017 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #ifndef BASE_CONTAINERS_SPAN_H_
6 #define BASE_CONTAINERS_SPAN_H_
7 
8 #include <stddef.h>
9 
10 #include <algorithm>
11 #include <array>
12 #include <iterator>
13 #include <type_traits>
14 #include <utility>
15 
16 #include "base/logging.h"
17 #include "base/stl_util.h"
18 
19 namespace base {
20 
21 // [views.constants]
22 constexpr size_t dynamic_extent = static_cast<size_t>(-1);
23 
24 template <typename T, size_t Extent = dynamic_extent>
25 class span;
26 
27 namespace internal {
28 
29 template <typename T>
30 struct IsSpanImpl : std::false_type {};
31 
32 template <typename T, size_t Extent>
33 struct IsSpanImpl<span<T, Extent>> : std::true_type {};
34 
35 template <typename T>
36 using IsSpan = IsSpanImpl<std::decay_t<T>>;
37 
38 template <typename T>
39 struct IsStdArrayImpl : std::false_type {};
40 
41 template <typename T, size_t N>
42 struct IsStdArrayImpl<std::array<T, N>> : std::true_type {};
43 
44 template <typename T>
45 using IsStdArray = IsStdArrayImpl<std::decay_t<T>>;
46 
47 template <typename T>
48 using IsCArray = std::is_array<std::remove_reference_t<T>>;
49 
50 template <typename From, typename To>
51 using IsLegalDataConversion = std::is_convertible<From (*)[], To (*)[]>;
52 
53 template <typename Container, typename T>
54 using ContainerHasConvertibleData = IsLegalDataConversion<
55     std::remove_pointer_t<decltype(base::data(std::declval<Container>()))>,
56     T>;
57 
58 template <typename Container>
59 using ContainerHasIntegralSize =
60     std::is_integral<decltype(base::size(std::declval<Container>()))>;
61 
62 template <typename From, size_t FromExtent, typename To, size_t ToExtent>
63 using EnableIfLegalSpanConversion =
64     std::enable_if_t<(ToExtent == dynamic_extent || ToExtent == FromExtent) &&
65                      IsLegalDataConversion<From, To>::value>;
66 
67 // SFINAE check if Array can be converted to a span<T>.
68 template <typename Array, size_t N, typename T, size_t Extent>
69 using EnableIfSpanCompatibleArray =
70     std::enable_if_t<(Extent == dynamic_extent || Extent == N) &&
71                      ContainerHasConvertibleData<Array, T>::value>;
72 
73 // SFINAE check if Container can be converted to a span<T>.
74 template <typename Container, typename T>
75 using EnableIfSpanCompatibleContainer =
76     std::enable_if_t<!internal::IsSpan<Container>::value &&
77                      !internal::IsStdArray<Container>::value &&
78                      !internal::IsCArray<Container>::value &&
79                      ContainerHasConvertibleData<Container, T>::value &&
80                      ContainerHasIntegralSize<Container>::value>;
81 
82 }  // namespace internal
83 
84 // A span is a value type that represents an array of elements of type T. Since
85 // it only consists of a pointer to memory with an associated size, it is very
86 // light-weight. It is cheap to construct, copy, move and use spans, so that
87 // users are encouraged to use it as a pass-by-value parameter. A span does not
88 // own the underlying memory, so care must be taken to ensure that a span does
89 // not outlive the backing store.
90 //
91 // span is somewhat analogous to StringPiece, but with arbitrary element types,
92 // allowing mutation if T is non-const.
93 //
94 // span is implicitly convertible from C++ arrays, as well as most [1]
95 // container-like types that provide a data() and size() method (such as
96 // std::vector<T>). A mutable span<T> can also be implicitly converted to an
97 // immutable span<const T>.
98 //
99 // Consider using a span for functions that take a data pointer and size
100 // parameter: it allows the function to still act on an array-like type, while
101 // allowing the caller code to be a bit more concise.
102 //
103 // For read-only data access pass a span<const T>: the caller can supply either
104 // a span<const T> or a span<T>, while the callee will have a read-only view.
105 // For read-write access a mutable span<T> is required.
106 //
107 // Without span:
108 //   Read-Only:
109 //     // std::string HexEncode(const uint8_t* data, size_t size);
110 //     std::vector<uint8_t> data_buffer = GenerateData();
111 //     std::string r = HexEncode(data_buffer.data(), data_buffer.size());
112 //
113 //  Mutable:
114 //     // ssize_t SafeSNPrintf(char* buf, size_t N, const char* fmt, Args...);
115 //     char str_buffer[100];
116 //     SafeSNPrintf(str_buffer, sizeof(str_buffer), "Pi ~= %lf", 3.14);
117 //
118 // With span:
119 //   Read-Only:
120 //     // std::string HexEncode(base::span<const uint8_t> data);
121 //     std::vector<uint8_t> data_buffer = GenerateData();
122 //     std::string r = HexEncode(data_buffer);
123 //
124 //  Mutable:
125 //     // ssize_t SafeSNPrintf(base::span<char>, const char* fmt, Args...);
126 //     char str_buffer[100];
127 //     SafeSNPrintf(str_buffer, "Pi ~= %lf", 3.14);
128 //
129 // Spans with "const" and pointers
130 // -------------------------------
131 //
132 // Const and pointers can get confusing. Here are vectors of pointers and their
133 // corresponding spans:
134 //
135 //   const std::vector<int*>        =>  base::span<int* const>
136 //   std::vector<const int*>        =>  base::span<const int*>
137 //   const std::vector<const int*>  =>  base::span<const int* const>
138 //
139 // Differences from the working group proposal
140 // -------------------------------------------
141 //
142 // https://wg21.link/P0122 is the latest working group proposal, Chromium
143 // currently implements R7. Differences between the proposal and the
144 // implementation are documented in subsections below.
145 //
146 // Differences from [span.objectrep]:
147 // - as_bytes() and as_writable_bytes() return spans of uint8_t instead of
148 //   std::byte
149 //
150 // Differences in constants and types:
151 // - index_type is aliased to size_t
152 //
153 // Differences from [span.sub]:
154 // - using size_t instead of ptrdiff_t for indexing
155 //
156 // Differences from [span.obs]:
157 // - using size_t instead of ptrdiff_t to represent size()
158 //
159 // Differences from [span.elem]:
160 // - using size_t instead of ptrdiff_t for indexing
161 //
162 // Furthermore, all constructors and methods are marked noexcept due to the lack
163 // of exceptions in Chromium.
164 //
165 // Due to the lack of class template argument deduction guides in C++14
166 // appropriate make_span() utility functions are provided.
167 
168 // [span], class template span
169 template <typename T, size_t Extent>
170 class span {
171  public:
172   using element_type = T;
173   using value_type = std::remove_cv_t<T>;
174   using index_type = size_t;
175   using difference_type = ptrdiff_t;
176   using pointer = T*;
177   using reference = T&;
178   using iterator = T*;
179   using const_iterator = const T*;
180   using reverse_iterator = std::reverse_iterator<iterator>;
181   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
182   static constexpr index_type extent = Extent;
183 
184   // [span.cons], span constructors, copy, assignment, and destructor
185   constexpr span() noexcept : data_(nullptr), size_(0) {
186     static_assert(Extent == dynamic_extent || Extent == 0, "Invalid Extent");
187   }
188 
189   constexpr span(T* data, size_t size) noexcept : data_(data), size_(size) {
190     CHECK(Extent == dynamic_extent || Extent == size);
191   }
192 
193   // Artificially templatized to break ambiguity for span(ptr, 0).
194   template <typename = void>
195   constexpr span(T* begin, T* end) noexcept : span(begin, end - begin) {
196     // Note: CHECK_LE is not constexpr, hence regular CHECK must be used.
197     CHECK(begin <= end);
198   }
199 
200   template <
201       size_t N,
202       typename = internal::EnableIfSpanCompatibleArray<T (&)[N], N, T, Extent>>
203   constexpr span(T (&array)[N]) noexcept : span(base::data(array), N) {}
204 
205   template <
206       size_t N,
207       typename = internal::
208           EnableIfSpanCompatibleArray<std::array<value_type, N>&, N, T, Extent>>
209   constexpr span(std::array<value_type, N>& array) noexcept
210       : span(base::data(array), N) {}
211 
212   template <size_t N,
213             typename = internal::EnableIfSpanCompatibleArray<
214                 const std::array<value_type, N>&,
215                 N,
216                 T,
217                 Extent>>
218   constexpr span(const std::array<value_type, N>& array) noexcept
219       : span(base::data(array), N) {}
220 
221   // Conversion from a container that has compatible base::data() and integral
222   // base::size().
223   template <typename Container,
224             typename = internal::EnableIfSpanCompatibleContainer<Container&, T>>
225   constexpr span(Container& container) noexcept
226       : span(base::data(container), base::size(container)) {}
227 
228   template <
229       typename Container,
230       typename = internal::EnableIfSpanCompatibleContainer<const Container&, T>>
231   span(const Container& container) noexcept
232       : span(base::data(container), base::size(container)) {}
233 
234   constexpr span(const span& other) noexcept = default;
235 
236   // Conversions from spans of compatible types and extents: this allows a
237   // span<T> to be seamlessly used as a span<const T>, but not the other way
238   // around. If extent is not dynamic, OtherExtent has to be equal to Extent.
239   template <
240       typename U,
241       size_t OtherExtent,
242       typename =
243           internal::EnableIfLegalSpanConversion<U, OtherExtent, T, Extent>>
244   constexpr span(const span<U, OtherExtent>& other)
245       : span(other.data(), other.size()) {}
246 
247   constexpr span& operator=(const span& other) noexcept = default;
248   ~span() noexcept = default;
249 
250   // [span.sub], span subviews
251   template <size_t Count>
252   constexpr span<T, Count> first() const noexcept {
253     static_assert(Extent == dynamic_extent || Count <= Extent,
254                   "Count must not exceed Extent");
255     CHECK(Extent != dynamic_extent || Count <= size());
256     return {data(), Count};
257   }
258 
259   template <size_t Count>
260   constexpr span<T, Count> last() const noexcept {
261     static_assert(Extent == dynamic_extent || Count <= Extent,
262                   "Count must not exceed Extent");
263     CHECK(Extent != dynamic_extent || Count <= size());
264     return {data() + (size() - Count), Count};
265   }
266 
267   template <size_t Offset, size_t Count = dynamic_extent>
268   constexpr span<T,
269                  (Count != dynamic_extent
270                      ? Count
271                      : (Extent != dynamic_extent ? Extent - Offset
272                                                  : dynamic_extent))>
273   subspan() const noexcept {
274     static_assert(Extent == dynamic_extent || Offset <= Extent,
275                   "Offset must not exceed Extent");
276     static_assert(Extent == dynamic_extent || Count == dynamic_extent ||
277                       Count <= Extent - Offset,
278                   "Count must not exceed Extent - Offset");
279     CHECK(Extent != dynamic_extent || Offset <= size());
280     CHECK(Extent != dynamic_extent || Count == dynamic_extent ||
281           Count <= size() - Offset);
282     return {data() + Offset, Count != dynamic_extent ? Count : size() - Offset};
283   }
284 
285   constexpr span<T, dynamic_extent> first(size_t count) const noexcept {
286     // Note: CHECK_LE is not constexpr, hence regular CHECK must be used.
287     CHECK(count <= size());
288     return {data(), count};
289   }
290 
291   constexpr span<T, dynamic_extent> last(size_t count) const noexcept {
292     // Note: CHECK_LE is not constexpr, hence regular CHECK must be used.
293     CHECK(count <= size());
294     return {data() + (size() - count), count};
295   }
296 
297   constexpr span<T, dynamic_extent> subspan(size_t offset,
298                                             size_t count = dynamic_extent) const
299       noexcept {
300     // Note: CHECK_LE is not constexpr, hence regular CHECK must be used.
301     CHECK(offset <= size());
302     CHECK(count == dynamic_extent || count <= size() - offset);
303     return {data() + offset, count != dynamic_extent ? count : size() - offset};
304   }
305 
306   // [span.obs], span observers
307   constexpr size_t size() const noexcept { return size_; }
308   constexpr size_t size_bytes() const noexcept { return size() * sizeof(T); }
309   constexpr bool empty() const noexcept { return size() == 0; }
310 
311   // [span.elem], span element access
312   constexpr T& operator[](size_t idx) const noexcept {
313     // Note: CHECK_LT is not constexpr, hence regular CHECK must be used.
314     CHECK(idx < size());
315     return *(data() + idx);
316   }
317 
318   constexpr T& operator()(size_t idx) const noexcept {
319     // Note: CHECK_LT is not constexpr, hence regular CHECK must be used.
320     CHECK(idx < size());
321     return *(data() + idx);
322   }
323 
324   constexpr T* data() const noexcept { return data_; }
325 
326   // [span.iter], span iterator support
327   constexpr iterator begin() const noexcept { return data(); }
328   constexpr iterator end() const noexcept { return data() + size(); }
329 
330   constexpr const_iterator cbegin() const noexcept { return begin(); }
331   constexpr const_iterator cend() const noexcept { return end(); }
332 
333   constexpr reverse_iterator rbegin() const noexcept {
334     return reverse_iterator(end());
335   }
336   constexpr reverse_iterator rend() const noexcept {
337     return reverse_iterator(begin());
338   }
339 
340   constexpr const_reverse_iterator crbegin() const noexcept {
341     return const_reverse_iterator(cend());
342   }
343   constexpr const_reverse_iterator crend() const noexcept {
344     return const_reverse_iterator(cbegin());
345   }
346 
347  private:
348   T* data_;
349   size_t size_;
350 };
351 
352 // span<T, Extent>::extent can not be declared inline prior to C++17, hence this
353 // definition is required.
354 template <class T, size_t Extent>
355 constexpr size_t span<T, Extent>::extent;
356 
357 // [span.comparison], span comparison operators
358 // Relational operators. Equality is a element-wise comparison.
359 template <typename T, size_t X, typename U, size_t Y>
360 constexpr bool operator==(span<T, X> lhs, span<U, Y> rhs) noexcept {
361   return std::equal(lhs.cbegin(), lhs.cend(), rhs.cbegin(), rhs.cend());
362 }
363 
364 template <typename T, size_t X, typename U, size_t Y>
365 constexpr bool operator!=(span<T, X> lhs, span<U, Y> rhs) noexcept {
366   return !(lhs == rhs);
367 }
368 
369 template <typename T, size_t X, typename U, size_t Y>
370 constexpr bool operator<(span<T, X> lhs, span<U, Y> rhs) noexcept {
371   return std::lexicographical_compare(lhs.cbegin(), lhs.cend(), rhs.cbegin(),
372                                       rhs.cend());
373 }
374 
375 template <typename T, size_t X, typename U, size_t Y>
376 constexpr bool operator<=(span<T, X> lhs, span<U, Y> rhs) noexcept {
377   return !(rhs < lhs);
378 }
379 
380 template <typename T, size_t X, typename U, size_t Y>
381 constexpr bool operator>(span<T, X> lhs, span<U, Y> rhs) noexcept {
382   return rhs < lhs;
383 }
384 
385 template <typename T, size_t X, typename U, size_t Y>
386 constexpr bool operator>=(span<T, X> lhs, span<U, Y> rhs) noexcept {
387   return !(lhs < rhs);
388 }
389 
390 // [span.objectrep], views of object representation
391 template <typename T, size_t X>
392 span<const uint8_t, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)>
393 as_bytes(span<T, X> s) noexcept {
394   return {reinterpret_cast<const uint8_t*>(s.data()), s.size_bytes()};
395 }
396 
397 template <typename T,
398           size_t X,
399           typename = std::enable_if_t<!std::is_const<T>::value>>
400 span<uint8_t, (X == dynamic_extent ? dynamic_extent : sizeof(T) * X)>
401 as_writable_bytes(span<T, X> s) noexcept {
402   return {reinterpret_cast<uint8_t*>(s.data()), s.size_bytes()};
403 }
404 
405 // Type-deducing helpers for constructing a span.
406 template <typename T>
407 constexpr span<T> make_span(T* data, size_t size) noexcept {
408   return {data, size};
409 }
410 
411 template <typename T>
412 constexpr span<T> make_span(T* begin, T* end) noexcept {
413   return {begin, end};
414 }
415 
416 template <typename T, size_t N>
417 constexpr span<T, N> make_span(T (&array)[N]) noexcept {
418   return array;
419 }
420 
421 template <typename T, size_t N>
422 constexpr span<T, N> make_span(std::array<T, N>& array) noexcept {
423   return array;
424 }
425 
426 template <typename T, size_t N>
427 constexpr span<const T, N> make_span(const std::array<T, N>& array) noexcept {
428   return array;
429 }
430 
431 template <typename Container,
432           typename T = typename Container::value_type,
433           typename = internal::EnableIfSpanCompatibleContainer<Container&, T>>
434 constexpr span<T> make_span(Container& container) noexcept {
435   return container;
436 }
437 
438 template <
439     typename Container,
440     typename T = const typename Container::value_type,
441     typename = internal::EnableIfSpanCompatibleContainer<const Container&, T>>
442 constexpr span<T> make_span(const Container& container) noexcept {
443   return container;
444 }
445 
446 template <typename T, size_t X>
447 constexpr span<T, X> make_span(const span<T, X>& span) noexcept {
448   return span;
449 }
450 
451 }  // namespace base
452 
453 #endif  // BASE_CONTAINERS_SPAN_H_
454