src/v8/src/unique.h

   1 // Copyright 2013 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_HYDROGEN_UNIQUE_H_
   6 #define V8_HYDROGEN_UNIQUE_H_
   7
   8 #include "handles.h"
   9 #include "objects.h"
  10 #include "utils.h"
  11 #include "zone.h"
  12
  13 namespace v8 {
  14 namespace internal {
  15
  16
  17 template <typename T>
  18 class UniqueSet;
  19
  20
  21 // Represents a handle to an object on the heap, but with the additional
  22 // ability of checking for equality and hashing without accessing the heap.
  23 //
  24 // Creating a Unique<T> requires first dereferencing the handle to obtain
  25 // the address of the object, which is used as the hashcode and the basis for
  26 // comparison. The object can be moved later by the GC, but comparison
  27 // and hashing use the old address of the object, without dereferencing it.
  28 //
  29 // Careful! Comparison of two Uniques is only correct if both were created
  30 // in the same "era" of GC or if at least one is a non-movable object.
  31 template <typename T>
  32 class Unique V8_FINAL {
  33  public:
  34   // TODO(titzer): make private and introduce a uniqueness scope.
  35   explicit Unique(Handle<T> handle) {
  36     if (handle.is_null()) {
  37       raw_address_ = NULL;
  38     } else {
  39       // This is a best-effort check to prevent comparing Unique<T>'s created
  40       // in different GC eras; we require heap allocation to be disallowed at
  41       // creation time.
  42       // NOTE: we currently consider maps to be non-movable, so no special
  43       // assurance is required for creating a Unique<Map>.
  44       // TODO(titzer): other immortable immovable objects are also fine.
  45       ASSERT(!AllowHeapAllocation::IsAllowed() || handle->IsMap());
  46       raw_address_ = reinterpret_cast<Address>(*handle);
  47       ASSERT_NE(raw_address_, NULL);  // Non-null should imply non-zero address.
  48     }
  49     handle_ = handle;
  50   }
  51
  52   // TODO(titzer): this is a hack to migrate to Unique<T> incrementally.
  53   Unique(Address raw_address, Handle<T> handle)
  54     : raw_address_(raw_address), handle_(handle) { }
  55
  56   // Constructor for handling automatic up casting.
  57   // Eg. Unique<JSFunction> can be passed when Unique<Object> is expected.
  58   template <class S> Unique(Unique<S> uniq) {
  59 #ifdef DEBUG
  60     T* a = NULL;
  61     S* b = NULL;
  62     a = b;  // Fake assignment to enforce type checks.
  63     USE(a);
  64 #endif
  65     raw_address_ = uniq.raw_address_;
  66     handle_ = uniq.handle_;
  67   }
  68
  69   template <typename U>
  70   inline bool operator==(const Unique<U>& other) const {
  71     ASSERT(IsInitialized() && other.IsInitialized());
  72     return raw_address_ == other.raw_address_;
  73   }
  74
  75   template <typename U>
  76   inline bool operator!=(const Unique<U>& other) const {
  77     ASSERT(IsInitialized() && other.IsInitialized());
  78     return raw_address_ != other.raw_address_;
  79   }
  80
  81   inline intptr_t Hashcode() const {
  82     ASSERT(IsInitialized());
  83     return reinterpret_cast<intptr_t>(raw_address_);
  84   }
  85
  86   inline bool IsNull() const {
  87     ASSERT(IsInitialized());
  88     return raw_address_ == NULL;
  89   }
  90
  91   inline bool IsKnownGlobal(void* global) const {
  92     ASSERT(IsInitialized());
  93     return raw_address_ == reinterpret_cast<Address>(global);
  94   }
  95
  96   inline Handle<T> handle() const {
  97     return handle_;
  98   }
  99
 100   template <class S> static Unique<T> cast(Unique<S> that) {
 101     return Unique<T>(that.raw_address_, Handle<T>::cast(that.handle_));
 102   }
 103
 104   inline bool IsInitialized() const {
 105     return raw_address_ != NULL || handle_.is_null();
 106   }
 107
 108   // TODO(titzer): this is a hack to migrate to Unique<T> incrementally.
 109   static Unique<T> CreateUninitialized(Handle<T> handle) {
 110     return Unique<T>(reinterpret_cast<Address>(NULL), handle);
 111   }
 112
 113   static Unique<T> CreateImmovable(Handle<T> handle) {
 114     return Unique<T>(reinterpret_cast<Address>(*handle), handle);
 115   }
 116
 117   friend class UniqueSet<T>;  // Uses internal details for speed.
 118   template <class U>
 119   friend class Unique;  // For comparing raw_address values.
 120
 121  private:
 122   Unique<T>() : raw_address_(NULL) { }
 123
 124   Address raw_address_;
 125   Handle<T> handle_;
 126
 127   friend class SideEffectsTracker;
 128 };
 129
 130
 131 template <typename T>
 132 class UniqueSet V8_FINAL : public ZoneObject {
 133  public:
 134   // Constructor. A new set will be empty.
 135   UniqueSet() : size_(0), capacity_(0), array_(NULL) { }
 136
 137   // Capacity constructor. A new set will be empty.
 138   UniqueSet(int capacity, Zone* zone)
 139       : size_(0), capacity_(capacity),
 140         array_(zone->NewArray<Unique<T> >(capacity)) {
 141     ASSERT(capacity <= kMaxCapacity);
 142   }
 143
 144   // Singleton constructor.
 145   UniqueSet(Unique<T> uniq, Zone* zone)
 146       : size_(1), capacity_(1), array_(zone->NewArray<Unique<T> >(1)) {
 147     array_[0] = uniq;
 148   }
 149
 150   // Add a new element to this unique set. Mutates this set. O(|this|).
 151   void Add(Unique<T> uniq, Zone* zone) {
 152     ASSERT(uniq.IsInitialized());
 153     // Keep the set sorted by the {raw_address} of the unique elements.
 154     for (int i = 0; i < size_; i++) {
 155       if (array_[i] == uniq) return;
 156       if (array_[i].raw_address_ > uniq.raw_address_) {
 157         // Insert in the middle.
 158         Grow(size_ + 1, zone);
 159         for (int j = size_ - 1; j >= i; j--) array_[j + 1] = array_[j];
 160         array_[i] = uniq;
 161         size_++;
 162         return;
 163       }
 164     }
 165     // Append the element to the the end.
 166     Grow(size_ + 1, zone);
 167     array_[size_++] = uniq;
 168   }
 169
 170   // Remove an element from this set. Mutates this set. O(|this|)
 171   void Remove(Unique<T> uniq) {
 172     for (int i = 0; i < size_; i++) {
 173       if (array_[i] == uniq) {
 174         while (++i < size_) array_[i - 1] = array_[i];
 175         size_--;
 176         return;
 177       }
 178     }
 179   }
 180
 181   // Compare this set against another set. O(|this|).
 182   bool Equals(const UniqueSet<T>* that) const {
 183     if (that->size_ != this->size_) return false;
 184     for (int i = 0; i < this->size_; i++) {
 185       if (this->array_[i] != that->array_[i]) return false;
 186     }
 187     return true;
 188   }
 189
 190   // Check whether this set contains the given element. O(|this|)
 191   // TODO(titzer): use binary search for large sets to make this O(log|this|)
 192   template <typename U>
 193   bool Contains(const Unique<U> elem) const {
 194     for (int i = 0; i < this->size_; ++i) {
 195       Unique<T> cand = this->array_[i];
 196       if (cand.raw_address_ >= elem.raw_address_) {
 197         return cand.raw_address_ == elem.raw_address_;
 198       }
 199     }
 200     return false;
 201   }
 202
 203   // Check if this set is a subset of the given set. O(|this| + |that|).
 204   bool IsSubset(const UniqueSet<T>* that) const {
 205     if (that->size_ < this->size_) return false;
 206     int j = 0;
 207     for (int i = 0; i < this->size_; i++) {
 208       Unique<T> sought = this->array_[i];
 209       while (true) {
 210         if (sought == that->array_[j++]) break;
 211         // Fail whenever there are more elements in {this} than {that}.
 212         if ((this->size_ - i) > (that->size_ - j)) return false;
 213       }
 214     }
 215     return true;
 216   }
 217
 218   // Returns a new set representing the intersection of this set and the other.
 219   // O(|this| + |that|).
 220   UniqueSet<T>* Intersect(const UniqueSet<T>* that, Zone* zone) const {
 221     if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet<T>();
 222
 223     UniqueSet<T>* out = new(zone) UniqueSet<T>(
 224         Min(this->size_, that->size_), zone);
 225
 226     int i = 0, j = 0, k = 0;
 227     while (i < this->size_ && j < that->size_) {
 228       Unique<T> a = this->array_[i];
 229       Unique<T> b = that->array_[j];
 230       if (a == b) {
 231         out->array_[k++] = a;
 232         i++;
 233         j++;
 234       } else if (a.raw_address_ < b.raw_address_) {
 235         i++;
 236       } else {
 237         j++;
 238       }
 239     }
 240
 241     out->size_ = k;
 242     return out;
 243   }
 244
 245   // Returns a new set representing the union of this set and the other.
 246   // O(|this| + |that|).
 247   UniqueSet<T>* Union(const UniqueSet<T>* that, Zone* zone) const {
 248     if (that->size_ == 0) return this->Copy(zone);
 249     if (this->size_ == 0) return that->Copy(zone);
 250
 251     UniqueSet<T>* out = new(zone) UniqueSet<T>(
 252         this->size_ + that->size_, zone);
 253
 254     int i = 0, j = 0, k = 0;
 255     while (i < this->size_ && j < that->size_) {
 256       Unique<T> a = this->array_[i];
 257       Unique<T> b = that->array_[j];
 258       if (a == b) {
 259         out->array_[k++] = a;
 260         i++;
 261         j++;
 262       } else if (a.raw_address_ < b.raw_address_) {
 263         out->array_[k++] = a;
 264         i++;
 265       } else {
 266         out->array_[k++] = b;
 267         j++;
 268       }
 269     }
 270
 271     while (i < this->size_) out->array_[k++] = this->array_[i++];
 272     while (j < that->size_) out->array_[k++] = that->array_[j++];
 273
 274     out->size_ = k;
 275     return out;
 276   }
 277
 278   // Makes an exact copy of this set. O(|this|).
 279   UniqueSet<T>* Copy(Zone* zone) const {
 280     UniqueSet<T>* copy = new(zone) UniqueSet<T>(this->size_, zone);
 281     copy->size_ = this->size_;
 282     memcpy(copy->array_, this->array_, this->size_ * sizeof(Unique<T>));
 283     return copy;
 284   }
 285
 286   void Clear() {
 287     size_ = 0;
 288   }
 289
 290   inline int size() const {
 291     return size_;
 292   }
 293
 294   inline Unique<T> at(int index) const {
 295     ASSERT(index >= 0 && index < size_);
 296     return array_[index];
 297   }
 298
 299  private:
 300   // These sets should be small, since operations are implemented with simple
 301   // linear algorithms. Enforce a maximum size.
 302   static const int kMaxCapacity = 65535;
 303
 304   uint16_t size_;
 305   uint16_t capacity_;
 306   Unique<T>* array_;
 307
 308   // Grow the size of internal storage to be at least {size} elements.
 309   void Grow(int size, Zone* zone) {
 310     CHECK(size < kMaxCapacity);  // Enforce maximum size.
 311     if (capacity_ < size) {
 312       int new_capacity = 2 * capacity_ + size;
 313       if (new_capacity > kMaxCapacity) new_capacity = kMaxCapacity;
 314       Unique<T>* new_array = zone->NewArray<Unique<T> >(new_capacity);
 315       if (size_ > 0) {
 316         memcpy(new_array, array_, size_ * sizeof(Unique<T>));
 317       }
 318       capacity_ = new_capacity;
 319       array_ = new_array;
 320     }
 321   }
 322 };
 323
 324
 325 } }  // namespace v8::internal
 326
 327 #endif  // V8_HYDROGEN_UNIQUE_H_