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
16namespace v8 {
17namespace internal {
18
19
20template <typename T>
21class Vector {
22 public:
23 constexpr Vector() : start_(nullptr), length_(0) {}
24
25 Vector(T* data, size_t length) : start_(data), length_(length) {
26 DCHECK(length == 0 || data != nullptr);
27 }
28
29 template <int N>
30 explicit constexpr Vector(T (&arr)[N]) : start_(arr), length_(N) {}
31
32 static Vector<T> New(int length) {
33 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 return Vector<T>(start() + from, to - from);
42 }
43
44 // Returns the length of the vector.
45 int length() const {
46 DCHECK(length_ <= static_cast<size_t>(std::numeric_limits<int>::max()));
47 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 constexpr T* start() const { return start_; }
58
59 // Access individual vector elements - checks bounds in debug mode.
60 T& operator[](size_t index) const {
61 DCHECK_LT(index, length_);
62 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 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 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 std::sort(start(), start() + length());
97 }
98
99 template <typename CompareFunction>
100 void StableSort(CompareFunction cmp, size_t s, size_t l) {
101 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 length_ = length;
116 }
117
118 // Releases the array underlying this vector. Once disposed the
119 // vector is empty.
120 void Dispose() {
121 DeleteArray(start_);
122 start_ = nullptr;
123 length_ = 0;
124 }
125
126 Vector<T> operator+(size_t offset) {
127 DCHECK_LE(offset, length_);
128 return Vector<T>(start_ + offset, length_ - offset);
129 }
130
131 Vector<T> operator+=(size_t offset) {
132 DCHECK_LE(offset, length_);
133 start_ += offset;
134 length_ -= offset;
135 return *this;
136 }
137
138 // Implicit conversion from Vector<T> to Vector<const T>.
139 inline operator Vector<const T>() const {
140 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 input.length() * sizeof(S) / sizeof(T));
147 }
148
149 bool operator==(const Vector<const T> other) const {
150 if (length_ != other.length_) return false;
151 if (start_ == other.start_) return true;
152 for (size_t i = 0; i < length_; ++i) {
153 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 return cmp_(&a, &b) < 0;
170 }
171
172 private:
173 CookedComparer cmp_;
174 };
175};
176
177
178template <typename T>
179class ScopedVector : public Vector<T> {
180 public:
181 explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { }
182 ~ScopedVector() {
183 DeleteArray(this->start());
184 }
185
186 private:
187 DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector);
188};
189
190template <typename T>
191class OwnedVector {
192 public:
193 MOVE_ONLY_WITH_DEFAULT_CONSTRUCTORS(OwnedVector);
194 OwnedVector(std::unique_ptr<T[]> data, size_t length)
195 : 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 : data_(std::move(other.data_)), length_(other.length_) {
206 STATIC_ASSERT(sizeof(U) == sizeof(T));
207 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 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 if (size == 0) return {};
235 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 static OwnedVector<T> Of(const U& collection) {
245 Iterator begin = std::begin(collection);
246 Iterator end = std::end(collection);
247 OwnedVector<T> vec = New(std::distance(begin, end));
248 std::copy(begin, end, vec.start());
249 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
263inline int StrLength(const char* string) {
264 size_t length = strlen(string);
265 DCHECK(length == static_cast<size_t>(static_cast<int>(length)));
266 return static_cast<int>(length);
267}
268
269template <size_t N>
270constexpr Vector<const uint8_t> StaticCharVector(const char (&array)[N]) {
271 return Vector<const uint8_t>::cast(Vector<const char>(array, N - 1));
272}
273
274inline Vector<const char> CStrVector(const char* data) {
275 return Vector<const char>(data, StrLength(data));
276}
277
278inline Vector<const uint8_t> OneByteVector(const char* data, int length) {
279 return Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), length);
280}
281
282inline Vector<const uint8_t> OneByteVector(const char* data) {
283 return OneByteVector(data, StrLength(data));
284}
285
286inline Vector<char> MutableCStrVector(char* data) {
287 return Vector<char>(data, StrLength(data));
288}
289
290inline Vector<char> MutableCStrVector(char* data, int max) {
291 int length = StrLength(data);
292 return Vector<char>(data, (length < max) ? length : max);
293}
294
295template <typename T, int N>
296inline 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.
301template <typename T>
302inline 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.
307template <typename Container>
308inline constexpr auto VectorOf(Container&& c)
309 -> decltype(VectorOf(c.data(), c.size())) {
310 return VectorOf(c.data(), c.size());
311}
312
313template <typename T, int kSize>
314class EmbeddedVector : public Vector<T> {
315 public:
316 EmbeddedVector() : Vector<T>(buffer_, kSize) {}
317
318 explicit EmbeddedVector(T initial_value) : Vector<T>(buffer_, kSize) {
319 for (int i = 0; i < kSize; ++i) {
320 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_
346