blob: 3539ace5bcd86d1a6eebd9f559b625dfb10cc8ca [file] [log] [blame]
Karl Wibergc1269372020-03-02 19:23:411/*
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
21namespace webrtc {
22namespace bounded_inline_vector_impl {
23
24template <bool...>
25struct 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.
30template <bool... Bs>
31using AllTrue = std::is_same<BoolPack<Bs..., true>, BoolPack<true, Bs...>>;
32
33template <typename To, typename... Froms>
34using 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`.
39template <typename T>
40void InitializeElements(T* data) {}
41template <typename T, typename U, typename... Us>
42void 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
Karl Wibergd084ea92020-03-02 20:49:2048// Default initializes uninitialized array elements.
49// TODO(kwiberg): Replace with std::uninitialized_default_construct_n() (C++17).
50template <typename T>
51void 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
Karl Wibergc1269372020-03-02 19:23:4158// Copies from source to uninitialized destination. Caller is responsible for
59// ensuring that there is enough space in `dst_data`.
60template <typename T>
61void 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`.
72template <typename T>
73void 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.
88template <typename T>
89void 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.
100static 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.
119template <typename T,
120 int fixed_capacity,
121 bool is_trivial = std::is_trivial<T>::value,
122 bool is_small = (sizeof(T) * fixed_capacity <= kSmallSize)>
123struct 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>
129 explicit Storage(Ts&&... elements) : size(sizeof...(Ts)) {
130 InitializeElements(data, std::forward<Ts>(elements)...);
131 }
132
133 Storage(const Storage& other) {
134 CopyElements(other.data, other.size, data, &size);
135 }
136
137 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
156 ~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.
168template <typename T, int fixed_capacity>
169struct 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.
190template <typename T, int fixed_capacity>
191struct 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_