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 34793829 : Vector() : start_(NULL), length_(0) {}
23 152253800 : Vector(T* data, int length) : start_(data), length_(length) {
24 : DCHECK(length == 0 || (length > 0 && data != NULL));
25 8280 : }
26 :
27 : template <int N>
28 0 : explicit Vector(T (&arr)[N]) : start_(arr), length_(N) {}
29 :
30 : static Vector<T> New(int length) {
31 12074220 : return Vector<T>(NewArray<T>(length), length);
32 : }
33 :
34 : // Returns a vector using the same backing storage as this one,
35 : // spanning from and including 'from', to but not including 'to'.
36 123106 : Vector<T> SubVector(int from, int to) const {
37 : DCHECK(0 <= from);
38 : SLOW_DCHECK(from <= to);
39 : SLOW_DCHECK(static_cast<unsigned>(to) <= static_cast<unsigned>(length_));
40 2802229 : return Vector<T>(start() + from, to - from);
41 : }
42 :
43 : // Returns the length of the vector.
44 1637311939 : int length() const { return length_; }
45 :
46 : // Returns whether or not the vector is empty.
47 : bool is_empty() const { return length_ == 0; }
48 :
49 : // Returns the pointer to the start of the data in the vector.
50 10885 : T* start() const { return start_; }
51 :
52 : // Access individual vector elements - checks bounds in debug mode.
53 1634619426 : T& operator[](int index) const {
54 : DCHECK_LE(0, index);
55 : DCHECK_LT(index, length_);
56 6999898498 : return start_[index];
57 : }
58 :
59 100165945 : const T& at(int index) const { return operator[](index); }
60 :
61 : T& first() { return start_[0]; }
62 :
63 : T& last() { return start_[length_ - 1]; }
64 :
65 : typedef T* iterator;
66 : inline iterator begin() const { return &start_[0]; }
67 1954683 : inline iterator end() const { return &start_[length_]; }
68 :
69 : // Returns a clone of this vector with a new backing store.
70 : Vector<T> Clone() const {
71 : T* result = NewArray<T>(length_);
72 : for (int i = 0; i < length_; i++) result[i] = start_[i];
73 : return Vector<T>(result, length_);
74 : }
75 :
76 : template <typename CompareFunction>
77 1136610 : void Sort(CompareFunction cmp, size_t s, size_t l) {
78 568305 : std::sort(start() + s, start() + s + l, RawComparer<CompareFunction>(cmp));
79 568305 : }
80 :
81 : template <typename CompareFunction>
82 : void Sort(CompareFunction cmp) {
83 : std::sort(start(), start() + length(), RawComparer<CompareFunction>(cmp));
84 : }
85 :
86 : void Sort() {
87 : std::sort(start(), start() + length());
88 : }
89 :
90 : template <typename CompareFunction>
91 22814 : void StableSort(CompareFunction cmp, size_t s, size_t l) {
92 22814 : std::stable_sort(start() + s, start() + s + l,
93 22814 : RawComparer<CompareFunction>(cmp));
94 11407 : }
95 :
96 : template <typename CompareFunction>
97 : void StableSort(CompareFunction cmp) {
98 : std::stable_sort(start(), start() + length(),
99 : RawComparer<CompareFunction>(cmp));
100 : }
101 :
102 : void StableSort() { std::stable_sort(start(), start() + length()); }
103 :
104 : void Truncate(int length) {
105 : DCHECK(length <= length_);
106 1369 : length_ = length;
107 : }
108 :
109 : // Releases the array underlying this vector. Once disposed the
110 : // vector is empty.
111 : void Dispose() {
112 36078520 : DeleteArray(start_);
113 36075995 : start_ = NULL;
114 36075995 : length_ = 0;
115 : }
116 :
117 : inline Vector<T> operator+(int offset) {
118 : DCHECK(offset < length_);
119 0 : return Vector<T>(start_ + offset, length_ - offset);
120 : }
121 :
122 : // Implicit conversion from Vector<T> to Vector<const T>.
123 1369 : inline operator Vector<const T>() { return Vector<const T>::cast(*this); }
124 :
125 : // Factory method for creating empty vectors.
126 : static Vector<T> empty() { return Vector<T>(NULL, 0); }
127 :
128 : template<typename S>
129 : static Vector<T> cast(Vector<S> input) {
130 : return Vector<T>(reinterpret_cast<T*>(input.start()),
131 137386 : input.length() * sizeof(S) / sizeof(T));
132 : }
133 :
134 : bool operator==(const Vector<T>& other) const {
135 2758 : if (length_ != other.length_) return false;
136 2538 : if (start_ == other.start_) return true;
137 23971 : for (int i = 0; i < length_; ++i) {
138 23998 : if (start_[i] != other.start_[i]) {
139 : return false;
140 : }
141 : }
142 : return true;
143 : }
144 :
145 : protected:
146 : void set_start(T* start) { start_ = start; }
147 :
148 : private:
149 : T* start_;
150 : int length_;
151 :
152 : template <typename CookedComparer>
153 : class RawComparer {
154 : public:
155 579712 : explicit RawComparer(CookedComparer cmp) : cmp_(cmp) {}
156 : bool operator()(const T& a, const T& b) {
157 48208642 : return cmp_(&a, &b) < 0;
158 : }
159 :
160 : private:
161 : CookedComparer cmp_;
162 : };
163 : };
164 :
165 :
166 : template <typename T>
167 : class ScopedVector : public Vector<T> {
168 : public:
169 492572 : explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { }
170 5852 : ~ScopedVector() {
171 5876 : DeleteArray(this->start());
172 5852 : }
173 :
174 : private:
175 : DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector);
176 : };
177 :
178 :
179 75 : inline int StrLength(const char* string) {
180 203343628 : size_t length = strlen(string);
181 : DCHECK(length == static_cast<size_t>(static_cast<int>(length)));
182 203343628 : return static_cast<int>(length);
183 : }
184 :
185 :
186 : #define STATIC_CHAR_VECTOR(x) \
187 : v8::internal::Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(x), \
188 : arraysize(x) - 1)
189 :
190 7660 : inline Vector<const char> CStrVector(const char* data) {
191 7660 : return Vector<const char>(data, StrLength(data));
192 : }
193 :
194 : inline Vector<const uint8_t> OneByteVector(const char* data, int length) {
195 : return Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), length);
196 : }
197 :
198 : inline Vector<const uint8_t> OneByteVector(const char* data) {
199 : return OneByteVector(data, StrLength(data));
200 : }
201 :
202 : inline Vector<char> MutableCStrVector(char* data) {
203 : return Vector<char>(data, StrLength(data));
204 : }
205 :
206 : inline Vector<char> MutableCStrVector(char* data, int max) {
207 : int length = StrLength(data);
208 : return Vector<char>(data, (length < max) ? length : max);
209 : }
210 :
211 : template <typename T, int N>
212 817419 : inline Vector<T> ArrayVector(T (&arr)[N]) {
213 817419 : return Vector<T>(arr);
214 : }
215 :
216 : } // namespace internal
217 : } // namespace v8
218 :
219 : #endif // V8_VECTOR_H_
|