Line data Source code
1 : /*
2 : * Copyright 2004 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 WEBRTC_BASE_BUFFER_H_
12 : #define WEBRTC_BASE_BUFFER_H_
13 :
14 : #include <algorithm>
15 : #include <cstring>
16 : #include <memory>
17 : #include <type_traits>
18 : #include <utility>
19 :
20 : #include "webrtc/base/array_view.h"
21 : #include "webrtc/base/checks.h"
22 : #include "webrtc/base/type_traits.h"
23 :
24 : namespace rtc {
25 :
26 : namespace internal {
27 :
28 : // (Internal; please don't use outside this file.) Determines if elements of
29 : // type U are compatible with a BufferT<T>. For most types, we just ignore
30 : // top-level const and forbid top-level volatile and require T and U to be
31 : // otherwise equal, but all byte-sized integers (notably char, int8_t, and
32 : // uint8_t) are compatible with each other. (Note: We aim to get rid of this
33 : // behavior, and treat all types the same.)
34 : template <typename T, typename U>
35 : struct BufferCompat {
36 : static constexpr bool value =
37 : !std::is_volatile<U>::value &&
38 : ((std::is_integral<T>::value && sizeof(T) == 1)
39 : ? (std::is_integral<U>::value && sizeof(U) == 1)
40 : : (std::is_same<T, typename std::remove_const<U>::type>::value));
41 : };
42 :
43 : } // namespace internal
44 :
45 : // Basic buffer class, can be grown and shrunk dynamically.
46 : // Unlike std::string/vector, does not initialize data when increasing size.
47 : template <typename T>
48 0 : class BufferT {
49 : // We want T's destructor and default constructor to be trivial, i.e. perform
50 : // no action, so that we don't have to touch the memory we allocate and
51 : // deallocate. And we want T to be trivially copyable, so that we can copy T
52 : // instances with std::memcpy. This is precisely the definition of a trivial
53 : // type.
54 : static_assert(std::is_trivial<T>::value, "T must be a trivial type.");
55 :
56 : // This class relies heavily on being able to mutate its data.
57 : static_assert(!std::is_const<T>::value, "T may not be const");
58 :
59 : public:
60 : // An empty BufferT.
61 0 : BufferT() : size_(0), capacity_(0), data_(nullptr) {
62 0 : RTC_DCHECK(IsConsistent());
63 0 : }
64 :
65 : // Disable copy construction and copy assignment, since copying a buffer is
66 : // expensive enough that we want to force the user to be explicit about it.
67 : BufferT(const BufferT&) = delete;
68 : BufferT& operator=(const BufferT&) = delete;
69 :
70 0 : BufferT(BufferT&& buf)
71 : : size_(buf.size()),
72 : capacity_(buf.capacity()),
73 0 : data_(std::move(buf.data_)) {
74 0 : RTC_DCHECK(IsConsistent());
75 0 : buf.OnMovedFrom();
76 0 : }
77 :
78 : // Construct a buffer with the specified number of uninitialized elements.
79 0 : explicit BufferT(size_t size) : BufferT(size, size) {}
80 :
81 0 : BufferT(size_t size, size_t capacity)
82 : : size_(size),
83 0 : capacity_(std::max(size, capacity)),
84 0 : data_(new T[capacity_]) {
85 0 : RTC_DCHECK(IsConsistent());
86 0 : }
87 :
88 : // Construct a buffer and copy the specified number of elements into it.
89 : template <typename U,
90 : typename std::enable_if<
91 : internal::BufferCompat<T, U>::value>::type* = nullptr>
92 0 : BufferT(const U* data, size_t size) : BufferT(data, size, size) {}
93 :
94 : template <typename U,
95 : typename std::enable_if<
96 : internal::BufferCompat<T, U>::value>::type* = nullptr>
97 0 : BufferT(U* data, size_t size, size_t capacity) : BufferT(size, capacity) {
98 : static_assert(sizeof(T) == sizeof(U), "");
99 0 : std::memcpy(data_.get(), data, size * sizeof(U));
100 0 : }
101 :
102 : // Construct a buffer from the contents of an array.
103 : template <typename U,
104 : size_t N,
105 : typename std::enable_if<
106 : internal::BufferCompat<T, U>::value>::type* = nullptr>
107 : BufferT(U (&array)[N]) : BufferT(array, N) {}
108 :
109 : // Get a pointer to the data. Just .data() will give you a (const) T*, but if
110 : // T is a byte-sized integer, you may also use .data<U>() for any other
111 : // byte-sized integer U.
112 : template <typename U = T,
113 : typename std::enable_if<
114 : internal::BufferCompat<T, U>::value>::type* = nullptr>
115 0 : const U* data() const {
116 0 : RTC_DCHECK(IsConsistent());
117 0 : return reinterpret_cast<U*>(data_.get());
118 : }
119 :
120 : template <typename U = T,
121 : typename std::enable_if<
122 : internal::BufferCompat<T, U>::value>::type* = nullptr>
123 0 : U* data() {
124 0 : RTC_DCHECK(IsConsistent());
125 0 : return reinterpret_cast<U*>(data_.get());
126 : }
127 :
128 0 : bool empty() const {
129 0 : RTC_DCHECK(IsConsistent());
130 0 : return size_ == 0;
131 : }
132 :
133 0 : size_t size() const {
134 0 : RTC_DCHECK(IsConsistent());
135 0 : return size_;
136 : }
137 :
138 0 : size_t capacity() const {
139 0 : RTC_DCHECK(IsConsistent());
140 0 : return capacity_;
141 : }
142 :
143 0 : BufferT& operator=(BufferT&& buf) {
144 0 : RTC_DCHECK(IsConsistent());
145 0 : RTC_DCHECK(buf.IsConsistent());
146 0 : size_ = buf.size_;
147 0 : capacity_ = buf.capacity_;
148 0 : data_ = std::move(buf.data_);
149 0 : buf.OnMovedFrom();
150 0 : return *this;
151 : }
152 :
153 0 : bool operator==(const BufferT& buf) const {
154 0 : RTC_DCHECK(IsConsistent());
155 0 : if (size_ != buf.size_) {
156 0 : return false;
157 : }
158 : if (std::is_integral<T>::value) {
159 : // Optimization.
160 0 : return std::memcmp(data_.get(), buf.data_.get(), size_ * sizeof(T)) == 0;
161 : }
162 : for (size_t i = 0; i < size_; ++i) {
163 : if (data_[i] != buf.data_[i]) {
164 : return false;
165 : }
166 : }
167 : return true;
168 : }
169 :
170 : bool operator!=(const BufferT& buf) const { return !(*this == buf); }
171 :
172 0 : T& operator[](size_t index) {
173 0 : RTC_DCHECK_LT(index, size_);
174 0 : return data()[index];
175 : }
176 :
177 : T operator[](size_t index) const {
178 : RTC_DCHECK_LT(index, size_);
179 : return data()[index];
180 : }
181 :
182 : // The SetData functions replace the contents of the buffer. They accept the
183 : // same input types as the constructors.
184 : template <typename U,
185 : typename std::enable_if<
186 : internal::BufferCompat<T, U>::value>::type* = nullptr>
187 0 : void SetData(const U* data, size_t size) {
188 0 : RTC_DCHECK(IsConsistent());
189 0 : size_ = 0;
190 0 : AppendData(data, size);
191 0 : }
192 :
193 : template <typename U,
194 : size_t N,
195 : typename std::enable_if<
196 : internal::BufferCompat<T, U>::value>::type* = nullptr>
197 : void SetData(const U (&array)[N]) {
198 : SetData(array, N);
199 : }
200 :
201 : template <typename W,
202 : typename std::enable_if<
203 : HasDataAndSize<const W, const T>::value>::type* = nullptr>
204 : void SetData(const W& w) {
205 : SetData(w.data(), w.size());
206 : }
207 :
208 : // Replace the data in the buffer with at most |max_elements| of data, using
209 : // the function |setter|, which should have the following signature:
210 : // size_t setter(ArrayView<U> view)
211 : // |setter| is given an appropriately typed ArrayView of the area in which to
212 : // write the data (i.e. starting at the beginning of the buffer) and should
213 : // return the number of elements actually written. This number must be <=
214 : // |max_elements|.
215 : template <typename U = T,
216 : typename F,
217 : typename std::enable_if<
218 : internal::BufferCompat<T, U>::value>::type* = nullptr>
219 : size_t SetData(size_t max_elements, F&& setter) {
220 : RTC_DCHECK(IsConsistent());
221 : size_ = 0;
222 : return AppendData<U>(max_elements, std::forward<F>(setter));
223 : }
224 :
225 : // The AppendData functions add data to the end of the buffer. They accept
226 : // the same input types as the constructors.
227 : template <typename U,
228 : typename std::enable_if<
229 : internal::BufferCompat<T, U>::value>::type* = nullptr>
230 0 : void AppendData(const U* data, size_t size) {
231 0 : RTC_DCHECK(IsConsistent());
232 0 : const size_t new_size = size_ + size;
233 0 : EnsureCapacityWithHeadroom(new_size, true);
234 : static_assert(sizeof(T) == sizeof(U), "");
235 0 : std::memcpy(data_.get() + size_, data, size * sizeof(U));
236 0 : size_ = new_size;
237 0 : RTC_DCHECK(IsConsistent());
238 0 : }
239 :
240 : template <typename U,
241 : size_t N,
242 : typename std::enable_if<
243 : internal::BufferCompat<T, U>::value>::type* = nullptr>
244 : void AppendData(const U (&array)[N]) {
245 : AppendData(array, N);
246 : }
247 :
248 : template <typename W,
249 : typename std::enable_if<
250 : HasDataAndSize<const W, const T>::value>::type* = nullptr>
251 : void AppendData(const W& w) {
252 : AppendData(w.data(), w.size());
253 : }
254 :
255 : template <typename U,
256 : typename std::enable_if<
257 : internal::BufferCompat<T, U>::value>::type* = nullptr>
258 0 : void AppendData(const U& item) {
259 0 : AppendData(&item, 1);
260 0 : }
261 :
262 : // Append at most |max_elements| to the end of the buffer, using the function
263 : // |setter|, which should have the following signature:
264 : // size_t setter(ArrayView<U> view)
265 : // |setter| is given an appropriately typed ArrayView of the area in which to
266 : // write the data (i.e. starting at the former end of the buffer) and should
267 : // return the number of elements actually written. This number must be <=
268 : // |max_elements|.
269 : template <typename U = T,
270 : typename F,
271 : typename std::enable_if<
272 : internal::BufferCompat<T, U>::value>::type* = nullptr>
273 0 : size_t AppendData(size_t max_elements, F&& setter) {
274 0 : RTC_DCHECK(IsConsistent());
275 0 : const size_t old_size = size_;
276 0 : SetSize(old_size + max_elements);
277 0 : U* base_ptr = data<U>() + old_size;
278 0 : size_t written_elements = setter(rtc::ArrayView<U>(base_ptr, max_elements));
279 :
280 0 : RTC_CHECK_LE(written_elements, max_elements);
281 0 : size_ = old_size + written_elements;
282 0 : RTC_DCHECK(IsConsistent());
283 0 : return written_elements;
284 : }
285 :
286 : // Sets the size of the buffer. If the new size is smaller than the old, the
287 : // buffer contents will be kept but truncated; if the new size is greater,
288 : // the existing contents will be kept and the new space will be
289 : // uninitialized.
290 0 : void SetSize(size_t size) {
291 0 : EnsureCapacityWithHeadroom(size, true);
292 0 : size_ = size;
293 0 : }
294 :
295 : // Ensure that the buffer size can be increased to at least capacity without
296 : // further reallocation. (Of course, this operation might need to reallocate
297 : // the buffer.)
298 0 : void EnsureCapacity(size_t capacity) {
299 : // Don't allocate extra headroom, since the user is asking for a specific
300 : // capacity.
301 0 : EnsureCapacityWithHeadroom(capacity, false);
302 0 : }
303 :
304 : // Resets the buffer to zero size without altering capacity. Works even if the
305 : // buffer has been moved from.
306 0 : void Clear() {
307 0 : size_ = 0;
308 0 : RTC_DCHECK(IsConsistent());
309 0 : }
310 :
311 : // Swaps two buffers. Also works for buffers that have been moved from.
312 : friend void swap(BufferT& a, BufferT& b) {
313 : using std::swap;
314 : swap(a.size_, b.size_);
315 : swap(a.capacity_, b.capacity_);
316 : swap(a.data_, b.data_);
317 : }
318 :
319 : private:
320 0 : void EnsureCapacityWithHeadroom(size_t capacity, bool extra_headroom) {
321 0 : RTC_DCHECK(IsConsistent());
322 0 : if (capacity <= capacity_)
323 0 : return;
324 :
325 : // If the caller asks for extra headroom, ensure that the new capacity is
326 : // >= 1.5 times the old capacity. Any constant > 1 is sufficient to prevent
327 : // quadratic behavior; as to why we pick 1.5 in particular, see
328 : // https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md and
329 : // http://www.gahcep.com/cpp-internals-stl-vector-part-1/.
330 : const size_t new_capacity =
331 0 : extra_headroom ? std::max(capacity, capacity_ + capacity_ / 2)
332 0 : : capacity;
333 :
334 0 : std::unique_ptr<T[]> new_data(new T[new_capacity]);
335 0 : std::memcpy(new_data.get(), data_.get(), size_ * sizeof(T));
336 0 : data_ = std::move(new_data);
337 0 : capacity_ = new_capacity;
338 0 : RTC_DCHECK(IsConsistent());
339 : }
340 :
341 : // Precondition for all methods except Clear and the destructor.
342 : // Postcondition for all methods except move construction and move
343 : // assignment, which leave the moved-from object in a possibly inconsistent
344 : // state.
345 0 : bool IsConsistent() const {
346 0 : return (data_ || capacity_ == 0) && capacity_ >= size_;
347 : }
348 :
349 : // Called when *this has been moved from. Conceptually it's a no-op, but we
350 : // can mutate the state slightly to help subsequent sanity checks catch bugs.
351 0 : void OnMovedFrom() {
352 : #if RTC_DCHECK_IS_ON
353 : // Make *this consistent and empty. Shouldn't be necessary, but better safe
354 : // than sorry.
355 0 : size_ = 0;
356 0 : capacity_ = 0;
357 : #else
358 : // Ensure that *this is always inconsistent, to provoke bugs.
359 : size_ = 1;
360 : capacity_ = 0;
361 : #endif
362 0 : }
363 :
364 : size_t size_;
365 : size_t capacity_;
366 : std::unique_ptr<T[]> data_;
367 : };
368 :
369 : // By far the most common sort of buffer.
370 : using Buffer = BufferT<uint8_t>;
371 :
372 : } // namespace rtc
373 :
374 : #endif // WEBRTC_BASE_BUFFER_H_
|
