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
