| // Copyright 2017 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef BASE_CONTAINERS_VECTOR_BUFFERS_H_ |
| #define BASE_CONTAINERS_VECTOR_BUFFERS_H_ |
| |
| #include <stdlib.h> |
| #include <string.h> |
| |
| #include <type_traits> |
| #include <utility> |
| |
| #include "base/logging.h" |
| |
| namespace base { |
| namespace internal { |
| |
| // Internal implementation detail of base/containers. |
| // |
| // Implements a vector-like buffer that holds a certain capacity of T. Unlike |
| // std::vector, VectorBuffer never constructs or destructs its arguments, and |
| // can't change sizes. But it does implement templates to assist in efficient |
| // moving and destruction of those items manually. |
| // |
| // In particular, the destructor function does not iterate over the items if |
| // there is no destructor. Moves should be implemented as a memcpy/memmove for |
| // trivially copyable objects (POD) otherwise, it should be a std::move if |
| // possible, and as a last resort it falls back to a copy. This behavior is |
| // similar to std::vector. |
| // |
| // No special consideration is done for noexcept move constructors since |
| // we compile without exceptions. |
| // |
| // The current API does not support moving overlapping ranges. |
| template <typename T> |
| class VectorBuffer { |
| public: |
| constexpr VectorBuffer() = default; |
| |
| #if defined(__clang__) |
| // This constructor converts an uninitialized void* to a T* which triggers |
| // clang Control Flow Integrity. Since this is as-designed, disable. |
| __attribute__((no_sanitize("cfi-unrelated-cast", "vptr"))) |
| #endif |
| VectorBuffer(size_t count) |
| : buffer_(reinterpret_cast<T*>(malloc(sizeof(T) * count))), |
| capacity_(count) { |
| } |
| VectorBuffer(VectorBuffer&& other) noexcept |
| : buffer_(other.buffer_), capacity_(other.capacity_) { |
| other.buffer_ = nullptr; |
| other.capacity_ = 0; |
| } |
| |
| ~VectorBuffer() { free(buffer_); } |
| |
| VectorBuffer& operator=(VectorBuffer&& other) { |
| free(buffer_); |
| buffer_ = other.buffer_; |
| capacity_ = other.capacity_; |
| |
| other.buffer_ = nullptr; |
| other.capacity_ = 0; |
| return *this; |
| } |
| |
| size_t capacity() const { return capacity_; } |
| |
| T& operator[](size_t i) { return buffer_[i]; } |
| const T& operator[](size_t i) const { return buffer_[i]; } |
| T* begin() { return buffer_; } |
| T* end() { return &buffer_[capacity_]; } |
| |
| // DestructRange ------------------------------------------------------------ |
| |
| // Trivially destructible objects need not have their destructors called. |
| template <typename T2 = T, |
| typename std::enable_if<std::is_trivially_destructible<T2>::value, |
| int>::type = 0> |
| void DestructRange(T* begin, T* end) {} |
| |
| // Non-trivially destructible objects must have their destructors called |
| // individually. |
| template <typename T2 = T, |
| typename std::enable_if<!std::is_trivially_destructible<T2>::value, |
| int>::type = 0> |
| void DestructRange(T* begin, T* end) { |
| while (begin != end) { |
| begin->~T(); |
| begin++; |
| } |
| } |
| |
| // MoveRange ---------------------------------------------------------------- |
| // |
| // The destructor will be called (as necessary) for all moved types. The |
| // ranges must not overlap. |
| // |
| // The parameters and begin and end (one past the last) of the input buffer, |
| // and the address of the first element to copy to. There must be sufficient |
| // room in the destination for all items in the range [begin, end). |
| |
| // Trivially copyable types can use memcpy. trivially copyable implies |
| // that there is a trivial destructor as we don't have to call it. |
| template <typename T2 = T, |
| typename std::enable_if<std::is_trivially_copyable<T2>::value, |
| int>::type = 0> |
| static void MoveRange(T* from_begin, T* from_end, T* to) { |
| DCHECK(!RangesOverlap(from_begin, from_end, to)); |
| memcpy(to, from_begin, (from_end - from_begin) * sizeof(T)); |
| } |
| |
| // Not trivially copyable, but movable: call the move constructor and |
| // destruct the original. |
| template <typename T2 = T, |
| typename std::enable_if<std::is_move_constructible<T2>::value && |
| !std::is_trivially_copyable<T2>::value, |
| int>::type = 0> |
| static void MoveRange(T* from_begin, T* from_end, T* to) { |
| DCHECK(!RangesOverlap(from_begin, from_end, to)); |
| while (from_begin != from_end) { |
| new (to) T(std::move(*from_begin)); |
| from_begin->~T(); |
| from_begin++; |
| to++; |
| } |
| } |
| |
| // Not movable, not trivially copyable: call the copy constructor and |
| // destruct the original. |
| template <typename T2 = T, |
| typename std::enable_if<!std::is_move_constructible<T2>::value && |
| !std::is_trivially_copyable<T2>::value, |
| int>::type = 0> |
| static void MoveRange(T* from_begin, T* from_end, T* to) { |
| DCHECK(!RangesOverlap(from_begin, from_end, to)); |
| while (from_begin != from_end) { |
| new (to) T(*from_begin); |
| from_begin->~T(); |
| from_begin++; |
| to++; |
| } |
| } |
| |
| private: |
| static bool RangesOverlap(const T* from_begin, |
| const T* from_end, |
| const T* to) { |
| return !(to >= from_end || to + (from_end - from_begin) <= from_begin); |
| } |
| |
| T* buffer_ = nullptr; |
| size_t capacity_ = 0; |
| |
| VectorBuffer(const VectorBuffer&) = delete; |
| VectorBuffer& operator=(const VectorBuffer&) = delete; |
| }; |
| |
| } // namespace internal |
| } // namespace base |
| |
| #endif // BASE_CONTAINERS_VECTOR_BUFFERS_H_ |