From 25372ac1111bbe07e7b30045f382e5653bb3ab8d Mon Sep 17 00:00:00 2001 From: "titzer@chromium.org" Date: Fri, 13 Sep 2013 12:35:36 +0000 Subject: [PATCH] Add Contains(), at(), and a constructor with raw addresses to UniqueSet and Unique. BUG= R=verwaest@chromium.org Review URL: https://codereview.chromium.org/23872027 git-svn-id: http://v8.googlecode.com/svn/branches/bleeding_edge@16716 ce2b1a6d-e550-0410-aec6-3dcde31c8c00 --- src/unique.h | 30 ++++++++++++++++---- test/cctest/test-unique.cc | 68 ++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 92 insertions(+), 6 deletions(-) diff --git a/src/unique.h b/src/unique.h index 7ae704a..38cc336 100644 --- a/src/unique.h +++ b/src/unique.h @@ -64,6 +64,10 @@ class Unique V8_FINAL { handle_ = handle; } + // TODO(titzer): this is a hack to migrate to Unique incrementally. + Unique(Address raw_address, Handle handle) + : raw_address_(raw_address), handle_(handle) { } + // Constructor for handling automatic up casting. // Ex. Unique can be passed when Unique is expected. template Unique(Unique uniq) { @@ -138,7 +142,7 @@ class UniqueSet V8_FINAL : public ZoneObject { } // Compare this set against another set. O(|this|). - bool Equals(UniqueSet* that) { + bool Equals(UniqueSet* that) const { if (that->size_ != this->size_) return false; for (int i = 0; i < this->size_; i++) { if (this->array_[i] != that->array_[i]) return false; @@ -146,8 +150,17 @@ class UniqueSet V8_FINAL : public ZoneObject { return true; } + template + bool Contains(Unique elem) const { + // TODO(titzer): use binary search for larger sets. + for (int i = 0; i < size_; i++) { + if (this->array_[i] == elem) return true; + } + return false; + } + // Check if this set is a subset of the given set. O(|this| + |that|). - bool IsSubset(UniqueSet* that) { + bool IsSubset(UniqueSet* that) const { if (that->size_ < this->size_) return false; int j = 0; for (int i = 0; i < this->size_; i++) { @@ -163,7 +176,7 @@ class UniqueSet V8_FINAL : public ZoneObject { // Returns a new set representing the intersection of this set and the other. // O(|this| + |that|). - UniqueSet* Intersect(UniqueSet* that, Zone* zone) { + UniqueSet* Intersect(UniqueSet* that, Zone* zone) const { if (that->size_ == 0 || this->size_ == 0) return new(zone) UniqueSet(); UniqueSet* out = new(zone) UniqueSet(); @@ -190,7 +203,7 @@ class UniqueSet V8_FINAL : public ZoneObject { // Returns a new set representing the union of this set and the other. // O(|this| + |that|). - UniqueSet* Union(UniqueSet* that, Zone* zone) { + UniqueSet* Union(UniqueSet* that, Zone* zone) const { if (that->size_ == 0) return this->Copy(zone); if (this->size_ == 0) return that->Copy(zone); @@ -222,7 +235,7 @@ class UniqueSet V8_FINAL : public ZoneObject { } // Makes an exact copy of this set. O(|this| + |that|). - UniqueSet* Copy(Zone* zone) { + UniqueSet* Copy(Zone* zone) const { UniqueSet* copy = new(zone) UniqueSet(); copy->size_ = this->size_; copy->capacity_ = this->size_; @@ -231,10 +244,15 @@ class UniqueSet V8_FINAL : public ZoneObject { return copy; } - inline int size() { + inline int size() const { return size_; } + inline Unique at(int index) const { + ASSERT(index >= 0 && index < size_); + return array_[index]; + } + private: // These sets should be small, since operations are implemented with simple // linear algorithms. Enforce a maximum size. diff --git a/test/cctest/test-unique.cc b/test/cctest/test-unique.cc index 1d26858..d482a33 100644 --- a/test/cctest/test-unique.cc +++ b/test/cctest/test-unique.cc @@ -146,6 +146,74 @@ TEST(UniqueSet_Add) { } +TEST(UniqueSet_Contains) { + CcTest::InitializeVM(); + Isolate* isolate = Isolate::Current(); + Factory* factory = isolate->factory(); + HandleScope sc(isolate); + + Unique A(factory->InternalizeUtf8String("A")); + Unique B(factory->InternalizeUtf8String("B")); + Unique C(factory->InternalizeUtf8String("C")); + + Zone zone(isolate); + + UniqueSet* set = new(&zone) UniqueSet(); + + CHECK_EQ(0, set->size()); + set->Add(A, &zone); + CHECK(set->Contains(A)); + CHECK(!set->Contains(B)); + CHECK(!set->Contains(C)); + + set->Add(A, &zone); + CHECK(set->Contains(A)); + CHECK(!set->Contains(B)); + CHECK(!set->Contains(C)); + + set->Add(B, &zone); + CHECK(set->Contains(A)); + CHECK(set->Contains(B)); + + set->Add(C, &zone); + CHECK(set->Contains(A)); + CHECK(set->Contains(B)); + CHECK(set->Contains(C)); +} + + +TEST(UniqueSet_At) { + CcTest::InitializeVM(); + Isolate* isolate = Isolate::Current(); + Factory* factory = isolate->factory(); + HandleScope sc(isolate); + + Unique A(factory->InternalizeUtf8String("A")); + Unique B(factory->InternalizeUtf8String("B")); + Unique C(factory->InternalizeUtf8String("C")); + + Zone zone(isolate); + + UniqueSet* set = new(&zone) UniqueSet(); + + CHECK_EQ(0, set->size()); + set->Add(A, &zone); + CHECK(A == set->at(0)); + + set->Add(A, &zone); + CHECK(A == set->at(0)); + + set->Add(B, &zone); + CHECK(A == set->at(0) || B == set->at(0)); + CHECK(A == set->at(1) || B == set->at(1)); + + set->Add(C, &zone); + CHECK(A == set->at(0) || B == set->at(0) || C == set->at(0)); + CHECK(A == set->at(1) || B == set->at(1) || C == set->at(1)); + CHECK(A == set->at(2) || B == set->at(2) || C == set->at(2)); +} + + template static void CHECK_SETS( UniqueSet* set1, UniqueSet* set2, bool expected) { -- 2.7.4