14a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// Copyright 2013 the V8 project authors. All rights reserved. 23484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// Use of this source code is governed by a BSD-style license that can be 33484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// found in the LICENSE file. 44a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 54a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org#ifndef V8_HYDROGEN_UNIQUE_H_ 64a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org#define V8_HYDROGEN_UNIQUE_H_ 74a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 86313e220249748eb26e1ddcee2bbe857fef03b42machenbach@chromium.org#include "src/handles-inl.h" // TODO(everyone): Fix our inl.h crap 96313e220249748eb26e1ddcee2bbe857fef03b42machenbach@chromium.org#include "src/objects-inl.h" // TODO(everyone): Fix our inl.h crap 107d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org#include "src/string-stream.h" 11196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/utils.h" 12196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/zone.h" 134a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 144a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.orgnamespace v8 { 154a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.orgnamespace internal { 164a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 174a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 184a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.orgtemplate <typename T> 194a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.orgclass UniqueSet; 204a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 214a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 224a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// Represents a handle to an object on the heap, but with the additional 234a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// ability of checking for equality and hashing without accessing the heap. 244a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// 254a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// Creating a Unique<T> requires first dereferencing the handle to obtain 264a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// the address of the object, which is used as the hashcode and the basis for 274a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// comparison. The object can be moved later by the GC, but comparison 284a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// and hashing use the old address of the object, without dereferencing it. 294a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// 304a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// Careful! Comparison of two Uniques is only correct if both were created 314a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org// in the same "era" of GC or if at least one is a non-movable object. 324a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.orgtemplate <typename T> 337d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.orgclass Unique { 344a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org public: 35e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org Unique<T>() : raw_address_(NULL) {} 36e20e19efeef112c26d0e63b1e5118e695b42d855machenbach@chromium.org 373d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org // TODO(titzer): make private and introduce a uniqueness scope. 384a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org explicit Unique(Handle<T> handle) { 394a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (handle.is_null()) { 404a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org raw_address_ = NULL; 414a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } else { 42528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // This is a best-effort check to prevent comparing Unique<T>'s created 43528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // in different GC eras; we require heap allocation to be disallowed at 44528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // creation time. 45528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // NOTE: we currently consider maps to be non-movable, so no special 46528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // assurance is required for creating a Unique<Map>. 47528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // TODO(titzer): other immortable immovable objects are also fine. 48e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(!AllowHeapAllocation::IsAllowed() || handle->IsMap()); 494a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org raw_address_ = reinterpret_cast<Address>(*handle); 50e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK_NE(raw_address_, NULL); // Non-null should imply non-zero address. 514a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 524a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org handle_ = handle; 534a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 544a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 55528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // TODO(titzer): this is a hack to migrate to Unique<T> incrementally. 56528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org Unique(Address raw_address, Handle<T> handle) 57528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org : raw_address_(raw_address), handle_(handle) { } 58528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 594a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Constructor for handling automatic up casting. 60528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // Eg. Unique<JSFunction> can be passed when Unique<Object> is expected. 614a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org template <class S> Unique(Unique<S> uniq) { 624a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org#ifdef DEBUG 634a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org T* a = NULL; 644a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org S* b = NULL; 654a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org a = b; // Fake assignment to enforce type checks. 664a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org USE(a); 674a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org#endif 684a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org raw_address_ = uniq.raw_address_; 69528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org handle_ = uniq.handle_; 704a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 714a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 724a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org template <typename U> 73528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org inline bool operator==(const Unique<U>& other) const { 74e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(IsInitialized() && other.IsInitialized()); 754a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return raw_address_ == other.raw_address_; 764a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 774a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 784a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org template <typename U> 79528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org inline bool operator!=(const Unique<U>& other) const { 80e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(IsInitialized() && other.IsInitialized()); 814a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return raw_address_ != other.raw_address_; 824a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 834a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 84528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org inline intptr_t Hashcode() const { 85e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(IsInitialized()); 864a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return reinterpret_cast<intptr_t>(raw_address_); 874a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 884a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 89528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org inline bool IsNull() const { 90e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(IsInitialized()); 914a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return raw_address_ == NULL; 924a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 934a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 943d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org inline bool IsKnownGlobal(void* global) const { 95e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(IsInitialized()); 963d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org return raw_address_ == reinterpret_cast<Address>(global); 973d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org } 983d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org 99528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org inline Handle<T> handle() const { 1004a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return handle_; 1014a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 1024a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 103cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org template <class S> static Unique<T> cast(Unique<S> that) { 104cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org return Unique<T>(that.raw_address_, Handle<T>::cast(that.handle_)); 105cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 106cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 107528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org inline bool IsInitialized() const { 108528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org return raw_address_ != NULL || handle_.is_null(); 109528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org } 110528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 111528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org // TODO(titzer): this is a hack to migrate to Unique<T> incrementally. 112528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org static Unique<T> CreateUninitialized(Handle<T> handle) { 1133d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org return Unique<T>(reinterpret_cast<Address>(NULL), handle); 1143d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org } 1153d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org 1163d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org static Unique<T> CreateImmovable(Handle<T> handle) { 1173d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org return Unique<T>(reinterpret_cast<Address>(*handle), handle); 118528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org } 119528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 1204a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org friend class UniqueSet<T>; // Uses internal details for speed. 1214a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org template <class U> 1224a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org friend class Unique; // For comparing raw_address values. 1234a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 1247d299ad4dc0ca26e0017b190b48362ad71328ce4machenbach@chromium.org protected: 1254a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Address raw_address_; 1264a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Handle<T> handle_; 127ca2f2040e0e1a10df95bec18e69499f85f4c1316machenbach@chromium.org 128ca2f2040e0e1a10df95bec18e69499f85f4c1316machenbach@chromium.org friend class SideEffectsTracker; 1294a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org}; 1304a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 1314a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 1324a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.orgtemplate <typename T> 133ada3a6017e603965f87fa34f6e2fa60379e8d697machenbach@chromium.orgclass UniqueSet FINAL : public ZoneObject { 1344a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org public: 1354a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Constructor. A new set will be empty. 1364a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org UniqueSet() : size_(0), capacity_(0), array_(NULL) { } 1374a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 138af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org // Capacity constructor. A new set will be empty. 139af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org UniqueSet(int capacity, Zone* zone) 140af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org : size_(0), capacity_(capacity), 141af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org array_(zone->NewArray<Unique<T> >(capacity)) { 142e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(capacity <= kMaxCapacity); 143af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org } 144af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org 145af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org // Singleton constructor. 146af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org UniqueSet(Unique<T> uniq, Zone* zone) 147af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org : size_(1), capacity_(1), array_(zone->NewArray<Unique<T> >(1)) { 148af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org array_[0] = uniq; 149af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org } 150af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org 1514a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Add a new element to this unique set. Mutates this set. O(|this|). 1524a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org void Add(Unique<T> uniq, Zone* zone) { 153e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(uniq.IsInitialized()); 1544a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Keep the set sorted by the {raw_address} of the unique elements. 1554a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org for (int i = 0; i < size_; i++) { 1564a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (array_[i] == uniq) return; 1574a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (array_[i].raw_address_ > uniq.raw_address_) { 1584a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Insert in the middle. 1594a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Grow(size_ + 1, zone); 1604a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org for (int j = size_ - 1; j >= i; j--) array_[j + 1] = array_[j]; 1614a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org array_[i] = uniq; 1624a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org size_++; 1634a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return; 1644a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 1654a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 1664a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Append the element to the the end. 1674a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Grow(size_ + 1, zone); 1684a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org array_[size_++] = uniq; 1694a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 1704a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 171cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org // Remove an element from this set. Mutates this set. O(|this|) 172cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void Remove(Unique<T> uniq) { 173cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org for (int i = 0; i < size_; i++) { 174cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org if (array_[i] == uniq) { 175cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org while (++i < size_) array_[i - 1] = array_[i]; 176cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org size_--; 177cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org return; 178cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 179cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 180cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 181cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 1824a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Compare this set against another set. O(|this|). 183a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org bool Equals(const UniqueSet<T>* that) const { 1844a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (that->size_ != this->size_) return false; 1854a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org for (int i = 0; i < this->size_; i++) { 1864a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (this->array_[i] != that->array_[i]) return false; 1874a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 1884a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return true; 1894a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 1904a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 1913d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org // Check whether this set contains the given element. O(|this|) 1923d079fe881245e49c7ba803b54b4fe6d4b46113cmachenbach@chromium.org // TODO(titzer): use binary search for large sets to make this O(log|this|) 193528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org template <typename U> 194a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org bool Contains(const Unique<U> elem) const { 195af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org for (int i = 0; i < this->size_; ++i) { 196af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org Unique<T> cand = this->array_[i]; 197af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org if (cand.raw_address_ >= elem.raw_address_) { 198af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org return cand.raw_address_ == elem.raw_address_; 199af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org } 200528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org } 201528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org return false; 202528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org } 203528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 2044a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Check if this set is a subset of the given set. O(|this| + |that|). 205a77ec9c2cf67e5b9c707fe42f33574526fed189amachenbach@chromium.org bool IsSubset(const UniqueSet<T>* that) const { 2064a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (that->size_ < this->size_) return false; 2074a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org int j = 0; 2084a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org for (int i = 0; i < this->size_; i++) { 2094a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Unique<T> sought = this->array_[i]; 2104a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org while (true) { 2114a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (sought == that->array_[j++]) break; 2124a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Fail whenever there are more elements in {this} than {that}. 2134a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if ((this->size_ - i) > (that->size_ - j)) return false; 2144a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 2154a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 2164a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return true; 2174a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 2184a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 2194a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Returns a new set representing the intersection of this set and the other. 2204a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // O(|this| + |that|). 221af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org UniqueSet<T>* Intersect(const UniqueSet<T>* that, Zone* zone) const { 2224a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet<T>(); 2234a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 224af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org UniqueSet<T>* out = new(zone) UniqueSet<T>( 225af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org Min(this->size_, that->size_), zone); 2264a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 2274a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org int i = 0, j = 0, k = 0; 2284a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org while (i < this->size_ && j < that->size_) { 2294a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Unique<T> a = this->array_[i]; 2304a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Unique<T> b = that->array_[j]; 2314a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (a == b) { 2324a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org out->array_[k++] = a; 2334a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org i++; 2344a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org j++; 2354a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } else if (a.raw_address_ < b.raw_address_) { 2364a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org i++; 2374a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } else { 2384a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org j++; 2394a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 2404a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 2414a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 2424a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org out->size_ = k; 2434a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return out; 2444a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 2454a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 2464a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Returns a new set representing the union of this set and the other. 2474a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // O(|this| + |that|). 248af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org UniqueSet<T>* Union(const UniqueSet<T>* that, Zone* zone) const { 2494a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (that->size_ == 0) return this->Copy(zone); 2504a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (this->size_ == 0) return that->Copy(zone); 2514a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 252af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org UniqueSet<T>* out = new(zone) UniqueSet<T>( 253af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org this->size_ + that->size_, zone); 2544a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 2554a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org int i = 0, j = 0, k = 0; 2564a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org while (i < this->size_ && j < that->size_) { 2574a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Unique<T> a = this->array_[i]; 2584a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Unique<T> b = that->array_[j]; 2594a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (a == b) { 2604a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org out->array_[k++] = a; 2614a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org i++; 2624a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org j++; 2634a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } else if (a.raw_address_ < b.raw_address_) { 2644a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org out->array_[k++] = a; 2654a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org i++; 2664a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } else { 2674a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org out->array_[k++] = b; 2684a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org j++; 2694a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 2704a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 2714a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 2724a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org while (i < this->size_) out->array_[k++] = this->array_[i++]; 2734a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org while (j < that->size_) out->array_[k++] = that->array_[j++]; 2744a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 2754a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org out->size_ = k; 2764a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return out; 2774a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 2784a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 2798d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org // Returns a new set representing all elements from this set which are not in 2808d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org // that set. O(|this| * |that|). 2818d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org UniqueSet<T>* Subtract(const UniqueSet<T>* that, Zone* zone) const { 2828d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (that->size_ == 0) return this->Copy(zone); 2838d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org 2848d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org UniqueSet<T>* out = new(zone) UniqueSet<T>(this->size_, zone); 2858d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org 2868d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org int i = 0, j = 0; 2878d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org while (i < this->size_) { 2888d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org Unique<T> cand = this->array_[i]; 2898d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org if (!that->Contains(cand)) { 2908d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org out->array_[j++] = cand; 2918d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 2928d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org i++; 2938d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 2948d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org 2958d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org out->size_ = j; 2968d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org return out; 2978d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org } 2988d8413cae4e7eb777aaed22e2901c19f8d5d1297machenbach@chromium.org 299ea9b8ba58955b7efcc3e1550dd33a44fb4530136hpayer@chromium.org // Makes an exact copy of this set. O(|this|). 300528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org UniqueSet<T>* Copy(Zone* zone) const { 301af6f699b0be532b73bc2f6c9e1cf40a57fa7e234machenbach@chromium.org UniqueSet<T>* copy = new(zone) UniqueSet<T>(this->size_, zone); 3024a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org copy->size_ = this->size_; 3034a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org memcpy(copy->array_, this->array_, this->size_ * sizeof(Unique<T>)); 3044a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return copy; 3054a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 3064a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 307cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org void Clear() { 308cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org size_ = 0; 309cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org } 310cfdf67d672b8e2cd6cc1df14c082671511745746machenbach@chromium.org 311528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org inline int size() const { 3124a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org return size_; 3134a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 3144a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 315528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org inline Unique<T> at(int index) const { 316e3c177a423baa3c30225c4e422b6f6c76d38b951machenbach@chromium.org DCHECK(index >= 0 && index < size_); 317528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org return array_[index]; 318528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org } 319528ce02b8680a3ab6d75c7079f180a4016c69b7amachenbach@chromium.org 3204a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org private: 3214a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // These sets should be small, since operations are implemented with simple 3224a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // linear algorithms. Enforce a maximum size. 3234a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org static const int kMaxCapacity = 65535; 3244a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 3254a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org uint16_t size_; 3264a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org uint16_t capacity_; 3274a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Unique<T>* array_; 3284a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 3294a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org // Grow the size of internal storage to be at least {size} elements. 3304a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org void Grow(int size, Zone* zone) { 3314a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org CHECK(size < kMaxCapacity); // Enforce maximum size. 3324a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (capacity_ < size) { 3334a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org int new_capacity = 2 * capacity_ + size; 3344a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (new_capacity > kMaxCapacity) new_capacity = kMaxCapacity; 3354a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org Unique<T>* new_array = zone->NewArray<Unique<T> >(new_capacity); 3364a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org if (size_ > 0) { 3374a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org memcpy(new_array, array_, size_ * sizeof(Unique<T>)); 3384a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 3394a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org capacity_ = new_capacity; 3404a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org array_ = new_array; 3414a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 3424a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org } 3434a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org}; 3444a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 3454a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org} } // namespace v8::internal 3464a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org 3474a35c5a501e5b966f895ddea8e19c3ca232cb23fdslomov@chromium.org#endif // V8_HYDROGEN_UNIQUE_H_ 348