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 Vector() : start_(NULL), length_(0) {} 23 Vector(T* data, int length) : start_(data), length_(length) { 24 DCHECK(length == 0 || (length > 0 && data != NULL)); 25 } 26 27 template <int N> 28 explicit Vector(T (&arr)[N]) : start_(arr), length_(N) {} 29 30 static Vector<T> New(int length) { 31 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 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 return Vector<T>(start() + from, to - from); 41 } 42 43 // Returns the length of the vector. 44 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 T* start() const { return start_; } 51 52 // Access individual vector elements - checks bounds in debug mode. 53 T& operator[](int index) const { 54 DCHECK_LE(0, index); 55 DCHECK_LT(index, length_); 56 return start_[index]; 57 } 58 59 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 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 void Sort(CompareFunction cmp, size_t s, size_t l) { 78 std::sort(start() + s, start() + s + l, RawComparer<CompareFunction>(cmp)); 79 } 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 void StableSort(CompareFunction cmp, size_t s, size_t l) { 92 std::stable_sort(start() + s, start() + s + l, 93 RawComparer<CompareFunction>(cmp)); 94 } 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 length_ = length; 107 } 108 109 // Releases the array underlying this vector. Once disposed the 110 // vector is empty. 111 void Dispose() { 112 DeleteArray(start_); 113 start_ = NULL; 114 length_ = 0; 115 } 116 117 inline Vector<T> operator+(int offset) { 118 DCHECK(offset < length_); 119 return Vector<T>(start_ + offset, length_ - offset); 120 } 121 122 // Implicit conversion from Vector<T> to Vector<const T>. 123 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 input.length() * sizeof(S) / sizeof(T)); 132 } 133 134 bool operator==(const Vector<T>& other) const { 135 if (length_ != other.length_) return false; 136 if (start_ == other.start_) return true; 137 for (int i = 0; i < length_; ++i) { 138 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 explicit RawComparer(CookedComparer cmp) : cmp_(cmp) {} 156 bool operator()(const T& a, const T& b) { 157 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 explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { } 170 ~ScopedVector() { 171 DeleteArray(this->start()); 172 } 173 174 private: 175 DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector); 176 }; 177 178 179 inline int StrLength(const char* string) { 180 size_t length = strlen(string); 181 DCHECK(length == static_cast<size_t>(static_cast<int>(length))); 182 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 inline Vector<const char> CStrVector(const char* data) { 191 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 inline Vector<T> ArrayVector(T (&arr)[N]) { 213 return Vector<T>(arr); 214 } 215 216 } // namespace internal 217 } // namespace v8 218 219 #endif // V8_VECTOR_H_ 220