Line data Source code
1 : // Copyright 2014 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_VECTOR_H_
6 : #define V8_VECTOR_H_
7 :
8 : #include <algorithm>
9 : #include <cstring>
10 : #include <iterator>
11 :
12 : #include "src/allocation.h"
13 : #include "src/checks.h"
14 : #include "src/globals.h"
15 :
16 : namespace v8 {
17 : namespace internal {
18 :
19 :
20 : template <typename T>
21 : class Vector {
22 : public:
23 28143042 : constexpr Vector() : start_(nullptr), length_(0) {}
24 :
25 210179334 : Vector(T* data, size_t length) : start_(data), length_(length) {
26 : DCHECK(length == 0 || data != nullptr);
27 104 : }
28 :
29 : template <int N>
30 2050 : explicit constexpr Vector(T (&arr)[N]) : start_(arr), length_(N) {}
31 :
32 : static Vector<T> New(int length) {
33 9636544 : return Vector<T>(NewArray<T>(length), length);
34 : }
35 :
36 : // Returns a vector using the same backing storage as this one,
37 : // spanning from and including 'from', to but not including 'to'.
38 : Vector<T> SubVector(size_t from, size_t to) const {
39 : DCHECK_LE(from, to);
40 : DCHECK_LE(to, length_);
41 7860610 : return Vector<T>(start() + from, to - from);
42 : }
43 :
44 : // Returns the length of the vector.
45 818879719 : int length() const {
46 : DCHECK(length_ <= static_cast<size_t>(std::numeric_limits<int>::max()));
47 3330505280 : return static_cast<int>(length_);
48 : }
49 :
50 : // Returns the length of the vector as a size_t.
51 : constexpr size_t size() const { return length_; }
52 :
53 : // Returns whether or not the vector is empty.
54 : constexpr bool empty() const { return length_ == 0; }
55 :
56 : // Returns the pointer to the start of the data in the vector.
57 75925 : constexpr T* start() const { return start_; }
58 :
59 : // Access individual vector elements - checks bounds in debug mode.
60 819666316 : T& operator[](size_t index) const {
61 : DCHECK_LT(index, length_);
62 16655223486 : return start_[index];
63 : }
64 :
65 : const T& at(size_t index) const { return operator[](index); }
66 :
67 : T& first() { return start_[0]; }
68 :
69 : T& last() {
70 : DCHECK_LT(0, length_);
71 : return start_[length_ - 1];
72 : }
73 :
74 : typedef T* iterator;
75 : constexpr iterator begin() const { return start_; }
76 87948432 : constexpr iterator end() const { return start_ + length_; }
77 :
78 : // Returns a clone of this vector with a new backing store.
79 : Vector<T> Clone() const {
80 : T* result = NewArray<T>(length_);
81 : for (size_t i = 0; i < length_; i++) result[i] = start_[i];
82 : return Vector<T>(result, length_);
83 : }
84 :
85 : template <typename CompareFunction>
86 : void Sort(CompareFunction cmp, size_t s, size_t l) {
87 55 : std::sort(start() + s, start() + s + l, RawComparer<CompareFunction>(cmp));
88 : }
89 :
90 : template <typename CompareFunction>
91 : void Sort(CompareFunction cmp) {
92 : std::sort(start(), start() + length(), RawComparer<CompareFunction>(cmp));
93 : }
94 :
95 : void Sort() {
96 40 : std::sort(start(), start() + length());
97 : }
98 :
99 : template <typename CompareFunction>
100 : void StableSort(CompareFunction cmp, size_t s, size_t l) {
101 8627 : std::stable_sort(start() + s, start() + s + l,
102 : RawComparer<CompareFunction>(cmp));
103 : }
104 :
105 : template <typename CompareFunction>
106 : void StableSort(CompareFunction cmp) {
107 : std::stable_sort(start(), start() + length(),
108 : RawComparer<CompareFunction>(cmp));
109 : }
110 :
111 : void StableSort() { std::stable_sort(start(), start() + length()); }
112 :
113 : void Truncate(size_t length) {
114 : DCHECK(length <= length_);
115 369232 : length_ = length;
116 : }
117 :
118 : // Releases the array underlying this vector. Once disposed the
119 : // vector is empty.
120 : void Dispose() {
121 29826679 : DeleteArray(start_);
122 29825165 : start_ = nullptr;
123 29825165 : length_ = 0;
124 : }
125 :
126 : Vector<T> operator+(size_t offset) {
127 : DCHECK_LE(offset, length_);
128 8205876 : return Vector<T>(start_ + offset, length_ - offset);
129 : }
130 :
131 : Vector<T> operator+=(size_t offset) {
132 : DCHECK_LE(offset, length_);
133 1063019 : start_ += offset;
134 4 : length_ -= offset;
135 : return *this;
136 : }
137 :
138 : // Implicit conversion from Vector<T> to Vector<const T>.
139 176 : inline operator Vector<const T>() const {
140 176 : return Vector<const T>::cast(*this);
141 : }
142 :
143 : template <typename S>
144 : static constexpr Vector<T> cast(Vector<S> input) {
145 : return Vector<T>(reinterpret_cast<T*>(input.start()),
146 25852428 : input.length() * sizeof(S) / sizeof(T));
147 : }
148 :
149 : bool operator==(const Vector<const T> other) const {
150 4438 : if (length_ != other.length_) return false;
151 4270 : if (start_ == other.start_) return true;
152 87442 : for (size_t i = 0; i < length_; ++i) {
153 41604 : if (start_[i] != other.start_[i]) {
154 : return false;
155 : }
156 : }
157 : return true;
158 : }
159 :
160 : private:
161 : T* start_;
162 : size_t length_;
163 :
164 : template <typename CookedComparer>
165 : class RawComparer {
166 : public:
167 : explicit RawComparer(CookedComparer cmp) : cmp_(cmp) {}
168 : bool operator()(const T& a, const T& b) {
169 213798 : return cmp_(&a, &b) < 0;
170 : }
171 :
172 : private:
173 : CookedComparer cmp_;
174 : };
175 : };
176 :
177 :
178 : template <typename T>
179 : class ScopedVector : public Vector<T> {
180 : public:
181 1298486 : explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { }
182 320 : ~ScopedVector() {
183 75925 : DeleteArray(this->start());
184 254575 : }
185 :
186 : private:
187 : DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector);
188 : };
189 :
190 : template <typename T>
191 45889522 : class OwnedVector {
192 : public:
193 32549011 : MOVE_ONLY_WITH_DEFAULT_CONSTRUCTORS(OwnedVector);
194 : OwnedVector(std::unique_ptr<T[]> data, size_t length)
195 3748007 : : data_(std::move(data)), length_(length) {
196 : DCHECK_IMPLIES(length_ > 0, data_ != nullptr);
197 : }
198 : // Implicit conversion from {OwnedVector<U>} to {OwnedVector<T>}, instantiable
199 : // if {std::unique_ptr<U>} can be converted to {std::unique_ptr<T>}.
200 : // Can be used to convert {OwnedVector<T>} to {OwnedVector<const T>}.
201 : template <typename U,
202 : typename = typename std::enable_if<std::is_convertible<
203 : std::unique_ptr<U>, std::unique_ptr<T>>::value>::type>
204 : OwnedVector(OwnedVector<U>&& other)
205 3776139 : : data_(std::move(other.data_)), length_(other.length_) {
206 : STATIC_ASSERT(sizeof(U) == sizeof(T));
207 1583015 : other.length_ = 0;
208 : }
209 :
210 : // Returns the length of the vector as a size_t.
211 : constexpr size_t size() const { return length_; }
212 :
213 : // Returns whether or not the vector is empty.
214 : constexpr bool empty() const { return length_ == 0; }
215 :
216 : // Returns the pointer to the start of the data in the vector.
217 : T* start() const {
218 : DCHECK_IMPLIES(length_ > 0, data_ != nullptr);
219 : return data_.get();
220 : }
221 :
222 : // Returns a {Vector<T>} view of the data in this vector.
223 : Vector<T> as_vector() const { return Vector<T>(start(), size()); }
224 :
225 : // Releases the backing data from this vector and transfers ownership to the
226 : // caller. This vector will be empty afterwards.
227 : std::unique_ptr<T[]> ReleaseData() {
228 1435512 : length_ = 0;
229 : return std::move(data_);
230 : }
231 :
232 : // Allocates a new vector of the specified size via the default allocator.
233 : static OwnedVector<T> New(size_t size) {
234 6211827 : if (size == 0) return {};
235 6297861 : return OwnedVector<T>(std::unique_ptr<T[]>(new T[size]), size);
236 : }
237 :
238 : // Allocates a new vector containing the specified collection of values.
239 : // {Iterator} is the common type of {std::begin} and {std::end} called on a
240 : // {const U&}. This function is only instantiable if that type exists.
241 : template <typename U, typename Iterator = typename std::common_type<
242 : decltype(std::begin(std::declval<const U&>())),
243 : decltype(std::end(std::declval<const U&>()))>::type>
244 1837323 : static OwnedVector<T> Of(const U& collection) {
245 : Iterator begin = std::begin(collection);
246 : Iterator end = std::end(collection);
247 1837323 : OwnedVector<T> vec = New(std::distance(begin, end));
248 : std::copy(begin, end, vec.start());
249 1839907 : return vec;
250 : }
251 :
252 : bool operator==(std::nullptr_t) const { return data_ == nullptr; }
253 : bool operator!=(std::nullptr_t) const { return data_ != nullptr; }
254 :
255 : private:
256 : template <typename U>
257 : friend class OwnedVector;
258 :
259 : std::unique_ptr<T[]> data_;
260 : size_t length_ = 0;
261 : };
262 :
263 : inline int StrLength(const char* string) {
264 232277634 : size_t length = strlen(string);
265 : DCHECK(length == static_cast<size_t>(static_cast<int>(length)));
266 232277634 : return static_cast<int>(length);
267 : }
268 :
269 : template <size_t N>
270 5938 : constexpr Vector<const uint8_t> StaticCharVector(const char (&array)[N]) {
271 5938 : return Vector<const uint8_t>::cast(Vector<const char>(array, N - 1));
272 : }
273 :
274 : inline Vector<const char> CStrVector(const char* data) {
275 19664136 : return Vector<const char>(data, StrLength(data));
276 : }
277 :
278 : inline Vector<const uint8_t> OneByteVector(const char* data, int length) {
279 36901777 : return Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), length);
280 : }
281 :
282 : inline Vector<const uint8_t> OneByteVector(const char* data) {
283 : return OneByteVector(data, StrLength(data));
284 : }
285 :
286 : inline Vector<char> MutableCStrVector(char* data) {
287 : return Vector<char>(data, StrLength(data));
288 : }
289 :
290 : inline Vector<char> MutableCStrVector(char* data, int max) {
291 : int length = StrLength(data);
292 : return Vector<char>(data, (length < max) ? length : max);
293 : }
294 :
295 : template <typename T, int N>
296 : inline constexpr Vector<T> ArrayVector(T (&arr)[N]) {
297 : return Vector<T>(arr);
298 : }
299 :
300 : // Construct a Vector from a start pointer and a size.
301 : template <typename T>
302 : inline constexpr Vector<T> VectorOf(T* start, size_t size) {
303 : return Vector<T>(start, size);
304 : }
305 :
306 : // Construct a Vector from anything providing a {data()} and {size()} accessor.
307 : template <typename Container>
308 : inline constexpr auto VectorOf(Container&& c)
309 : -> decltype(VectorOf(c.data(), c.size())) {
310 : return VectorOf(c.data(), c.size());
311 : }
312 :
313 : template <typename T, int kSize>
314 : class EmbeddedVector : public Vector<T> {
315 : public:
316 3193165775 : EmbeddedVector() : Vector<T>(buffer_, kSize) {}
317 :
318 509823020 : explicit EmbeddedVector(T initial_value) : Vector<T>(buffer_, kSize) {
319 509829886 : for (int i = 0; i < kSize; ++i) {
320 250993216 : buffer_[i] = initial_value;
321 : }
322 : }
323 :
324 : // When copying, make underlying Vector to reference our buffer.
325 : EmbeddedVector(const EmbeddedVector& rhs) V8_NOEXCEPT : Vector<T>(rhs) {
326 : MemCopy(buffer_, rhs.buffer_, sizeof(T) * kSize);
327 : this->set_start(buffer_);
328 : }
329 :
330 : EmbeddedVector& operator=(const EmbeddedVector& rhs) V8_NOEXCEPT {
331 : if (this == &rhs) return *this;
332 : Vector<T>::operator=(rhs);
333 : MemCopy(buffer_, rhs.buffer_, sizeof(T) * kSize);
334 : this->set_start(buffer_);
335 : return *this;
336 : }
337 :
338 : private:
339 : T buffer_[kSize];
340 : };
341 :
342 : } // namespace internal
343 : } // namespace v8
344 :
345 : #endif // V8_VECTOR_H_
|
