blob: efc642d6fc692caf9ec4e372de3c75a1fcab884a [file] [log] [blame]
kwiberg529662a2017-09-04 05:43:17 -07001/*
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
Mirko Bonadei92ea95e2017-09-15 06:47:31 +020011#ifndef API_ARRAY_VIEW_H_
12#define API_ARRAY_VIEW_H_
kwiberg529662a2017-09-04 05:43:17 -070013
14#include <algorithm>
Yves Gerey665174f2018-06-19 15:03:05 +020015#include <array>
kwiberg529662a2017-09-04 05:43:17 -070016#include <type_traits>
17
Mirko Bonadei92ea95e2017-09-15 06:47:31 +020018#include "rtc_base/checks.h"
19#include "rtc_base/type_traits.h"
kwiberg529662a2017-09-04 05:43:17 -070020
21namespace rtc {
22
23// tl;dr: rtc::ArrayView is the same thing as gsl::span from the Guideline
24// Support Library.
25//
26// Many functions read from or write to arrays. The obvious way to do this is
27// to use two arguments, a pointer to the first element and an element count:
28//
29// bool Contains17(const int* arr, size_t size) {
30// for (size_t i = 0; i < size; ++i) {
31// if (arr[i] == 17)
32// return true;
33// }
34// return false;
35// }
36//
37// This is flexible, since it doesn't matter how the array is stored (C array,
38// std::vector, rtc::Buffer, ...), but it's error-prone because the caller has
39// to correctly specify the array length:
40//
41// Contains17(arr, arraysize(arr)); // C array
42// Contains17(arr.data(), arr.size()); // std::vector
43// Contains17(arr, size); // pointer + size
44// ...
45//
46// It's also kind of messy to have two separate arguments for what is
47// conceptually a single thing.
48//
49// Enter rtc::ArrayView<T>. It contains a T pointer (to an array it doesn't
50// own) and a count, and supports the basic things you'd expect, such as
51// indexing and iteration. It allows us to write our function like this:
52//
53// bool Contains17(rtc::ArrayView<const int> arr) {
54// for (auto e : arr) {
55// if (e == 17)
56// return true;
57// }
58// return false;
59// }
60//
61// And even better, because a bunch of things will implicitly convert to
62// ArrayView, we can call it like this:
63//
64// Contains17(arr); // C array
65// Contains17(arr); // std::vector
66// Contains17(rtc::ArrayView<int>(arr, size)); // pointer + size
67// Contains17(nullptr); // nullptr -> empty ArrayView
68// ...
69//
70// ArrayView<T> stores both a pointer and a size, but you may also use
71// ArrayView<T, N>, which has a size that's fixed at compile time (which means
72// it only has to store the pointer).
73//
74// One important point is that ArrayView<T> and ArrayView<const T> are
75// different types, which allow and don't allow mutation of the array elements,
76// respectively. The implicit conversions work just like you'd hope, so that
77// e.g. vector<int> will convert to either ArrayView<int> or ArrayView<const
78// int>, but const vector<int> will convert only to ArrayView<const int>.
79// (ArrayView itself can be the source type in such conversions, so
80// ArrayView<int> will convert to ArrayView<const int>.)
81//
82// Note: ArrayView is tiny (just a pointer and a count if variable-sized, just
83// a pointer if fix-sized) and trivially copyable, so it's probably cheaper to
84// pass it by value than by const reference.
85
86namespace impl {
87
88// Magic constant for indicating that the size of an ArrayView is variable
89// instead of fixed.
90enum : std::ptrdiff_t { kArrayViewVarSize = -4711 };
91
92// Base class for ArrayViews of fixed nonzero size.
93template <typename T, std::ptrdiff_t Size>
94class ArrayViewBase {
95 static_assert(Size > 0, "ArrayView size must be variable or non-negative");
96
97 public:
98 ArrayViewBase(T* data, size_t size) : data_(data) {}
99
100 static constexpr size_t size() { return Size; }
101 static constexpr bool empty() { return false; }
102 T* data() const { return data_; }
103
104 protected:
105 static constexpr bool fixed_size() { return true; }
106
107 private:
108 T* data_;
109};
110
111// Specialized base class for ArrayViews of fixed zero size.
112template <typename T>
113class ArrayViewBase<T, 0> {
114 public:
115 explicit ArrayViewBase(T* data, size_t size) {}
116
117 static constexpr size_t size() { return 0; }
118 static constexpr bool empty() { return true; }
119 T* data() const { return nullptr; }
120
121 protected:
122 static constexpr bool fixed_size() { return true; }
123};
124
125// Specialized base class for ArrayViews of variable size.
126template <typename T>
127class ArrayViewBase<T, impl::kArrayViewVarSize> {
128 public:
129 ArrayViewBase(T* data, size_t size)
130 : data_(size == 0 ? nullptr : data), size_(size) {}
131
132 size_t size() const { return size_; }
133 bool empty() const { return size_ == 0; }
134 T* data() const { return data_; }
135
136 protected:
137 static constexpr bool fixed_size() { return false; }
138
139 private:
140 T* data_;
141 size_t size_;
142};
143
144} // namespace impl
145
146template <typename T, std::ptrdiff_t Size = impl::kArrayViewVarSize>
147class ArrayView final : public impl::ArrayViewBase<T, Size> {
148 public:
149 using value_type = T;
150 using const_iterator = const T*;
151
152 // Construct an ArrayView from a pointer and a length.
153 template <typename U>
154 ArrayView(U* data, size_t size)
155 : impl::ArrayViewBase<T, Size>::ArrayViewBase(data, size) {
156 RTC_DCHECK_EQ(size == 0 ? nullptr : data, this->data());
157 RTC_DCHECK_EQ(size, this->size());
158 RTC_DCHECK_EQ(!this->data(),
159 this->size() == 0); // data is null iff size == 0.
160 }
161
162 // Construct an empty ArrayView. Note that fixed-size ArrayViews of size > 0
163 // cannot be empty.
164 ArrayView() : ArrayView(nullptr, 0) {}
165 ArrayView(std::nullptr_t) // NOLINT
166 : ArrayView() {}
167 ArrayView(std::nullptr_t, size_t size)
168 : ArrayView(static_cast<T*>(nullptr), size) {
169 static_assert(Size == 0 || Size == impl::kArrayViewVarSize, "");
170 RTC_DCHECK_EQ(0, size);
171 }
172
Alessio Bazzica858c4d72018-05-14 16:33:58 +0200173 // Construct an ArrayView from a C-style array.
kwiberg529662a2017-09-04 05:43:17 -0700174 template <typename U, size_t N>
175 ArrayView(U (&array)[N]) // NOLINT
176 : ArrayView(array, N) {
177 static_assert(Size == N || Size == impl::kArrayViewVarSize,
178 "Array size must match ArrayView size");
179 }
180
Alessio Bazzica28a325b2018-05-15 14:57:51 +0200181 // (Only if size is fixed.) Construct a fixed size ArrayView<T, N> from a
182 // non-const std::array instance. For an ArrayView with variable size, the
183 // used ctor is ArrayView(U& u) instead.
Alessio Bazzica858c4d72018-05-14 16:33:58 +0200184 template <typename U,
185 size_t N,
186 typename std::enable_if<
187 Size == static_cast<std::ptrdiff_t>(N)>::type* = nullptr>
188 ArrayView(std::array<U, N>& u) // NOLINT
189 : ArrayView(u.data(), u.size()) {}
190
Alessio Bazzica28a325b2018-05-15 14:57:51 +0200191 // (Only if size is fixed.) Construct a fixed size ArrayView<T, N> where T is
192 // const from a const(expr) std::array instance. For an ArrayView with
193 // variable size, the used ctor is ArrayView(U& u) instead.
194 template <typename U,
195 size_t N,
196 typename std::enable_if<
197 Size == static_cast<std::ptrdiff_t>(N)>::type* = nullptr>
198 ArrayView(const std::array<U, N>& u) // NOLINT
199 : ArrayView(u.data(), u.size()) {}
200
kwiberg529662a2017-09-04 05:43:17 -0700201 // (Only if size is fixed.) Construct an ArrayView from any type U that has a
202 // static constexpr size() method whose return value is equal to Size, and a
203 // data() method whose return value converts implicitly to T*. In particular,
204 // this means we allow conversion from ArrayView<T, N> to ArrayView<const T,
205 // N>, but not the other way around. We also don't allow conversion from
206 // ArrayView<T> to ArrayView<T, N>, or from ArrayView<T, M> to ArrayView<T,
207 // N> when M != N.
208 template <
209 typename U,
210 typename std::enable_if<Size != impl::kArrayViewVarSize &&
211 HasDataAndSize<U, T>::value>::type* = nullptr>
212 ArrayView(U& u) // NOLINT
213 : ArrayView(u.data(), u.size()) {
214 static_assert(U::size() == Size, "Sizes must match exactly");
215 }
216
217 // (Only if size is variable.) Construct an ArrayView from any type U that
218 // has a size() method whose return value converts implicitly to size_t, and
219 // a data() method whose return value converts implicitly to T*. In
220 // particular, this means we allow conversion from ArrayView<T> to
221 // ArrayView<const T>, but not the other way around. Other allowed
222 // conversions include
223 // ArrayView<T, N> to ArrayView<T> or ArrayView<const T>,
224 // std::vector<T> to ArrayView<T> or ArrayView<const T>,
225 // const std::vector<T> to ArrayView<const T>,
226 // rtc::Buffer to ArrayView<uint8_t> or ArrayView<const uint8_t>, and
227 // const rtc::Buffer to ArrayView<const uint8_t>.
228 template <
229 typename U,
230 typename std::enable_if<Size == impl::kArrayViewVarSize &&
231 HasDataAndSize<U, T>::value>::type* = nullptr>
232 ArrayView(U& u) // NOLINT
233 : ArrayView(u.data(), u.size()) {}
234
235 // Indexing and iteration. These allow mutation even if the ArrayView is
236 // const, because the ArrayView doesn't own the array. (To prevent mutation,
237 // use a const element type.)
238 T& operator[](size_t idx) const {
239 RTC_DCHECK_LT(idx, this->size());
240 RTC_DCHECK(this->data());
241 return this->data()[idx];
242 }
243 T* begin() const { return this->data(); }
244 T* end() const { return this->data() + this->size(); }
245 const T* cbegin() const { return this->data(); }
246 const T* cend() const { return this->data() + this->size(); }
247
248 ArrayView<T> subview(size_t offset, size_t size) const {
249 return offset < this->size()
250 ? ArrayView<T>(this->data() + offset,
251 std::min(size, this->size() - offset))
252 : ArrayView<T>();
253 }
254 ArrayView<T> subview(size_t offset) const {
255 return subview(offset, this->size());
256 }
257};
258
259// Comparing two ArrayViews compares their (pointer,size) pairs; it does *not*
260// dereference the pointers.
261template <typename T, std::ptrdiff_t Size1, std::ptrdiff_t Size2>
262bool operator==(const ArrayView<T, Size1>& a, const ArrayView<T, Size2>& b) {
263 return a.data() == b.data() && a.size() == b.size();
264}
265template <typename T, std::ptrdiff_t Size1, std::ptrdiff_t Size2>
266bool operator!=(const ArrayView<T, Size1>& a, const ArrayView<T, Size2>& b) {
267 return !(a == b);
268}
269
270// Variable-size ArrayViews are the size of two pointers; fixed-size ArrayViews
271// are the size of one pointer. (And as a special case, fixed-size ArrayViews
272// of size 0 require no storage.)
273static_assert(sizeof(ArrayView<int>) == 2 * sizeof(int*), "");
274static_assert(sizeof(ArrayView<int, 17>) == sizeof(int*), "");
275static_assert(std::is_empty<ArrayView<int, 0>>::value, "");
276
277template <typename T>
278inline ArrayView<T> MakeArrayView(T* data, size_t size) {
279 return ArrayView<T>(data, size);
280}
281
282} // namespace rtc
283
Mirko Bonadei92ea95e2017-09-15 06:47:31 +0200284#endif // API_ARRAY_VIEW_H_