Line data Source code
1 : // Copyright 2018 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #ifndef V8_BASE_SMALL_VECTOR_H_
6 : #define V8_BASE_SMALL_VECTOR_H_
7 :
8 : #include <type_traits>
9 :
10 : #include "src/base/bits.h"
11 : #include "src/base/macros.h"
12 :
13 : namespace v8 {
14 : namespace base {
15 :
16 : // Minimal SmallVector implementation. Uses inline storage first, switches to
17 : // malloc when it overflows.
18 : template <typename T, size_t kInlineSize>
19 : class SmallVector {
20 : // Currently only support trivially copyable and trivially destructible data
21 : // types, as it uses memcpy to copy elements and never calls destructors.
22 : ASSERT_TRIVIALLY_COPYABLE(T);
23 : STATIC_ASSERT(std::is_trivially_destructible<T>::value);
24 :
25 : public:
26 3734087 : SmallVector() = default;
27 : SmallVector(const SmallVector& other) V8_NOEXCEPT { *this = other; }
28 346196 : SmallVector(SmallVector&& other) V8_NOEXCEPT { *this = std::move(other); }
29 :
30 : ~SmallVector() {
31 2318555 : if (is_big()) free(begin_);
32 : }
33 :
34 440049 : SmallVector& operator=(const SmallVector& other) V8_NOEXCEPT {
35 146683 : if (this == &other) return *this;
36 : size_t other_size = other.size();
37 146683 : if (capacity() < other_size) {
38 : // Create large-enough heap-allocated storage.
39 27 : if (is_big()) free(begin_);
40 27 : begin_ = reinterpret_cast<T*>(malloc(sizeof(T) * other_size));
41 27 : end_of_storage_ = begin_ + other_size;
42 : }
43 146683 : memcpy(begin_, other.begin_, sizeof(T) * other_size);
44 146683 : end_ = begin_ + other_size;
45 146683 : return *this;
46 : }
47 :
48 346197 : SmallVector& operator=(SmallVector&& other) V8_NOEXCEPT {
49 173095 : if (this == &other) return *this;
50 173102 : if (other.is_big()) {
51 0 : if (is_big()) free(begin_);
52 0 : begin_ = other.begin_;
53 0 : end_ = other.end_;
54 0 : end_of_storage_ = other.end_of_storage_;
55 : other.reset();
56 : } else {
57 : DCHECK_GE(capacity(), other.size()); // Sanity check.
58 : size_t other_size = other.size();
59 173102 : memcpy(begin_, other.begin_, sizeof(T) * other_size);
60 173102 : end_ = begin_ + other_size;
61 : }
62 : return *this;
63 : }
64 :
65 : T* data() const { return begin_; }
66 : T* begin() const { return begin_; }
67 : T* end() const { return end_; }
68 2726549 : size_t size() const { return end_ - begin_; }
69 : bool empty() const { return end_ == begin_; }
70 305885 : size_t capacity() const { return end_of_storage_ - begin_; }
71 :
72 : T& back() {
73 : DCHECK_NE(0, size());
74 : return end_[-1];
75 : }
76 :
77 : T& operator[](size_t index) {
78 : DCHECK_GT(size(), index);
79 7269596 : return begin_[index];
80 : }
81 :
82 : const T& operator[](size_t index) const {
83 : DCHECK_GT(size(), index);
84 70634 : return begin_[index];
85 : }
86 :
87 : template <typename... Args>
88 4334414 : void emplace_back(Args&&... args) {
89 4334414 : if (V8_UNLIKELY(end_ == end_of_storage_)) Grow();
90 4334491 : new (end_) T(std::forward<Args>(args)...);
91 4334491 : ++end_;
92 4334491 : }
93 :
94 : void pop_back(size_t count = 1) {
95 : DCHECK_GE(size(), count);
96 2801694 : end_ -= count;
97 : }
98 :
99 138914 : void resize_no_init(size_t new_size) {
100 : // Resizing without initialization is safe if T is trivially copyable.
101 : ASSERT_TRIVIALLY_COPYABLE(T);
102 138914 : if (new_size > capacity()) Grow(new_size);
103 138914 : end_ = begin_ + new_size;
104 138914 : }
105 :
106 : // Clear without freeing any storage.
107 : void clear() { end_ = begin_; }
108 :
109 : // Clear and go back to inline storage.
110 : void reset() {
111 0 : begin_ = inline_storage_begin();
112 0 : end_ = begin_;
113 0 : end_of_storage_ = begin_ + kInlineSize;
114 : }
115 :
116 : private:
117 1588587 : T* begin_ = inline_storage_begin();
118 : T* end_ = begin_;
119 1761685 : T* end_of_storage_ = begin_ + kInlineSize;
120 : typename std::aligned_storage<sizeof(T) * kInlineSize, alignof(T)>::type
121 : inline_storage_;
122 :
123 40576 : void Grow(size_t min_capacity = 0) {
124 20288 : size_t in_use = end_ - begin_;
125 : size_t new_capacity =
126 60864 : base::bits::RoundUpToPowerOfTwo(std::max(min_capacity, 2 * capacity()));
127 20288 : T* new_storage = reinterpret_cast<T*>(malloc(sizeof(T) * new_capacity));
128 20288 : memcpy(new_storage, begin_, sizeof(T) * in_use);
129 20288 : if (is_big()) free(begin_);
130 20288 : begin_ = new_storage;
131 20288 : end_ = new_storage + in_use;
132 20288 : end_of_storage_ = new_storage + new_capacity;
133 20288 : }
134 :
135 2511972 : bool is_big() const { return begin_ != inline_storage_begin(); }
136 :
137 : T* inline_storage_begin() { return reinterpret_cast<T*>(&inline_storage_); }
138 : const T* inline_storage_begin() const {
139 : return reinterpret_cast<const T*>(&inline_storage_);
140 : }
141 : };
142 :
143 : } // namespace base
144 : } // namespace v8
145 :
146 : #endif // V8_BASE_SMALL_VECTOR_H_
|