1 /*
2 * Copyright 2020 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 RTC_BASE_BOUNDED_INLINE_VECTOR_IMPL_H_
12 #define RTC_BASE_BOUNDED_INLINE_VECTOR_IMPL_H_
13
14 #include <stdint.h>
15
16 #include <cstring>
17 #include <memory>
18 #include <type_traits>
19 #include <utility>
20
21 namespace webrtc {
22 namespace bounded_inline_vector_impl {
23
24 template <bool...>
25 struct BoolPack;
26
27 // Tests if all its parameters (x0, x1, ..., xn) are true. The implementation
28 // checks whether (x0, x1, ..., xn, true) == (true, x0, x1, ..., xn), which is
29 // true iff true == x0 && x0 == x1 && x1 == x2 ... && xn-1 == xn && xn == true.
30 template <bool... Bs>
31 using AllTrue = std::is_same<BoolPack<Bs..., true>, BoolPack<true, Bs...>>;
32
33 template <typename To, typename... Froms>
34 using AllConvertible = AllTrue<std::is_convertible<Froms, To>::value...>;
35
36 // Initializes part of an uninitialized array. Unlike normal array
37 // initialization, does not zero the remaining array elements. Caller is
38 // responsible for ensuring that there is enough space in `data`.
39 template <typename T>
InitializeElements(T * data)40 void InitializeElements(T* data) {}
41 template <typename T, typename U, typename... Us>
InitializeElements(T * data,U && element,Us &&...elements)42 void InitializeElements(T* data, U&& element, Us&&... elements) {
43 // Placement new, because we construct a new object in uninitialized memory.
44 ::new (data) T(std::forward<U>(element));
45 InitializeElements(data + 1, std::forward<Us>(elements)...);
46 }
47
48 // Default initializes uninitialized array elements.
49 // TODO(kwiberg): Replace with std::uninitialized_default_construct_n() (C++17).
50 template <typename T>
DefaultInitializeElements(T * data,int size)51 void DefaultInitializeElements(T* data, int size) {
52 for (int i = 0; i < size; ++i) {
53 // Placement new, because we construct a new object in uninitialized memory.
54 ::new (&data[i]) T;
55 }
56 }
57
58 // Copies from source to uninitialized destination. Caller is responsible for
59 // ensuring that there is enough space in `dst_data`.
60 template <typename T>
CopyElements(const T * src_data,int src_size,T * dst_data,int * dst_size)61 void CopyElements(const T* src_data, int src_size, T* dst_data, int* dst_size) {
62 if /*constexpr*/ (std::is_trivially_copy_constructible<T>::value) {
63 std::memcpy(dst_data, src_data, src_size * sizeof(T));
64 } else {
65 std::uninitialized_copy_n(src_data, src_size, dst_data);
66 }
67 *dst_size = src_size;
68 }
69
70 // Moves from source to uninitialized destination. Caller is responsible for
71 // ensuring that there is enough space in `dst_data`.
72 template <typename T>
MoveElements(T * src_data,int src_size,T * dst_data,int * dst_size)73 void MoveElements(T* src_data, int src_size, T* dst_data, int* dst_size) {
74 if /*constexpr*/ (std::is_trivially_move_constructible<T>::value) {
75 std::memcpy(dst_data, src_data, src_size * sizeof(T));
76 } else {
77 // TODO(kwiberg): Use std::uninitialized_move_n() instead (C++17).
78 for (int i = 0; i < src_size; ++i) {
79 // Placement new, because we create a new object in uninitialized
80 // memory.
81 ::new (&dst_data[i]) T(std::move(src_data[i]));
82 }
83 }
84 *dst_size = src_size;
85 }
86
87 // Destroys elements, leaving them uninitialized.
88 template <typename T>
DestroyElements(T * data,int size)89 void DestroyElements(T* data, int size) {
90 if /*constexpr*/ (!std::is_trivially_destructible<T>::value) {
91 for (int i = 0; i < size; ++i) {
92 data[i].~T();
93 }
94 }
95 }
96
97 // If elements are trivial and the total capacity is at most this many bytes,
98 // copy everything instead of just the elements that are in use; this is more
99 // efficient, and makes BoundedInlineVector trivially copyable.
100 static constexpr int kSmallSize = 64;
101
102 // Storage implementations.
103 //
104 // There are diferent Storage structs for diferent kinds of element types. The
105 // common contract is the following:
106 //
107 // * They have public `size` variables and `data` array members.
108 //
109 // * Their owner is responsible for enforcing the invariant that the first
110 // `size` elements in `data` are initialized, and the remaining elements are
111 // not initialized.
112 //
113 // * They implement default construction, construction with one or more
114 // elements, copy/move construction, copy/move assignment, and destruction;
115 // the owner must ensure that the invariant holds whenever these operations
116 // occur.
117
118 // Storage implementation for nontrivial element types.
119 template <typename T,
120 int fixed_capacity,
121 bool is_trivial = std::is_trivial<T>::value,
122 bool is_small = (sizeof(T) * fixed_capacity <= kSmallSize)>
123 struct Storage {
124 static_assert(!std::is_trivial<T>::value, "");
125
126 template <
127 typename... Ts,
128 typename std::enable_if_t<AllConvertible<T, Ts...>::value>* = nullptr>
StorageStorage129 explicit Storage(Ts&&... elements) : size(sizeof...(Ts)) {
130 InitializeElements(data, std::forward<Ts>(elements)...);
131 }
132
StorageStorage133 Storage(const Storage& other) {
134 CopyElements(other.data, other.size, data, &size);
135 }
136
StorageStorage137 Storage(Storage&& other) {
138 MoveElements(other.data, other.size, data, &size);
139 }
140
141 Storage& operator=(const Storage& other) {
142 if (this != &other) {
143 DestroyElements(data, size);
144 CopyElements(other.data, other.size, data, &size);
145 }
146 return *this;
147 }
148
149 Storage& operator=(Storage&& other) {
150 DestroyElements(data, size);
151 size = 0; // Needed in case of self assignment.
152 MoveElements(other.data, other.size, data, &size);
153 return *this;
154 }
155
~StorageStorage156 ~Storage() { DestroyElements(data, size); }
157
158 int size;
159 union {
160 // Since this array is in a union, we get to construct and destroy it
161 // manually.
162 T data[fixed_capacity]; // NOLINT(runtime/arrays)
163 };
164 };
165
166 // Storage implementation for trivial element types when the capacity is small
167 // enough that we can cheaply copy everything.
168 template <typename T, int fixed_capacity>
169 struct Storage<T, fixed_capacity, /*is_trivial=*/true, /*is_small=*/true> {
170 static_assert(std::is_trivial<T>::value, "");
171 static_assert(sizeof(T) * fixed_capacity <= kSmallSize, "");
172
173 template <
174 typename... Ts,
175 typename std::enable_if_t<AllConvertible<T, Ts...>::value>* = nullptr>
176 explicit Storage(Ts&&... elements) : size(sizeof...(Ts)) {
177 InitializeElements(data, std::forward<Ts>(elements)...);
178 }
179
180 Storage(const Storage&) = default;
181 Storage& operator=(const Storage&) = default;
182 ~Storage() = default;
183
184 int size;
185 T data[fixed_capacity]; // NOLINT(runtime/arrays)
186 };
187
188 // Storage implementation for trivial element types when the capacity is large
189 // enough that we want to avoid copying uninitialized elements.
190 template <typename T, int fixed_capacity>
191 struct Storage<T, fixed_capacity, /*is_trivial=*/true, /*is_small=*/false> {
192 static_assert(std::is_trivial<T>::value, "");
193 static_assert(sizeof(T) * fixed_capacity > kSmallSize, "");
194
195 template <
196 typename... Ts,
197 typename std::enable_if_t<AllConvertible<T, Ts...>::value>* = nullptr>
198 explicit Storage(Ts&&... elements) : size(sizeof...(Ts)) {
199 InitializeElements(data, std::forward<Ts>(elements)...);
200 }
201
202 Storage(const Storage& other) : size(other.size) {
203 std::memcpy(data, other.data, other.size * sizeof(T));
204 }
205
206 Storage& operator=(const Storage& other) {
207 if (this != &other) {
208 size = other.size;
209 std::memcpy(data, other.data, other.size * sizeof(T));
210 }
211 return *this;
212 }
213
214 ~Storage() = default;
215
216 int size;
217 union {
218 T data[fixed_capacity]; // NOLINT(runtime/arrays)
219 };
220 };
221
222 } // namespace bounded_inline_vector_impl
223 } // namespace webrtc
224
225 #endif // RTC_BASE_BOUNDED_INLINE_VECTOR_IMPL_H_
226