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 kSize>
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 : static constexpr size_t kInlineSize = kSize;
27 :
28 3267292 : SmallVector() = default;
29 : SmallVector(const SmallVector& other) V8_NOEXCEPT { *this = other; }
30 303472 : SmallVector(SmallVector&& other) V8_NOEXCEPT { *this = std::move(other); }
31 :
32 : ~SmallVector() {
33 2029842 : if (is_big()) free(begin_);
34 2029842 : }
35 :
36 129549 : SmallVector& operator=(const SmallVector& other) V8_NOEXCEPT {
37 129549 : if (this == &other) return *this;
38 : size_t other_size = other.size();
39 129552 : if (capacity() < other_size) {
40 : // Create large-enough heap-allocated storage.
41 32 : if (is_big()) free(begin_);
42 32 : begin_ = reinterpret_cast<T*>(malloc(sizeof(T) * other_size));
43 32 : end_of_storage_ = begin_ + other_size;
44 : }
45 129552 : memcpy(begin_, other.begin_, sizeof(T) * other_size);
46 129552 : end_ = begin_ + other_size;
47 129552 : return *this;
48 : }
49 :
50 151721 : SmallVector& operator=(SmallVector&& other) V8_NOEXCEPT {
51 151721 : if (this == &other) return *this;
52 151726 : if (other.is_big()) {
53 0 : if (is_big()) free(begin_);
54 0 : begin_ = other.begin_;
55 0 : end_ = other.end_;
56 0 : end_of_storage_ = other.end_of_storage_;
57 : other.reset();
58 : } else {
59 : DCHECK_GE(capacity(), other.size()); // Sanity check.
60 : size_t other_size = other.size();
61 151726 : memcpy(begin_, other.begin_, sizeof(T) * other_size);
62 151726 : end_ = begin_ + other_size;
63 : }
64 : return *this;
65 : }
66 :
67 : T* data() { return begin_; }
68 : const T* data() const { return begin_; }
69 :
70 : T* begin() { return begin_; }
71 : const T* begin() const { return begin_; }
72 :
73 : T* end() { return end_; }
74 : const T* end() const { return end_; }
75 :
76 2372910 : size_t size() const { return end_ - begin_; }
77 : bool empty() const { return end_ == begin_; }
78 482381 : size_t capacity() const { return end_of_storage_ - begin_; }
79 :
80 : T& back() {
81 : DCHECK_NE(0, size());
82 459853 : return end_[-1];
83 : }
84 :
85 : T& operator[](size_t index) {
86 : DCHECK_GT(size(), index);
87 6016133 : return begin_[index];
88 : }
89 :
90 : const T& operator[](size_t index) const {
91 : DCHECK_GT(size(), index);
92 62804 : return begin_[index];
93 : }
94 :
95 : template <typename... Args>
96 3311137 : void emplace_back(Args&&... args) {
97 3311137 : if (V8_UNLIKELY(end_ == end_of_storage_)) Grow();
98 3311363 : new (end_) T(std::forward<Args>(args)...);
99 3311363 : ++end_;
100 3311363 : }
101 :
102 : void pop_back(size_t count = 1) {
103 : DCHECK_GE(size(), count);
104 2392382 : end_ -= count;
105 : }
106 :
107 122289 : void resize_no_init(size_t new_size) {
108 : // Resizing without initialization is safe if T is trivially copyable.
109 : ASSERT_TRIVIALLY_COPYABLE(T);
110 336057 : if (new_size > capacity()) Grow(new_size);
111 336057 : end_ = begin_ + new_size;
112 122289 : }
113 :
114 : // Clear without freeing any storage.
115 : void clear() { end_ = begin_; }
116 :
117 : // Clear and go back to inline storage.
118 : void reset() {
119 0 : begin_ = inline_storage_begin();
120 0 : end_ = begin_;
121 0 : end_of_storage_ = begin_ + kInlineSize;
122 : }
123 :
124 : private:
125 : T* begin_ = inline_storage_begin();
126 : T* end_ = begin_;
127 1539903 : T* end_of_storage_ = begin_ + kInlineSize;
128 : typename std::aligned_storage<sizeof(T) * kInlineSize, alignof(T)>::type
129 : inline_storage_;
130 :
131 16772 : void Grow(size_t min_capacity = 0) {
132 16772 : size_t in_use = end_ - begin_;
133 : size_t new_capacity =
134 50316 : base::bits::RoundUpToPowerOfTwo(std::max(min_capacity, 2 * capacity()));
135 16772 : T* new_storage = reinterpret_cast<T*>(malloc(sizeof(T) * new_capacity));
136 16772 : memcpy(new_storage, begin_, sizeof(T) * in_use);
137 16772 : if (is_big()) free(begin_);
138 16772 : begin_ = new_storage;
139 16772 : end_ = new_storage + in_use;
140 16772 : end_of_storage_ = new_storage + new_capacity;
141 16772 : }
142 :
143 2181568 : bool is_big() const { return begin_ != inline_storage_begin(); }
144 :
145 1539903 : T* inline_storage_begin() { return reinterpret_cast<T*>(&inline_storage_); }
146 : const T* inline_storage_begin() const {
147 1653969 : return reinterpret_cast<const T*>(&inline_storage_);
148 : }
149 : };
150 :
151 : } // namespace base
152 : } // namespace v8
153 :
154 : #endif // V8_BASE_SMALL_VECTOR_H_
|