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     // Allow fetching location() to unsafe-cast the handle. This is necessary
 112     // since we can't concurrently safe-cast. Safe-casting requires looking at
 113     // the heap which may be moving concurrently to the compiler thread.
 114     AllowHandleDereference allow_deref;
 115     return Unique<T>(that.raw_address_,
 116                      Handle<T>(reinterpret_cast<T**>(that.handle_.location())));
 117   }
 118
 119   inline bool IsInitialized() const {
 120     return raw_address_ != NULL || handle_.is_null();
 121   }
 122
 123   // TODO(titzer): this is a hack to migrate to Unique<T> incrementally.
 124   static Unique<T> CreateUninitialized(Handle<T> handle) {
 125     return Unique<T>(NULL, handle);
 126   }
 127
 128   static Unique<T> CreateImmovable(Handle<T> handle) {
 129     return Unique<T>(reinterpret_cast<Address>(*handle), handle);
 130   }
 131
 132   friend class UniqueSet<T>;  // Uses internal details for speed.
 133   template <class U>
 134   friend class Unique;  // For comparing raw_address values.
 135
 136  protected:
 137   Address raw_address_;
 138   Handle<T> handle_;
 139
 140   friend class SideEffectsTracker;
 141 };
 142
 143 template <typename T>
 144 inline std::ostream& operator<<(std::ostream& os, Unique<T> uniq) {
 145   return os << Brief(*uniq.handle());
 146 }
 147
 148
 149 template <typename T>
 150 class UniqueSet FINAL : public ZoneObject {
 151  public:
 152   // Constructor. A new set will be empty.
 153   UniqueSet() : size_(0), capacity_(0), array_(NULL) { }
 154
 155   // Capacity constructor. A new set will be empty.
 156   UniqueSet(int capacity, Zone* zone)
 157       : size_(0), capacity_(capacity),
 158         array_(zone->NewArray<Unique<T> >(capacity)) {
 159     DCHECK(capacity <= kMaxCapacity);
 160   }
 161
 162   // Singleton constructor.
 163   UniqueSet(Unique<T> uniq, Zone* zone)
 164       : size_(1), capacity_(1), array_(zone->NewArray<Unique<T> >(1)) {
 165     array_[0] = uniq;
 166   }
 167
 168   // Add a new element to this unique set. Mutates this set. O(|this|).
 169   void Add(Unique<T> uniq, Zone* zone) {
 170     DCHECK(uniq.IsInitialized());
 171     // Keep the set sorted by the {raw_address} of the unique elements.
 172     for (int i = 0; i < size_; i++) {
 173       if (array_[i] == uniq) return;
 174       if (array_[i].raw_address_ > uniq.raw_address_) {
 175         // Insert in the middle.
 176         Grow(size_ + 1, zone);
 177         for (int j = size_ - 1; j >= i; j--) array_[j + 1] = array_[j];
 178         array_[i] = uniq;
 179         size_++;
 180         return;
 181       }
 182     }
 183     // Append the element to the the end.
 184     Grow(size_ + 1, zone);
 185     array_[size_++] = uniq;
 186   }
 187
 188   // Remove an element from this set. Mutates this set. O(|this|)
 189   void Remove(Unique<T> uniq) {
 190     for (int i = 0; i < size_; i++) {
 191       if (array_[i] == uniq) {
 192         while (++i < size_) array_[i - 1] = array_[i];
 193         size_--;
 194         return;
 195       }
 196     }
 197   }
 198
 199   // Compare this set against another set. O(|this|).
 200   bool Equals(const UniqueSet<T>* that) const {
 201     if (that->size_ != this->size_) return false;
 202     for (int i = 0; i < this->size_; i++) {
 203       if (this->array_[i] != that->array_[i]) return false;
 204     }
 205     return true;
 206   }
 207
 208   // Check whether this set contains the given element. O(|this|)
 209   // TODO(titzer): use binary search for large sets to make this O(log|this|)
 210   template <typename U>
 211   bool Contains(const Unique<U> elem) const {
 212     for (int i = 0; i < this->size_; ++i) {
 213       Unique<T> cand = this->array_[i];
 214       if (cand.raw_address_ >= elem.raw_address_) {
 215         return cand.raw_address_ == elem.raw_address_;
 216       }
 217     }
 218     return false;
 219   }
 220
 221   // Check if this set is a subset of the given set. O(|this| + |that|).
 222   bool IsSubset(const UniqueSet<T>* that) const {
 223     if (that->size_ < this->size_) return false;
 224     int j = 0;
 225     for (int i = 0; i < this->size_; i++) {
 226       Unique<T> sought = this->array_[i];
 227       while (true) {
 228         if (sought == that->array_[j++]) break;
 229         // Fail whenever there are more elements in {this} than {that}.
 230         if ((this->size_ - i) > (that->size_ - j)) return false;
 231       }
 232     }
 233     return true;
 234   }
 235
 236   // Returns a new set representing the intersection of this set and the other.
 237   // O(|this| + |that|).
 238   UniqueSet<T>* Intersect(const UniqueSet<T>* that, Zone* zone) const {
 239     if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet<T>();
 240
 241     UniqueSet<T>* out = new(zone) UniqueSet<T>(
 242         Min(this->size_, that->size_), zone);
 243
 244     int i = 0, j = 0, k = 0;
 245     while (i < this->size_ && j < that->size_) {
 246       Unique<T> a = this->array_[i];
 247       Unique<T> b = that->array_[j];
 248       if (a == b) {
 249         out->array_[k++] = a;
 250         i++;
 251         j++;
 252       } else if (a.raw_address_ < b.raw_address_) {
 253         i++;
 254       } else {
 255         j++;
 256       }
 257     }
 258
 259     out->size_ = k;
 260     return out;
 261   }
 262
 263   // Returns a new set representing the union of this set and the other.
 264   // O(|this| + |that|).
 265   UniqueSet<T>* Union(const UniqueSet<T>* that, Zone* zone) const {
 266     if (that->size_ == 0) return this->Copy(zone);
 267     if (this->size_ == 0) return that->Copy(zone);
 268
 269     UniqueSet<T>* out = new(zone) UniqueSet<T>(
 270         this->size_ + that->size_, zone);
 271
 272     int i = 0, j = 0, k = 0;
 273     while (i < this->size_ && j < that->size_) {
 274       Unique<T> a = this->array_[i];
 275       Unique<T> b = that->array_[j];
 276       if (a == b) {
 277         out->array_[k++] = a;
 278         i++;
 279         j++;
 280       } else if (a.raw_address_ < b.raw_address_) {
 281         out->array_[k++] = a;
 282         i++;
 283       } else {
 284         out->array_[k++] = b;
 285         j++;
 286       }
 287     }
 288
 289     while (i < this->size_) out->array_[k++] = this->array_[i++];
 290     while (j < that->size_) out->array_[k++] = that->array_[j++];
 291
 292     out->size_ = k;
 293     return out;
 294   }
 295
 296   // Returns a new set representing all elements from this set which are not in
 297   // that set. O(|this| * |that|).
 298   UniqueSet<T>* Subtract(const UniqueSet<T>* that, Zone* zone) const {
 299     if (that->size_ == 0) return this->Copy(zone);
 300
 301     UniqueSet<T>* out = new(zone) UniqueSet<T>(this->size_, zone);
 302
 303     int i = 0, j = 0;
 304     while (i < this->size_) {
 305       Unique<T> cand = this->array_[i];
 306       if (!that->Contains(cand)) {
 307         out->array_[j++] = cand;
 308       }
 309       i++;
 310     }
 311
 312     out->size_ = j;
 313     return out;
 314   }
 315
 316   // Makes an exact copy of this set. O(|this|).
 317   UniqueSet<T>* Copy(Zone* zone) const {
 318     UniqueSet<T>* copy = new(zone) UniqueSet<T>(this->size_, zone);
 319     copy->size_ = this->size_;
 320     memcpy(copy->array_, this->array_, this->size_ * sizeof(Unique<T>));
 321     return copy;
 322   }
 323
 324   void Clear() {
 325     size_ = 0;
 326   }
 327
 328   inline int size() const {
 329     return size_;
 330   }
 331
 332   inline Unique<T> at(int index) const {
 333     DCHECK(index >= 0 && index < size_);
 334     return array_[index];
 335   }
 336
 337  private:
 338   // These sets should be small, since operations are implemented with simple
 339   // linear algorithms. Enforce a maximum size.
 340   static const int kMaxCapacity = 65535;
 341
 342   uint16_t size_;
 343   uint16_t capacity_;
 344   Unique<T>* array_;
 345
 346   // Grow the size of internal storage to be at least {size} elements.
 347   void Grow(int size, Zone* zone) {
 348     CHECK(size < kMaxCapacity);  // Enforce maximum size.
 349     if (capacity_ < size) {
 350       int new_capacity = 2 * capacity_ + size;
 351       if (new_capacity > kMaxCapacity) new_capacity = kMaxCapacity;
 352       Unique<T>* new_array = zone->NewArray<Unique<T> >(new_capacity);
 353       if (size_ > 0) {
 354         memcpy(new_array, array_, size_ * sizeof(Unique<T>));
 355       }
 356       capacity_ = new_capacity;
 357       array_ = new_array;
 358     }
 359   }
 360 };
 361
 362 } }  // namespace v8::internal
 363
 364 #endif  // V8_HYDROGEN_UNIQUE_H_