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 23883665 : constexpr Vector() : start_(nullptr), length_(0) {}
24 :
25 234083470 : Vector(T* data, size_t length) : start_(data), length_(length) {
26 : DCHECK(length == 0 || data != nullptr);
27 675 : }
28 :
29 : template <int N>
30 2070 : explicit constexpr Vector(T (&arr)[N]) : start_(arr), length_(N) {}
31 :
32 : static Vector<T> New(int length) {
33 9759525 : 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 282434 : Vector<T> SubVector(size_t from, size_t to) const {
39 : DCHECK_LE(from, to);
40 : DCHECK_LE(to, length_);
41 3625336 : return Vector<T>(start() + from, to - from);
42 : }
43 :
44 : // Returns the length of the vector.
45 1136904619 : int length() const {
46 : DCHECK(length_ <= static_cast<size_t>(std::numeric_limits<int>::max()));
47 12534141974 : 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 is_empty() const { return length_ == 0; }
55 :
56 : // Returns the pointer to the start of the data in the vector.
57 76430205 : constexpr T* start() const { return start_; }
58 :
59 : // Access individual vector elements - checks bounds in debug mode.
60 1059066971 : T& operator[](size_t index) const {
61 : DCHECK_LT(index, length_);
62 16017877399 : return start_[index];
63 : }
64 :
65 49361408 : 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 27183994 : 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 110 : void Sort(CompareFunction cmp, size_t s, size_t l) {
87 55 : std::sort(start() + s, start() + s + l, RawComparer<CompareFunction>(cmp));
88 55 : }
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 17254 : void StableSort(CompareFunction cmp, size_t s, size_t l) {
101 17254 : std::stable_sort(start() + s, start() + s + l,
102 17254 : RawComparer<CompareFunction>(cmp));
103 8627 : }
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 1229 : length_ = length;
116 : }
117 :
118 : // Releases the array underlying this vector. Once disposed the
119 : // vector is empty.
120 : void Dispose() {
121 29391503 : DeleteArray(start_);
122 29389768 : start_ = nullptr;
123 29389768 : length_ = 0;
124 : }
125 :
126 : Vector<T> operator+(size_t offset) {
127 : DCHECK_LE(offset, length_);
128 8257509 : return Vector<T>(start_ + offset, length_ - offset);
129 : }
130 :
131 : Vector<T> operator+=(size_t offset) {
132 : DCHECK_LE(offset, length_);
133 4 : start_ += offset;
134 4 : 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 : // Factory method for creating empty vectors.
144 : static Vector<T> empty() { return Vector<T>(nullptr, 0); }
145 :
146 : template <typename S>
147 : static constexpr Vector<T> cast(Vector<S> input) {
148 : return Vector<T>(reinterpret_cast<T*>(input.start()),
149 20884395 : input.length() * sizeof(S) / sizeof(T));
150 : }
151 :
152 : bool operator==(const Vector<const T> other) const {
153 4483 : if (length_ != other.length_) return false;
154 4315 : if (start_ == other.start_) return true;
155 41991 : for (size_t i = 0; i < length_; ++i) {
156 42009 : if (start_[i] != other.start_[i]) {
157 : return false;
158 : }
159 : }
160 : return true;
161 : }
162 :
163 : private:
164 : T* start_;
165 : size_t length_;
166 :
167 : template <typename CookedComparer>
168 : class RawComparer {
169 : public:
170 8682 : explicit RawComparer(CookedComparer cmp) : cmp_(cmp) {}
171 : bool operator()(const T& a, const T& b) {
172 150757 : return cmp_(&a, &b) < 0;
173 : }
174 :
175 : private:
176 : CookedComparer cmp_;
177 : };
178 : };
179 :
180 :
181 : template <typename T>
182 : class ScopedVector : public Vector<T> {
183 : public:
184 1814682 : explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { }
185 1483 : ~ScopedVector() {
186 1523 : DeleteArray(this->start());
187 1483 : }
188 :
189 : private:
190 : DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector);
191 : };
192 :
193 : template <typename T>
194 8534992 : class OwnedVector {
195 : public:
196 255046873 : MOVE_ONLY_WITH_DEFAULT_CONSTRUCTORS(OwnedVector);
197 : OwnedVector(std::unique_ptr<T[]> data, size_t length)
198 4419485 : : data_(std::move(data)), length_(length) {
199 : DCHECK_IMPLIES(length_ > 0, data_ != nullptr);
200 : }
201 : // Implicit conversion from {OwnedVector<U>} to {OwnedVector<T>}, instantiable
202 : // if {std::unique_ptr<U>} can be converted to {std::unique_ptr<T>}.
203 : // Can be used to convert {OwnedVector<T>} to {OwnedVector<const T>}.
204 : template <typename U,
205 : typename = typename std::enable_if<std::is_convertible<
206 : std::unique_ptr<U>, std::unique_ptr<T>>::value>::type>
207 1916418 : OwnedVector(OwnedVector<U>&& other)
208 82900411 : : data_(other.ReleaseData()), length_(other.size()) {}
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 is_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 45405656 : 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 vectors data can no longer be used afterwards.
227 : std::unique_ptr<T[]> ReleaseData() { return std::move(data_); }
228 :
229 : // Allocates a new vector of the specified size via the default allocator.
230 1755906 : static OwnedVector<T> New(size_t size) {
231 88586009 : if (size == 0) return {};
232 9131981 : return OwnedVector<T>(std::unique_ptr<T[]>(new T[size]), size);
233 : }
234 :
235 : // Allocates a new vector containing the specified collection of values.
236 : // {Iterator} is the common type of {std::begin} and {std::end} called on a
237 : // {const U&}. This function is only instantiable if that type exists.
238 : template <typename U, typename Iterator = typename std::common_type<
239 : decltype(std::begin(std::declval<const U&>())),
240 : decltype(std::end(std::declval<const U&>()))>::type>
241 2244120 : static OwnedVector<T> Of(const U& collection) {
242 : Iterator begin = std::begin(collection);
243 : Iterator end = std::end(collection);
244 2244120 : OwnedVector<T> vec = New(std::distance(begin, end));
245 : std::copy(begin, end, vec.start());
246 2244582 : return vec;
247 : }
248 :
249 : private:
250 : std::unique_ptr<T[]> data_;
251 : size_t length_ = 0;
252 : };
253 :
254 : inline int StrLength(const char* string) {
255 235686817 : size_t length = strlen(string);
256 : DCHECK(length == static_cast<size_t>(static_cast<int>(length)));
257 235686817 : return static_cast<int>(length);
258 : }
259 :
260 : template <size_t N>
261 7029 : constexpr Vector<const uint8_t> StaticCharVector(const char (&array)[N]) {
262 7029 : return Vector<const uint8_t>::cast(Vector<const char>(array, N - 1));
263 : }
264 :
265 : inline Vector<const char> CStrVector(const char* data) {
266 20797866 : return Vector<const char>(data, StrLength(data));
267 : }
268 :
269 : inline Vector<const uint8_t> OneByteVector(const char* data, int length) {
270 37815755 : return Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), length);
271 : }
272 :
273 : inline Vector<const uint8_t> OneByteVector(const char* data) {
274 : return OneByteVector(data, StrLength(data));
275 : }
276 :
277 : inline Vector<char> MutableCStrVector(char* data) {
278 : return Vector<char>(data, StrLength(data));
279 : }
280 :
281 : inline Vector<char> MutableCStrVector(char* data, int max) {
282 : int length = StrLength(data);
283 : return Vector<char>(data, (length < max) ? length : max);
284 : }
285 :
286 : template <typename T, int N>
287 3698 : inline constexpr Vector<T> ArrayVector(T (&arr)[N]) {
288 3698 : return Vector<T>(arr);
289 : }
290 :
291 : // Construct a Vector from a start pointer and a size.
292 : template <typename T>
293 : inline constexpr Vector<T> VectorOf(T* start, size_t size) {
294 : return Vector<T>(start, size);
295 : }
296 :
297 : // Construct a Vector from anything providing a {data()} and {size()} accessor.
298 : template <typename Container>
299 153106 : inline constexpr auto VectorOf(Container&& c)
300 : -> decltype(VectorOf(c.data(), c.size())) {
301 7723933 : return VectorOf(c.data(), c.size());
302 : }
303 :
304 : } // namespace internal
305 : } // namespace v8
306 :
307 : #endif // V8_VECTOR_H_
|
