1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2014 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#ifndef V8_VECTOR_H_ 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define V8_VECTOR_H_ 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include <string.h> 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include <algorithm> 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/allocation.h" 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/checks.h" 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/globals.h" 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace v8 { 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace internal { 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <typename T> 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass Vector { 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Vector() : start_(NULL), length_(0) {} 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Vector(T* data, int length) : start_(data), length_(length) { 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(length == 0 || (length > 0 && data != NULL)); 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static Vector<T> New(int length) { 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Vector<T>(NewArray<T>(length), length); 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns a vector using the same backing storage as this one, 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // spanning from and including 'from', to but not including 'to'. 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Vector<T> SubVector(int from, int to) { 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SLOW_DCHECK(to <= length_); 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SLOW_DCHECK(from < to); 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(0 <= from); 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Vector<T>(start() + from, to - from); 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns the length of the vector. 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int length() const { return length_; } 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns whether or not the vector is empty. 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool is_empty() const { return length_ == 0; } 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns the pointer to the start of the data in the vector. 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T* start() const { return start_; } 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Access individual vector elements - checks bounds in debug mode. 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T& operator[](int index) const { 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(0 <= index && index < length_); 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return start_[index]; 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const T& at(int index) const { return operator[](index); } 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T& first() { return start_[0]; } 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T& last() { return start_[length_ - 1]; } 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Returns a clone of this vector with a new backing store. 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Vector<T> Clone() const { 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T* result = NewArray<T>(length_); 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < length_; i++) result[i] = start_[i]; 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Vector<T>(result, length_); 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Sort(int (*cmp)(const T*, const T*)) { 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch std::sort(start(), start() + length(), RawComparer(cmp)); 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Sort() { 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch std::sort(start(), start() + length()); 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Truncate(int length) { 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(length <= length_); 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch length_ = length; 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Releases the array underlying this vector. Once disposed the 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // vector is empty. 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Dispose() { 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DeleteArray(start_); 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch start_ = NULL; 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch length_ = 0; 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch inline Vector<T> operator+(int offset) { 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(offset < length_); 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Vector<T>(start_ + offset, length_ - offset); 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Factory method for creating empty vectors. 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static Vector<T> empty() { return Vector<T>(NULL, 0); } 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch template<typename S> 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch static Vector<T> cast(Vector<S> input) { 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Vector<T>(reinterpret_cast<T*>(input.start()), 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch input.length() * sizeof(S) / sizeof(T)); 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool operator==(const Vector<T>& other) const { 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (length_ != other.length_) return false; 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (start_ == other.start_) return true; 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < length_; ++i) { 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if (start_[i] != other.start_[i]) { 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return false; 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return true; 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch protected: 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void set_start(T* start) { start_ = start; } 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T* start_; 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int length_; 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch class RawComparer { 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit RawComparer(int (*cmp)(const T*, const T*)) : cmp_(cmp) {} 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool operator()(const T& a, const T& b) { 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return cmp_(&a, &b) < 0; 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int (*cmp_)(const T*, const T*); 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <typename T> 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass ScopedVector : public Vector<T> { 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch explicit ScopedVector(int length) : Vector<T>(NewArray<T>(length), length) { } 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ~ScopedVector() { 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DeleteArray(this->start()); 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch private: 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DISALLOW_IMPLICIT_CONSTRUCTORS(ScopedVector); 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline int StrLength(const char* string) { 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch size_t length = strlen(string); 149b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch DCHECK(length == static_cast<size_t>(static_cast<int>(length))); 150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return static_cast<int>(length); 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define STATIC_CHAR_VECTOR(x) \ 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch v8::internal::Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(x), \ 156b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch arraysize(x) - 1) 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline Vector<const char> CStrVector(const char* data) { 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Vector<const char>(data, StrLength(data)); 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline Vector<const uint8_t> OneByteVector(const char* data, int length) { 163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Vector<const uint8_t>(reinterpret_cast<const uint8_t*>(data), length); 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 165b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline Vector<const uint8_t> OneByteVector(const char* data) { 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return OneByteVector(data, StrLength(data)); 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline Vector<char> MutableCStrVector(char* data) { 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Vector<char>(data, StrLength(data)); 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochinline Vector<char> MutableCStrVector(char* data, int max) { 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int length = StrLength(data); 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return Vector<char>(data, (length < max) ? length : max); 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} } // namespace v8::internal 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#endif // V8_VECTOR_H_ 183