1b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Copyright 2014 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 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/factory.h" 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "test/cctest/cctest.h" 34b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 35b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochnamespace { 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochusing namespace v8::internal; 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(Set) { 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LocalContext context; 42b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Isolate* isolate = CcTest::i_isolate(); 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Factory* factory = isolate->factory(); 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HandleScope scope(isolate); 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<OrderedHashSet> ordered_set = factory->NewOrderedHashSet(); 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(2, ordered_set->NumberOfBuckets()); 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, ordered_set->NumberOfElements()); 48b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, ordered_set->NumberOfDeletedElements()); 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize); 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj = factory->NewJSObjectFromMap(map); 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!ordered_set->Contains(obj)); 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Add(ordered_set, obj); 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, ordered_set->NumberOfElements()); 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_set->Contains(obj)); 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool was_present = false; 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Remove(ordered_set, obj, &was_present); 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, ordered_set->NumberOfElements()); 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!ordered_set->Contains(obj)); 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Removing a not-present object should set was_present to false. 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Remove(ordered_set, obj, &was_present); 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(!was_present); 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Test for collisions/chaining 67b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map); 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Add(ordered_set, obj1); 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map); 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Add(ordered_set, obj2); 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map); 72b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Add(ordered_set, obj3); 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(3, ordered_set->NumberOfElements()); 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_set->Contains(obj1)); 75b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_set->Contains(obj2)); 76b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_set->Contains(obj3)); 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Test growth 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Add(ordered_set, obj); 80b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map); 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Add(ordered_set, obj4); 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_set->Contains(obj)); 83b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_set->Contains(obj1)); 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_set->Contains(obj2)); 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_set->Contains(obj3)); 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_set->Contains(obj4)); 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(5, ordered_set->NumberOfElements()); 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, ordered_set->NumberOfDeletedElements()); 89b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(4, ordered_set->NumberOfBuckets()); 90b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Test shrinking 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Remove(ordered_set, obj, &was_present); 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 94b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Remove(ordered_set, obj1, &was_present); 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Remove(ordered_set, obj2, &was_present); 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 98b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_set = OrderedHashSet::Remove(ordered_set, obj3, &was_present); 99b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 100b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, ordered_set->NumberOfElements()); 101b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(2, ordered_set->NumberOfBuckets()); 102b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 105b8a8cc1952d61a2f3a2568848933943a543b5d3eBen MurdochTEST(Map) { 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch LocalContext context; 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Isolate* isolate = CcTest::i_isolate(); 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Factory* factory = isolate->factory(); 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch HandleScope scope(isolate); 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<OrderedHashMap> ordered_map = factory->NewOrderedHashMap(); 111b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(2, ordered_map->NumberOfBuckets()); 112b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, ordered_map->NumberOfElements()); 113b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, ordered_map->NumberOfDeletedElements()); 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 115b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize); 116b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj = factory->NewJSObjectFromMap(map); 117b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> val = factory->NewJSObjectFromMap(map); 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_map->Lookup(obj)->IsTheHole()); 119b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Put(ordered_map, obj, val); 120b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, ordered_map->NumberOfElements()); 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Object* lookup = ordered_map->Lookup(obj); 122b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(lookup->SameValue(*val)); 123b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch bool was_present = false; 124b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Remove(ordered_map, obj, &was_present); 125b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 126b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(0, ordered_map->NumberOfElements()); 127b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(ordered_map->Lookup(obj)->IsTheHole()); 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 129b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Test for collisions/chaining 130b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map); 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map); 132b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map); 133b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> val1 = factory->NewJSObjectFromMap(map); 134b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> val2 = factory->NewJSObjectFromMap(map); 135b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> val3 = factory->NewJSObjectFromMap(map); 136b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Put(ordered_map, obj1, val1); 137b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Put(ordered_map, obj2, val2); 138b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Put(ordered_map, obj3, val3); 139b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(3, ordered_map->NumberOfElements()); 140b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lookup = ordered_map->Lookup(obj1); 141b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(lookup->SameValue(*val1)); 142b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lookup = ordered_map->Lookup(obj2); 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(lookup->SameValue(*val2)); 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lookup = ordered_map->Lookup(obj3); 145b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(lookup->SameValue(*val3)); 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Test growth 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Put(ordered_map, obj, val); 149b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map); 150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Handle<JSObject> val4 = factory->NewJSObjectFromMap(map); 151b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Put(ordered_map, obj4, val4); 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lookup = ordered_map->Lookup(obj); 153b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(lookup->SameValue(*val)); 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lookup = ordered_map->Lookup(obj1); 155b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(lookup->SameValue(*val1)); 156b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lookup = ordered_map->Lookup(obj2); 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(lookup->SameValue(*val2)); 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lookup = ordered_map->Lookup(obj3); 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(lookup->SameValue(*val3)); 160b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch lookup = ordered_map->Lookup(obj4); 161b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(lookup->SameValue(*val4)); 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(5, ordered_map->NumberOfElements()); 163b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(4, ordered_map->NumberOfBuckets()); 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 165b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Test shrinking 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Remove(ordered_map, obj, &was_present); 167b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 168b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Remove(ordered_map, obj1, &was_present); 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Remove(ordered_map, obj2, &was_present); 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 172b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ordered_map = OrderedHashMap::Remove(ordered_map, obj3, &was_present); 173b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK(was_present); 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(1, ordered_map->NumberOfElements()); 175b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(2, ordered_map->NumberOfBuckets()); 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 177b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 179b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch} 180