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