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