src/vector.h

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