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:
Vector()23 constexpr Vector() : start_(nullptr), length_(0) {}
24
Vector(T * data,size_t length)25 Vector(T* data, size_t length) : start_(data), length_(length) {
26 DCHECK(length == 0 || data != nullptr);
27 }
28
29 template <int N>
Vector(T (& arr)[N])30 explicit constexpr Vector(T (&arr)[N]) : start_(arr), length_(N) {}
31
New(int length)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'.
SubVector(size_t from,size_t 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.
length()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.
size()51 constexpr size_t size() const { return length_; }
52
53 // Returns whether or not the vector is empty.
is_empty()54 constexpr bool is_empty() const { return length_ == 0; }
55
56 // Returns the pointer to the start of the data in the vector.
start()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
at(size_t index)65 const T& at(size_t index) const { return operator[](index); }
66
first()67 T& first() { return start_[0]; }
68
last()69 T& last() {
70 DCHECK_LT(0, length_);
71 return start_[length_ - 1];
72 }
73
74 typedef T* iterator;
begin()75 constexpr iterator begin() const { return start_; }
end()76 constexpr iterator end() const { return start_ + length_; }
77
78 // Returns a clone of this vector with a new backing store.
Clone()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>
Sort(CompareFunction cmp,size_t s,size_t l)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>
Sort(CompareFunction cmp)91 void Sort(CompareFunction cmp) {
92 std::sort(start(), start() + length(), RawComparer<CompareFunction>(cmp));
93 }
94
Sort()95 void Sort() {
96 std::sort(start(), start() + length());
97 }
98
99 template <typename CompareFunction>
StableSort(CompareFunction cmp,size_t s,size_t l)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>
StableSort(CompareFunction cmp)106 void StableSort(CompareFunction cmp) {
107 std::stable_sort(start(), start() + length(),
108 RawComparer<CompareFunction>(cmp));
109 }
110
StableSort()111 void StableSort() { std::stable_sort(start(), start() + length()); }
112
Truncate(size_t length)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.
Dispose()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>() { return Vector<const T>::cast(*this); }
140
141 // Factory method for creating empty vectors.
empty()142 static Vector<T> empty() { return Vector<T>(nullptr, 0); }
143
144 template <typename S>
cast(Vector<S> input)145 static constexpr Vector<T> cast(Vector<S> input) {
146 return Vector<T>(reinterpret_cast<T*>(input.start()),
147 input.length() * sizeof(S) / sizeof(T));
148 }
149
150 bool operator==(const Vector<T>& other) const {
151 if (length_ != other.length_) return false;
152 if (start_ == other.start_) return true;
153 for (size_t i = 0; i < length_; ++i) {
154 if (start_[i] != other.start_[i]) {
155 return false;
156 }
157 }
158 return true;
159 }
160
161 private:
162 T* start_;
163 size_t length_;
164
165 template <typename CookedComparer>
166 class RawComparer {
167 public:
RawComparer(CookedComparer cmp)168 explicit RawComparer(CookedComparer cmp) : cmp_(cmp) {}
operator()169 bool operator()(const T& a, const T& b) {
170 return cmp_(&a, &b) < 0;
171 }
172
173 private:
174 CookedComparer cmp_;
175 };
176 };
177
178
179 template <typename T>
180 class ScopedVector : public Vector<T> {
181 public:
ScopedVector(int length)182 explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { }
~ScopedVector()183 ~ScopedVector() {
184 DeleteArray(this->start());
185 }
186
187 private:
188 DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector);
189 };
190
191 template <typename T>
192 class OwnedVector {
193 public:
194 MOVE_ONLY_WITH_DEFAULT_CONSTRUCTORS(OwnedVector);
OwnedVector(std::unique_ptr<T[]> data,size_t length)195 OwnedVector(std::unique_ptr<T[]> data, size_t length)
196 : data_(std::move(data)), length_(length) {
197 DCHECK_IMPLIES(length_ > 0, data_ != nullptr);
198 }
199 // Implicit conversion from {OwnedVector<U>} to {OwnedVector<T>}, instantiable
200 // if {std::unique_ptr<U>} can be converted to {std::unique_ptr<T>}.
201 // Can be used to convert {OwnedVector<T>} to {OwnedVector<const T>}.
202 template <typename U,
203 typename = typename std::enable_if<std::is_convertible<
204 std::unique_ptr<U>, std::unique_ptr<T>>::value>::type>
OwnedVector(OwnedVector<U> && other)205 OwnedVector(OwnedVector<U>&& other)
206 : data_(other.ReleaseData()), length_(other.size()) {}
207
208 // Returns the length of the vector as a size_t.
size()209 constexpr size_t size() const { return length_; }
210
211 // Returns whether or not the vector is empty.
is_empty()212 constexpr bool is_empty() const { return length_ == 0; }
213
214 // Returns the pointer to the start of the data in the vector.
start()215 T* start() const {
216 DCHECK_IMPLIES(length_ > 0, data_ != nullptr);
217 return data_.get();
218 }
219
220 // Returns a {Vector<T>} view of the data in this vector.
as_vector()221 Vector<T> as_vector() const { return Vector<T>(start(), size()); }
222
223 // Releases the backing data from this vector and transfers ownership to the
224 // caller. This vectors data can no longer be used afterwards.
ReleaseData()225 std::unique_ptr<T[]> ReleaseData() { return std::move(data_); }
226
227 // Allocates a new vector of the specified size via the default allocator.
New(size_t size)228 static OwnedVector<T> New(size_t size) {
229 if (size == 0) return {};
230 return OwnedVector<T>(std::unique_ptr<T[]>(new T[size]), size);
231 }
232
233 // Allocates a new vector containing the specified collection of values.
234 // {Iterator} is the common type of {std::begin} and {std::end} called on a
235 // {const U&}. This function is only instantiable if that type exists.
236 template <typename U, typename Iterator = typename std::common_type<
237 decltype(std::begin(std::declval<const U&>())),
238 decltype(std::end(std::declval<const U&>()))>::type>
Of(const U & collection)239 static OwnedVector<T> Of(const U& collection) {
240 Iterator begin = std::begin(collection);
241 Iterator end = std::end(collection);
242 OwnedVector<T> vec = New(std::distance(begin, end));
243 std::copy(begin, end, vec.start());
244 return vec;
245 }
246
247 private:
248 std::unique_ptr<T[]> data_;
249 size_t length_ = 0;
250 };
251
StrLength(const char * string)252 inline int StrLength(const char* string) {
253 size_t length = strlen(string);
254 DCHECK(length == static_cast<size_t>(static_cast<int>(length)));
255 return static_cast<int>(length);
256 }
257
258
259 #define STATIC_CHAR_VECTOR(x) \
260 v8::internal::Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(x), \
261 arraysize(x) - 1)
262
CStrVector(const char * data)263 inline Vector<const char> CStrVector(const char* data) {
264 return Vector<const char>(data, StrLength(data));
265 }
266
OneByteVector(const char * data,int length)267 inline Vector<const uint8_t> OneByteVector(const char* data, int length) {
268 return Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), length);
269 }
270
OneByteVector(const char * data)271 inline Vector<const uint8_t> OneByteVector(const char* data) {
272 return OneByteVector(data, StrLength(data));
273 }
274
MutableCStrVector(char * data)275 inline Vector<char> MutableCStrVector(char* data) {
276 return Vector<char>(data, StrLength(data));
277 }
278
MutableCStrVector(char * data,int max)279 inline Vector<char> MutableCStrVector(char* data, int max) {
280 int length = StrLength(data);
281 return Vector<char>(data, (length < max) ? length : max);
282 }
283
284 template <typename T, int N>
ArrayVector(T (& arr)[N])285 inline constexpr Vector<T> ArrayVector(T (&arr)[N]) {
286 return Vector<T>(arr);
287 }
288
289 } // namespace internal
290 } // namespace v8
291
292 #endif // V8_VECTOR_H_
293