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 constexpr Vector() : start_(nullptr), length_(0) {} 24 25 Vector(T* data, size_t length) : start_(data), length_(length) { 26 DCHECK(length == 0 || data != nullptr); 27 } 28 29 template <int N> 30 explicit constexpr Vector(T (&arr)[N]) : start_(arr), length_(N) {} 31 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'. 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. 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. 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 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 65 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 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 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> 91 void Sort(CompareFunction cmp) { 92 std::sort(start(), start() + length(), RawComparer<CompareFunction>(cmp)); 93 } 94 95 void Sort() { 96 std::sort(start(), start() + length()); 97 } 98 99 template <typename CompareFunction> 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> 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 length_ = length; 116 } 117 118 // Releases the array underlying this vector. Once disposed the 119 // vector is empty. 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. 142 static Vector<T> empty() { return Vector<T>(nullptr, 0); } 143 144 template <typename S> 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: 168 explicit RawComparer(CookedComparer cmp) : cmp_(cmp) {} 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: 182 explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { } 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); 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> 205 OwnedVector(OwnedVector<U>&& other) 206 : data_(other.ReleaseData()), length_(other.size()) {} 207 208 // Returns the length of the vector as a size_t. 209 constexpr size_t size() const { return length_; } 210 211 // Returns whether or not the vector 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. 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. 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. 225 std::unique_ptr<T[]> ReleaseData() { return std::move(data_); } 226 227 // Allocates a new vector of the specified size via the default allocator. 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> 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 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 263 inline Vector<const char> CStrVector(const char* data) { 264 return Vector<const char>(data, StrLength(data)); 265 } 266 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 271 inline Vector<const uint8_t> OneByteVector(const char* data) { 272 return OneByteVector(data, StrLength(data)); 273 } 274 275 inline Vector<char> MutableCStrVector(char* data) { 276 return Vector<char>(data, StrLength(data)); 277 } 278 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> 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