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 <string.h>
9 : #include <algorithm>
10 :
11 : #include "src/allocation.h"
12 : #include "src/checks.h"
13 : #include "src/globals.h"
14 :
15 : namespace v8 {
16 : namespace internal {
17 :
18 :
19 : template <typename T>
20 : class Vector {
21 : public:
22 22941505 : constexpr Vector() : start_(nullptr), length_(0) {}
23 :
24 151652318 : Vector(T* data, size_t length) : start_(data), length_(length) {
25 : DCHECK(length == 0 || data != nullptr);
26 7615 : }
27 :
28 : template <int N>
29 36 : explicit constexpr Vector(T (&arr)[N]) : start_(arr), length_(N) {}
30 :
31 : static Vector<T> New(int length) {
32 8462158 : return Vector<T>(NewArray<T>(length), length);
33 : }
34 :
35 : // Returns a vector using the same backing storage as this one,
36 : // spanning from and including 'from', to but not including 'to'.
37 248598 : Vector<T> SubVector(size_t from, size_t to) const {
38 : DCHECK_LE(from, to);
39 : DCHECK_LE(to, length_);
40 3674158 : return Vector<T>(start() + from, to - from);
41 : }
42 :
43 : // Returns the length of the vector.
44 1172193347 : int length() const {
45 : DCHECK(length_ <= static_cast<size_t>(std::numeric_limits<int>::max()));
46 12711889325 : return static_cast<int>(length_);
47 : }
48 :
49 : // Returns the length of the vector as a size_t.
50 : constexpr size_t size() const { return length_; }
51 :
52 : // Returns whether or not the vector is empty.
53 : constexpr bool is_empty() const { return length_ == 0; }
54 :
55 : // Returns the pointer to the start of the data in the vector.
56 6170 : constexpr T* start() const { return start_; }
57 :
58 : // Access individual vector elements - checks bounds in debug mode.
59 1170767777 : T& operator[](size_t index) const {
60 : DCHECK_LT(index, length_);
61 16800349596 : return start_[index];
62 : }
63 :
64 1249779 : const T& at(size_t index) const { return operator[](index); }
65 :
66 : T& first() { return start_[0]; }
67 :
68 : T& last() {
69 : DCHECK_LT(0, length_);
70 : return start_[length_ - 1];
71 : }
72 :
73 : typedef T* iterator;
74 : constexpr iterator begin() const { return start_; }
75 2372176 : constexpr iterator end() const { return start_ + length_; }
76 :
77 : // Returns a clone of this vector with a new backing store.
78 : Vector<T> Clone() const {
79 : T* result = NewArray<T>(length_);
80 : for (size_t i = 0; i < length_; i++) result[i] = start_[i];
81 : return Vector<T>(result, length_);
82 : }
83 :
84 : template <typename CompareFunction>
85 132 : void Sort(CompareFunction cmp, size_t s, size_t l) {
86 66 : std::sort(start() + s, start() + s + l, RawComparer<CompareFunction>(cmp));
87 66 : }
88 :
89 : template <typename CompareFunction>
90 : void Sort(CompareFunction cmp) {
91 : std::sort(start(), start() + length(), RawComparer<CompareFunction>(cmp));
92 : }
93 :
94 : void Sort() {
95 48 : std::sort(start(), start() + length());
96 : }
97 :
98 : template <typename CompareFunction>
99 19390 : void StableSort(CompareFunction cmp, size_t s, size_t l) {
100 19390 : std::stable_sort(start() + s, start() + s + l,
101 19390 : RawComparer<CompareFunction>(cmp));
102 9695 : }
103 :
104 : template <typename CompareFunction>
105 : void StableSort(CompareFunction cmp) {
106 : std::stable_sort(start(), start() + length(),
107 : RawComparer<CompareFunction>(cmp));
108 : }
109 :
110 : void StableSort() { std::stable_sort(start(), start() + length()); }
111 :
112 : void Truncate(size_t length) {
113 : DCHECK(length <= length_);
114 18 : length_ = length;
115 : }
116 :
117 : // Releases the array underlying this vector. Once disposed the
118 : // vector is empty.
119 : void Dispose() {
120 27714454 : DeleteArray(start_);
121 27711595 : start_ = nullptr;
122 27711595 : length_ = 0;
123 : }
124 :
125 : inline Vector<T> operator+(size_t offset) {
126 : DCHECK_LT(offset, length_);
127 4100 : return Vector<T>(start_ + offset, length_ - offset);
128 : }
129 :
130 : // Implicit conversion from Vector<T> to Vector<const T>.
131 : inline operator Vector<const T>() { return Vector<const T>::cast(*this); }
132 :
133 : // Factory method for creating empty vectors.
134 : static Vector<T> empty() { return Vector<T>(nullptr, 0); }
135 :
136 : template <typename S>
137 : static constexpr Vector<T> cast(Vector<S> input) {
138 : return Vector<T>(reinterpret_cast<T*>(input.start()),
139 9545225 : input.length() * sizeof(S) / sizeof(T));
140 : }
141 :
142 : bool operator==(const Vector<T>& other) const {
143 3292 : if (length_ != other.length_) return false;
144 3121 : if (start_ == other.start_) return true;
145 31239 : for (size_t i = 0; i < length_; ++i) {
146 31260 : if (start_[i] != other.start_[i]) {
147 : return false;
148 : }
149 : }
150 : return true;
151 : }
152 :
153 : protected:
154 : void set_start(T* start) { start_ = start; }
155 :
156 : private:
157 : T* start_;
158 : size_t length_;
159 :
160 : template <typename CookedComparer>
161 : class RawComparer {
162 : public:
163 9761 : explicit RawComparer(CookedComparer cmp) : cmp_(cmp) {}
164 : bool operator()(const T& a, const T& b) {
165 156171 : return cmp_(&a, &b) < 0;
166 : }
167 :
168 : private:
169 : CookedComparer cmp_;
170 : };
171 : };
172 :
173 :
174 : template <typename T>
175 : class ScopedVector : public Vector<T> {
176 : public:
177 591058 : explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { }
178 2707 : ~ScopedVector() {
179 2742 : DeleteArray(this->start());
180 2707 : }
181 :
182 : private:
183 : DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector);
184 : };
185 :
186 :
187 50 : inline int StrLength(const char* string) {
188 176861772 : size_t length = strlen(string);
189 : DCHECK(length == static_cast<size_t>(static_cast<int>(length)));
190 176861772 : return static_cast<int>(length);
191 : }
192 :
193 :
194 : #define STATIC_CHAR_VECTOR(x) \
195 : v8::internal::Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(x), \
196 : arraysize(x) - 1)
197 :
198 1845 : inline Vector<const char> CStrVector(const char* data) {
199 7572097 : return Vector<const char>(data, StrLength(data));
200 : }
201 :
202 : inline Vector<const uint8_t> OneByteVector(const char* data, int length) {
203 39493526 : return Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), length);
204 : }
205 :
206 : inline Vector<const uint8_t> OneByteVector(const char* data) {
207 : return OneByteVector(data, StrLength(data));
208 : }
209 :
210 : inline Vector<char> MutableCStrVector(char* data) {
211 : return Vector<char>(data, StrLength(data));
212 : }
213 :
214 : inline Vector<char> MutableCStrVector(char* data, int max) {
215 : int length = StrLength(data);
216 : return Vector<char>(data, (length < max) ? length : max);
217 : }
218 :
219 : template <typename T, int N>
220 1581447 : inline constexpr Vector<T> ArrayVector(T (&arr)[N]) {
221 1581447 : return Vector<T>(arr);
222 : }
223 :
224 : } // namespace internal
225 : } // namespace v8
226 :
227 : #endif // V8_VECTOR_H_
|
