array_view.h (13194B)
1 /* 2 * Copyright 2015 The WebRTC Project Authors. All rights reserved. 3 * 4 * Use of this source code is governed by a BSD-style license 5 * that can be found in the LICENSE file in the root of the source 6 * tree. An additional intellectual property rights grant can be found 7 * in the file PATENTS. All contributing project authors may 8 * be found in the AUTHORS file in the root of the source tree. 9 */ 10 11 #ifndef API_ARRAY_VIEW_H_ 12 #define API_ARRAY_VIEW_H_ 13 14 #include <algorithm> 15 #include <array> 16 #include <cstddef> 17 #include <iterator> 18 #include <type_traits> 19 20 #include "rtc_base/checks.h" 21 #include "rtc_base/type_traits.h" 22 23 namespace webrtc { 24 25 // tl;dr: ArrayView is the same thing as gsl::span from the Guideline 26 // Support Library. 27 // 28 // Many functions read from or write to arrays. The obvious way to do this is 29 // to use two arguments, a pointer to the first element and an element count: 30 // 31 // bool Contains17(const int* arr, size_t size) { 32 // for (size_t i = 0; i < size; ++i) { 33 // if (arr[i] == 17) 34 // return true; 35 // } 36 // return false; 37 // } 38 // 39 // This is flexible, since it doesn't matter how the array is stored (C array, 40 // std::vector, Buffer, ...), but it's error-prone because the caller 41 // has to correctly specify the array length: 42 // 43 // Contains17(arr, std::size(arr)); // C array 44 // Contains17(arr.data(), arr.size()); // std::vector 45 // Contains17(arr, size); // pointer + size 46 // ... 47 // 48 // It's also kind of messy to have two separate arguments for what is 49 // conceptually a single thing. 50 // 51 // Enter ArrayView<T>. It contains a T pointer (to an array it doesn't 52 // own) and a count, and supports the basic things you'd expect, such as 53 // indexing and iteration. It allows us to write our function like this: 54 // 55 // bool Contains17(ArrayView<const int> arr) { 56 // for (auto e : arr) { 57 // if (e == 17) 58 // return true; 59 // } 60 // return false; 61 // } 62 // 63 // And even better, because a bunch of things will implicitly convert to 64 // ArrayView, we can call it like this: 65 // 66 // Contains17(arr); // C array 67 // Contains17(arr); // std::vector 68 // Contains17(ArrayView<int>(arr, size)); // pointer + size 69 // Contains17(nullptr); // nullptr -> empty ArrayView 70 // ... 71 // 72 // ArrayView<T> stores both a pointer and a size, but you may also use 73 // ArrayView<T, N>, which has a size that's fixed at compile time (which means 74 // it only has to store the pointer). 75 // 76 // One important point is that ArrayView<T> and ArrayView<const T> are 77 // different types, which allow and don't allow mutation of the array elements, 78 // respectively. The implicit conversions work just like you'd hope, so that 79 // e.g. vector<int> will convert to either ArrayView<int> or ArrayView<const 80 // int>, but const vector<int> will convert only to ArrayView<const int>. 81 // (ArrayView itself can be the source type in such conversions, so 82 // ArrayView<int> will convert to ArrayView<const int>.) 83 // 84 // Note: ArrayView is tiny (just a pointer and a count if variable-sized, just 85 // a pointer if fix-sized) and trivially copyable, so it's probably cheaper to 86 // pass it by value than by const reference. 87 88 namespace array_view_internal { 89 90 // Magic constant for indicating that the size of an ArrayView is variable 91 // instead of fixed. 92 enum : std::ptrdiff_t { kArrayViewVarSize = -4711 }; 93 94 // Base class for ArrayViews of fixed nonzero size. 95 template <typename T, std::ptrdiff_t Size> 96 class ArrayViewBase { 97 static_assert(Size > 0, "ArrayView size must be variable or non-negative"); 98 99 public: 100 ArrayViewBase(T* data, size_t /* size */) : data_(data) {} 101 102 static constexpr size_t size() { return Size; } 103 static constexpr bool empty() { return false; } 104 T* data() const { return data_; } 105 106 protected: 107 static constexpr bool fixed_size() { return true; } 108 109 private: 110 T* data_; 111 }; 112 113 // Specialized base class for ArrayViews of fixed zero size. 114 template <typename T> 115 class ArrayViewBase<T, 0> { 116 public: 117 explicit ArrayViewBase(T* /* data */, size_t /* size */) {} 118 119 static constexpr size_t size() { return 0; } 120 static constexpr bool empty() { return true; } 121 T* data() const { return nullptr; } 122 123 protected: 124 static constexpr bool fixed_size() { return true; } 125 }; 126 127 // Specialized base class for ArrayViews of variable size. 128 template <typename T> 129 class ArrayViewBase<T, array_view_internal::kArrayViewVarSize> { 130 public: 131 ArrayViewBase(T* data, size_t size) 132 : data_(size == 0 ? nullptr : data), size_(size) {} 133 134 size_t size() const { return size_; } 135 bool empty() const { return size_ == 0; } 136 T* data() const { return data_; } 137 138 protected: 139 static constexpr bool fixed_size() { return false; } 140 141 private: 142 T* data_; 143 size_t size_; 144 }; 145 146 } // namespace array_view_internal 147 148 template <typename T, 149 std::ptrdiff_t Size = array_view_internal::kArrayViewVarSize> 150 class ArrayView final : public array_view_internal::ArrayViewBase<T, Size> { 151 public: 152 using value_type = T; 153 using reference = value_type&; 154 using const_reference = const value_type&; 155 using pointer = value_type*; 156 using const_pointer = const value_type*; 157 using const_iterator = const T*; 158 159 // Construct an ArrayView from a pointer and a length. 160 template <typename U> 161 ArrayView(U* data, size_t size) 162 : array_view_internal::ArrayViewBase<T, Size>::ArrayViewBase(data, size) { 163 RTC_DCHECK_EQ(size == 0 ? nullptr : data, this->data()); 164 RTC_DCHECK_EQ(size, this->size()); 165 RTC_DCHECK_EQ(!this->data(), 166 this->size() == 0); // data is null iff size == 0. 167 } 168 169 // Construct an empty ArrayView. Note that fixed-size ArrayViews of size > 0 170 // cannot be empty. 171 ArrayView() : ArrayView(nullptr, 0) {} 172 ArrayView(std::nullptr_t) // NOLINT 173 : ArrayView() {} 174 ArrayView(std::nullptr_t, size_t size) 175 : ArrayView(static_cast<T*>(nullptr), size) { 176 static_assert(Size == 0 || Size == array_view_internal::kArrayViewVarSize, 177 ""); 178 RTC_DCHECK_EQ(0, size); 179 } 180 181 // Construct an ArrayView from a C-style array. 182 template <typename U, size_t N> 183 ArrayView(U (&array)[N]) // NOLINT 184 : ArrayView(array, N) { 185 static_assert(Size == N || Size == array_view_internal::kArrayViewVarSize, 186 "Array size must match ArrayView size"); 187 } 188 189 // (Only if size is fixed.) Construct a fixed size ArrayView<T, N> from a 190 // non-const std::array instance. For an ArrayView with variable size, the 191 // used ctor is ArrayView(U& u) instead. 192 template <typename U, 193 size_t N, 194 typename std::enable_if< 195 Size == static_cast<std::ptrdiff_t>(N)>::type* = nullptr> 196 ArrayView(std::array<U, N>& u) // NOLINT 197 : ArrayView(u.data(), u.size()) {} 198 199 // (Only if size is fixed.) Construct a fixed size ArrayView<T, N> where T is 200 // const from a const(expr) std::array instance. For an ArrayView with 201 // variable size, the used ctor is ArrayView(U& u) instead. 202 template <typename U, 203 size_t N, 204 typename std::enable_if< 205 Size == static_cast<std::ptrdiff_t>(N)>::type* = nullptr> 206 ArrayView(const std::array<U, N>& u) // NOLINT 207 : ArrayView(u.data(), u.size()) {} 208 209 // (Only if size is fixed.) Construct an ArrayView from any type U that has a 210 // static constexpr size() method whose return value is equal to Size, and a 211 // data() method whose return value converts implicitly to T*. In particular, 212 // this means we allow conversion from ArrayView<T, N> to ArrayView<const T, 213 // N>, but not the other way around. We also don't allow conversion from 214 // ArrayView<T> to ArrayView<T, N>, or from ArrayView<T, M> to ArrayView<T, 215 // N> when M != N. 216 template <typename U, 217 typename std::enable_if_t< 218 !std::is_same_v<ArrayView, std::remove_reference_t<U>> && 219 Size != array_view_internal::kArrayViewVarSize && 220 HasDataAndSize<U, T>::value>* = nullptr> 221 ArrayView(U& u) // NOLINT 222 : ArrayView(u.data(), u.size()) { 223 static_assert(U::size() == Size, "Sizes must match exactly"); 224 } 225 226 template <typename U, 227 typename std::enable_if_t< 228 !std::is_same_v<ArrayView, std::remove_reference_t<U>> && 229 Size != array_view_internal::kArrayViewVarSize && 230 HasDataAndSize<U, T>::value>* = nullptr> 231 ArrayView(const U& u) // NOLINT(runtime/explicit) 232 : ArrayView(u.data(), u.size()) { 233 static_assert(U::size() == Size, "Sizes must match exactly"); 234 } 235 236 // (Only if size is variable.) Construct an ArrayView from any type U that 237 // has a size() method whose return value converts implicitly to size_t, and 238 // a data() method whose return value converts implicitly to T*. In 239 // particular, this means we allow conversion from ArrayView<T> to 240 // ArrayView<const T>, but not the other way around. Other allowed 241 // conversions include 242 // ArrayView<T, N> to ArrayView<T> or ArrayView<const T>, 243 // std::vector<T> to ArrayView<T> or ArrayView<const T>, 244 // const std::vector<T> to ArrayView<const T>, 245 // Buffer to ArrayView<uint8_t> or ArrayView<const uint8_t>, and 246 // const Buffer to ArrayView<const uint8_t>. 247 template <typename U, 248 typename std::enable_if_t< 249 !std::is_same_v<ArrayView, std::remove_reference_t<U>> && 250 Size == array_view_internal::kArrayViewVarSize && 251 HasDataAndSize<U, T>::value>* = nullptr> 252 ArrayView(U& u) // NOLINT 253 : ArrayView(u.data(), u.size()) {} 254 255 template <typename U, 256 typename std::enable_if_t< 257 !std::is_same_v<ArrayView, std::remove_reference_t<U>> && 258 Size == array_view_internal::kArrayViewVarSize && 259 HasDataAndSize<U, T>::value>* = nullptr> 260 ArrayView(const U& u) // NOLINT(runtime/explicit) 261 : ArrayView(u.data(), u.size()) {} 262 263 // Indexing and iteration. These allow mutation even if the ArrayView is 264 // const, because the ArrayView doesn't own the array. (To prevent mutation, 265 // use a const element type.) 266 T& operator[](size_t idx) const { 267 RTC_DCHECK_LT(idx, this->size()); 268 RTC_DCHECK(this->data()); 269 return this->data()[idx]; 270 } 271 T* begin() const { return this->data(); } 272 T* end() const { return this->data() + this->size(); } 273 const T* cbegin() const { return this->data(); } 274 const T* cend() const { return this->data() + this->size(); } 275 std::reverse_iterator<T*> rbegin() const { 276 return std::make_reverse_iterator(end()); 277 } 278 std::reverse_iterator<T*> rend() const { 279 return std::make_reverse_iterator(begin()); 280 } 281 std::reverse_iterator<const T*> crbegin() const { 282 return std::make_reverse_iterator(cend()); 283 } 284 std::reverse_iterator<const T*> crend() const { 285 return std::make_reverse_iterator(cbegin()); 286 } 287 288 ArrayView<T> subview(size_t offset, size_t size) const { 289 return offset < this->size() 290 ? ArrayView<T>(this->data() + offset, 291 std::min(size, this->size() - offset)) 292 : ArrayView<T>(); 293 } 294 ArrayView<T> subview(size_t offset) const { 295 return subview(offset, this->size()); 296 } 297 }; 298 299 // Comparing two ArrayViews compares their (pointer,size) pairs; it does *not* 300 // dereference the pointers. 301 template <typename T, std::ptrdiff_t Size1, std::ptrdiff_t Size2> 302 bool operator==(const ArrayView<T, Size1>& a, const ArrayView<T, Size2>& b) { 303 return a.data() == b.data() && a.size() == b.size(); 304 } 305 template <typename T, std::ptrdiff_t Size1, std::ptrdiff_t Size2> 306 bool operator!=(const ArrayView<T, Size1>& a, const ArrayView<T, Size2>& b) { 307 return !(a == b); 308 } 309 310 // Variable-size ArrayViews are the size of two pointers; fixed-size ArrayViews 311 // are the size of one pointer. (And as a special case, fixed-size ArrayViews 312 // of size 0 require no storage.) 313 static_assert(sizeof(ArrayView<int>) == 2 * sizeof(int*), ""); 314 static_assert(sizeof(ArrayView<int, 17>) == sizeof(int*), ""); 315 static_assert(std::is_empty<ArrayView<int, 0>>::value, ""); 316 317 template <typename T> 318 inline ArrayView<T> MakeArrayView(T* data, size_t size) { 319 return ArrayView<T>(data, size); 320 } 321 322 // Only for primitive types that have the same size and aligment. 323 // Allow reinterpret cast of the array view to another primitive type of the 324 // same size. 325 // Template arguments order is (U, T, Size) to allow deduction of the template 326 // arguments in client calls: reinterpret_array_view<target_type>(array_view). 327 template <typename U, typename T, std::ptrdiff_t Size> 328 inline ArrayView<U, Size> reinterpret_array_view(ArrayView<T, Size> view) { 329 static_assert(sizeof(U) == sizeof(T) && alignof(U) == alignof(T), 330 "ArrayView reinterpret_cast is only supported for casting " 331 "between views that represent the same chunk of memory."); 332 static_assert( 333 std::is_fundamental<T>::value && std::is_fundamental<U>::value, 334 "ArrayView reinterpret_cast is only supported for casting between " 335 "fundamental types."); 336 return ArrayView<U, Size>(reinterpret_cast<U*>(view.data()), view.size()); 337 } 338 339 } // namespace webrtc 340 341 342 #endif // API_ARRAY_VIEW_H_