1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2013 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Redistribution and use in source and binary forms, with or without 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// modification, are permitted provided that the following conditions are 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// met: 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// * Redistributions of source code must retain the above copyright 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// notice, this list of conditions and the following disclaimer. 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// * Redistributions in binary form must reproduce the above 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// copyright notice, this list of conditions and the following 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// disclaimer in the documentation and/or other materials provided 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// with the distribution. 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// * Neither the name of Google Inc. nor the names of its 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// contributors may be used to endorse or promote products derived 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// from this software without specific prior written permission. 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include <stdlib.h> 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/v8.h" 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 32014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch#include "src/crankshaft/unique.h" 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/factory.h" 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/global-handles.h" 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "test/cctest/cctest.h" 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochusing namespace v8::internal; 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define MAKE_HANDLES_AND_DISALLOW_ALLOCATION \ 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochIsolate* isolate = CcTest::i_isolate(); \ 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochFactory* factory = isolate->factory(); \ 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochHandleScope sc(isolate); \ 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochHandle<String> handles[] = { \ 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch factory->InternalizeUtf8String("A"), \ 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch factory->InternalizeUtf8String("B"), \ 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch factory->InternalizeUtf8String("C"), \ 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch factory->InternalizeUtf8String("D"), \ 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch factory->InternalizeUtf8String("E"), \ 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch factory->InternalizeUtf8String("F"), \ 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch factory->InternalizeUtf8String("G") \ 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch}; \ 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochDisallowHeapAllocation _disable 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define MAKE_UNIQUES_A_B_C \ 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> A(handles[0]); \ 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> B(handles[1]); \ 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> C(handles[2]) 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#define MAKE_UNIQUES_A_B_C_D_E_F_G \ 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> A(handles[0]); \ 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> B(handles[1]); \ 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> C(handles[2]); \ 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> D(handles[3]); \ 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> E(handles[4]); \ 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> F(handles[5]); \ 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> G(handles[6]) 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <class T, class U> 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid CheckHashCodeEqual(Unique<T> a, Unique<U> b) { 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int64_t hasha = static_cast<int64_t>(a.Hashcode()); 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int64_t hashb = static_cast<int64_t>(b.Hashcode()); 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(static_cast<int64_t>(0), hasha); 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(static_cast<int64_t>(0), hashb); 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(hasha, hashb); 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <class T, class U> 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochvoid CheckHashCodeNotEqual(Unique<T> a, Unique<U> b) { 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int64_t hasha = static_cast<int64_t>(a.Hashcode()); 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch int64_t hashb = static_cast<int64_t>(b.Hashcode()); 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(static_cast<int64_t>(0), hasha); 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(static_cast<int64_t>(0), hashb); 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(hasha, hashb); 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueCreate) { 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<String> A = handles[0], B = handles[1]; 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> HA(A); 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(*HA.handle() == *A); 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(*A, *HA.handle()); 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> HA2(A); 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CheckHashCodeEqual(HA, HA2); 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(HA == HA2); 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(*HA.handle(), *HA2.handle()); 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(HA2 == HA); 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(*HA2.handle(), *HA.handle()); 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> HB(B); 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CheckHashCodeNotEqual(HA, HB); 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(HA != HB); 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(*HA.handle(), *HB.handle()); 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(HB != HA); 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(*HB.handle(), *HA.handle()); 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // TODO(titzer): check that Unique properly survives a GC. 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSubsume) { 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<String> A = handles[0]; 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> HA(A); 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(*HA.handle() == *A); 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(*A, *HA.handle()); 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<Object> HO = HA; // Here comes the subsumption, boys. 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CheckHashCodeEqual(HA, HO); 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(HA == HO); 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(*HA.handle(), *HO.handle()); 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(HO == HA); 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(*HO.handle(), *HA.handle()); 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_Add) { 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C; 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 146014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set = new(&zone) UniqueSet<String>(); 149b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, set->size()); 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(A, &zone); 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, set->size()); 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(A, &zone); 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, set->size()); 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(B, &zone); 156b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(2, set->size()); 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(C, &zone); 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(3, set->size()); 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(C, &zone); 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(3, set->size()); 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(B, &zone); 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(3, set->size()); 163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(A, &zone); 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(3, set->size()); 165b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_Remove) { 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C; 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 173014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set = new(&zone) UniqueSet<String>(); 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(A, &zone); 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(B, &zone); 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(C, &zone); 180b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(3, set->size()); 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Remove(A); 183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(2, set->size()); 184b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(A)); 185b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(B)); 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(C)); 187b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 188b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Remove(A); 189b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(2, set->size()); 190b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(A)); 191b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(B)); 192b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(C)); 193b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 194b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Remove(B); 195b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, set->size()); 196b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(A)); 197b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(B)); 198b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(C)); 199b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 200b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Remove(C); 201b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, set->size()); 202b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(A)); 203b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(B)); 204b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(C)); 205b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 206b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 207b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 208b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_Contains) { 209b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 210b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 211b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C; 212b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 213014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 214b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 215b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set = new(&zone) UniqueSet<String>(); 216b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 217b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, set->size()); 218b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(A, &zone); 219b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(A)); 220b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(B)); 221b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(C)); 222b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 223b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(A, &zone); 224b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(A)); 225b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(B)); 226b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set->Contains(C)); 227b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 228b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(B, &zone); 229b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(A)); 230b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(B)); 231b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 232b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(C, &zone); 233b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(A)); 234b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(B)); 235b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set->Contains(C)); 236b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 237b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 238b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 239b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_At) { 240b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 241b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 242b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C; 243b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 244014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 245b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 246b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set = new(&zone) UniqueSet<String>(); 247b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 248b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, set->size()); 249b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(A, &zone); 250b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(A == set->at(0)); 251b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 252b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(A, &zone); 253b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(A == set->at(0)); 254b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 255b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(B, &zone); 256b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(A == set->at(0) || B == set->at(0)); 257b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(A == set->at(1) || B == set->at(1)); 258b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 259b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set->Add(C, &zone); 260b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(A == set->at(0) || B == set->at(0) || C == set->at(0)); 261b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(A == set->at(1) || B == set->at(1) || C == set->at(1)); 262b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(A == set->at(2) || B == set->at(2) || C == set->at(2)); 263b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 264b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 265b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 266b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <class T> 267b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochstatic void CHECK_SETS( 268b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<T>* set1, UniqueSet<T>* set2, bool expected) { 269b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->Equals(set1)); 270b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->Equals(set2)); 271b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(expected == set1->Equals(set2)); 272b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(expected == set2->Equals(set1)); 273b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 274b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 275b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 276b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_Equals) { 277b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 278b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 279b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C; 280b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 281014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 282b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 283b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 284b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 285b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 286b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_SETS(set1, set2, true); 287b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 288b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(A, &zone); 289b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 290b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_SETS(set1, set2, false); 291b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 292b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(A, &zone); 293b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 294b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_SETS(set1, set2, true); 295b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 296b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(B, &zone); 297b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 298b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_SETS(set1, set2, false); 299b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 300b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(C, &zone); 301b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 302b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_SETS(set1, set2, false); 303b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 304b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(C, &zone); 305b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 306b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_SETS(set1, set2, false); 307b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 308b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(B, &zone); 309b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 310b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_SETS(set1, set2, true); 311b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 312b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 313b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 314b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_IsSubset1) { 315b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 316b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 317b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C; 318b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 319014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 320b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 321b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 322b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 323b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 324b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->IsSubset(set2)); 325b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->IsSubset(set1)); 326b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 327b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(A, &zone); 328b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 329b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set1->IsSubset(set2)); 330b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->IsSubset(set1)); 331b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 332b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(B, &zone); 333b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 334b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set1->IsSubset(set2)); 335b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set2->IsSubset(set1)); 336b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 337b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(A, &zone); 338b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 339b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->IsSubset(set2)); 340b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set2->IsSubset(set1)); 341b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 342b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(B, &zone); 343b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 344b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->IsSubset(set2)); 345b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->IsSubset(set1)); 346b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 347b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 348b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 349b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_IsSubset2) { 350b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 351b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 352b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C_D_E_F_G; 353b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 354014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 355b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 356b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 357b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 358b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 359b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(A, &zone); 360b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(C, &zone); 361b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(E, &zone); 362b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 363b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(A, &zone); 364b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(B, &zone); 365b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(C, &zone); 366b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(D, &zone); 367b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(E, &zone); 368b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(F, &zone); 369b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 370b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->IsSubset(set2)); 371b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set2->IsSubset(set1)); 372b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 373b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(G, &zone); 374b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 375b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set1->IsSubset(set2)); 376b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!set2->IsSubset(set1)); 377b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 378b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 379b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 380b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate <class T> 381b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochstatic UniqueSet<T>* MakeSet(Zone* zone, int which, Unique<T>* elements) { 382b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<T>* set = new(zone) UniqueSet<T>(); 383b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < 32; i++) { 384b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch if ((which & (1 << i)) != 0) set->Add(elements[i], zone); 385b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 386b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch return set; 387b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 388b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 389b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 390b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_IsSubsetExhaustive) { 391b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const int kSetSize = 6; 392b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 393b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 394b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 395b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C_D_E_F_G; 396b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 397014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 398b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 399b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> elements[] = { 400b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch A, B, C, D, E, F, G 401b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 402b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 403b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Exhaustively test all sets with <= 6 elements. 404b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < (1 << kSetSize); i++) { 405b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int j = 0; j < (1 << kSetSize); j++) { 406b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set1 = MakeSet(&zone, i, elements); 407b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set2 = MakeSet(&zone, j, elements); 408b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 409b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(((i & j) == i) == set1->IsSubset(set2)); 410b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 411b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 412b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 413b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 414b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 415b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_Intersect1) { 416b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 417b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 418b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C; 419b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 420014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 421b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 422b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 423b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 424b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* result; 425b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 426b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->IsSubset(set2)); 427b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->IsSubset(set1)); 428b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 429b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(A, &zone); 430b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 431b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = set1->Intersect(set2, &zone); 432b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 433b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, result->size()); 434b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->Equals(result)); 435b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 436b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(A, &zone); 437b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 438b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = set1->Intersect(set2, &zone); 439b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 440b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, result->size()); 441b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->Equals(result)); 442b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->Equals(result)); 443b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 444b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(B, &zone); 445b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(C, &zone); 446b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 447b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = set1->Intersect(set2, &zone); 448b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 449b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, result->size()); 450b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->Equals(result)); 451b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 452b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 453b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 454b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_IntersectExhaustive) { 455b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const int kSetSize = 6; 456b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 457b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 458b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 459b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C_D_E_F_G; 460b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 461014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 462b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 463b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> elements[] = { 464b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch A, B, C, D, E, F, G 465b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 466b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 467b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Exhaustively test all sets with <= 6 elements. 468b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < (1 << kSetSize); i++) { 469b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int j = 0; j < (1 << kSetSize); j++) { 470b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set1 = MakeSet(&zone, i, elements); 471b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set2 = MakeSet(&zone, j, elements); 472b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 473b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* result = set1->Intersect(set2, &zone); 474b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* expected = MakeSet(&zone, i & j, elements); 475b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 476b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(result->Equals(expected)); 477b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(expected->Equals(result)); 478b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 479b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 480b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 481b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 482b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 483b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_Union1) { 484b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 485b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 486b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C; 487b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 488014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 489b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 490b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set1 = new(&zone) UniqueSet<String>(); 491b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set2 = new(&zone) UniqueSet<String>(); 492b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* result; 493b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 494b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->IsSubset(set2)); 495b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->IsSubset(set1)); 496b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 497b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set1->Add(A, &zone); 498b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 499b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = set1->Union(set2, &zone); 500b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 501b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, result->size()); 502b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->Equals(result)); 503b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 504b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(A, &zone); 505b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 506b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = set1->Union(set2, &zone); 507b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 508b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, result->size()); 509b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set1->Equals(result)); 510b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->Equals(result)); 511b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 512b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(B, &zone); 513b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch set2->Add(C, &zone); 514b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 515b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch result = set1->Union(set2, &zone); 516b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 517b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(3, result->size()); 518b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(set2->Equals(result)); 519b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 520b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 521b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 522b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(UniqueSet_UnionExhaustive) { 523b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const int kSetSize = 6; 524b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 525b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CcTest::InitializeVM(); 526b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_HANDLES_AND_DISALLOW_ALLOCATION; 527b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch MAKE_UNIQUES_A_B_C_D_E_F_G; 528b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 529014dc512cdd3e367bee49a713fdc5ed92584a3e5Ben Murdoch Zone zone; 530b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 531b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Unique<String> elements[] = { 532b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch A, B, C, D, E, F, G 533b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch }; 534b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 535b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Exhaustively test all sets with <= 6 elements. 536b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < (1 << kSetSize); i++) { 537b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int j = 0; j < (1 << kSetSize); j++) { 538b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set1 = MakeSet(&zone, i, elements); 539b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* set2 = MakeSet(&zone, j, elements); 540b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 541b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* result = set1->Union(set2, &zone); 542b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch UniqueSet<String>* expected = MakeSet(&zone, i | j, elements); 543b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 544b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(result->Equals(expected)); 545b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(expected->Equals(result)); 546b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 547b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 548b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 549