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