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