1// Copyright 2014 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#include <stdlib.h> 29 30#include "src/v8.h" 31 32#include "src/factory.h" 33#include "test/cctest/cctest.h" 34 35namespace { 36 37using namespace v8::internal; 38 39 40TEST(Set) { 41 LocalContext context; 42 Isolate* isolate = CcTest::i_isolate(); 43 Factory* factory = isolate->factory(); 44 HandleScope scope(isolate); 45 Handle<OrderedHashSet> ordered_set = factory->NewOrderedHashSet(); 46 CHECK_EQ(2, ordered_set->NumberOfBuckets()); 47 CHECK_EQ(0, ordered_set->NumberOfElements()); 48 CHECK_EQ(0, ordered_set->NumberOfDeletedElements()); 49 50 Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize); 51 Handle<JSObject> obj = factory->NewJSObjectFromMap(map); 52 CHECK(!ordered_set->Contains(obj)); 53 ordered_set = OrderedHashSet::Add(ordered_set, obj); 54 CHECK_EQ(1, ordered_set->NumberOfElements()); 55 CHECK(ordered_set->Contains(obj)); 56 bool was_present = false; 57 ordered_set = OrderedHashSet::Remove(ordered_set, obj, &was_present); 58 CHECK(was_present); 59 CHECK_EQ(0, ordered_set->NumberOfElements()); 60 CHECK(!ordered_set->Contains(obj)); 61 62 // Removing a not-present object should set was_present to false. 63 ordered_set = OrderedHashSet::Remove(ordered_set, obj, &was_present); 64 CHECK(!was_present); 65 66 // Test for collisions/chaining 67 Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map); 68 ordered_set = OrderedHashSet::Add(ordered_set, obj1); 69 Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map); 70 ordered_set = OrderedHashSet::Add(ordered_set, obj2); 71 Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map); 72 ordered_set = OrderedHashSet::Add(ordered_set, obj3); 73 CHECK_EQ(3, ordered_set->NumberOfElements()); 74 CHECK(ordered_set->Contains(obj1)); 75 CHECK(ordered_set->Contains(obj2)); 76 CHECK(ordered_set->Contains(obj3)); 77 78 // Test growth 79 ordered_set = OrderedHashSet::Add(ordered_set, obj); 80 Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map); 81 ordered_set = OrderedHashSet::Add(ordered_set, obj4); 82 CHECK(ordered_set->Contains(obj)); 83 CHECK(ordered_set->Contains(obj1)); 84 CHECK(ordered_set->Contains(obj2)); 85 CHECK(ordered_set->Contains(obj3)); 86 CHECK(ordered_set->Contains(obj4)); 87 CHECK_EQ(5, ordered_set->NumberOfElements()); 88 CHECK_EQ(0, ordered_set->NumberOfDeletedElements()); 89 CHECK_EQ(4, ordered_set->NumberOfBuckets()); 90 91 // Test shrinking 92 ordered_set = OrderedHashSet::Remove(ordered_set, obj, &was_present); 93 CHECK(was_present); 94 ordered_set = OrderedHashSet::Remove(ordered_set, obj1, &was_present); 95 CHECK(was_present); 96 ordered_set = OrderedHashSet::Remove(ordered_set, obj2, &was_present); 97 CHECK(was_present); 98 ordered_set = OrderedHashSet::Remove(ordered_set, obj3, &was_present); 99 CHECK(was_present); 100 CHECK_EQ(1, ordered_set->NumberOfElements()); 101 CHECK_EQ(2, ordered_set->NumberOfBuckets()); 102} 103 104 105TEST(Map) { 106 LocalContext context; 107 Isolate* isolate = CcTest::i_isolate(); 108 Factory* factory = isolate->factory(); 109 HandleScope scope(isolate); 110 Handle<OrderedHashMap> ordered_map = factory->NewOrderedHashMap(); 111 CHECK_EQ(2, ordered_map->NumberOfBuckets()); 112 CHECK_EQ(0, ordered_map->NumberOfElements()); 113 CHECK_EQ(0, ordered_map->NumberOfDeletedElements()); 114 115 Handle<Map> map = factory->NewMap(JS_OBJECT_TYPE, JSObject::kHeaderSize); 116 Handle<JSObject> obj = factory->NewJSObjectFromMap(map); 117 Handle<JSObject> val = factory->NewJSObjectFromMap(map); 118 CHECK(ordered_map->Lookup(obj)->IsTheHole()); 119 ordered_map = OrderedHashMap::Put(ordered_map, obj, val); 120 CHECK_EQ(1, ordered_map->NumberOfElements()); 121 Object* lookup = ordered_map->Lookup(obj); 122 CHECK(lookup->SameValue(*val)); 123 bool was_present = false; 124 ordered_map = OrderedHashMap::Remove(ordered_map, obj, &was_present); 125 CHECK(was_present); 126 CHECK_EQ(0, ordered_map->NumberOfElements()); 127 CHECK(ordered_map->Lookup(obj)->IsTheHole()); 128 129 // Test for collisions/chaining 130 Handle<JSObject> obj1 = factory->NewJSObjectFromMap(map); 131 Handle<JSObject> obj2 = factory->NewJSObjectFromMap(map); 132 Handle<JSObject> obj3 = factory->NewJSObjectFromMap(map); 133 Handle<JSObject> val1 = factory->NewJSObjectFromMap(map); 134 Handle<JSObject> val2 = factory->NewJSObjectFromMap(map); 135 Handle<JSObject> val3 = factory->NewJSObjectFromMap(map); 136 ordered_map = OrderedHashMap::Put(ordered_map, obj1, val1); 137 ordered_map = OrderedHashMap::Put(ordered_map, obj2, val2); 138 ordered_map = OrderedHashMap::Put(ordered_map, obj3, val3); 139 CHECK_EQ(3, ordered_map->NumberOfElements()); 140 lookup = ordered_map->Lookup(obj1); 141 CHECK(lookup->SameValue(*val1)); 142 lookup = ordered_map->Lookup(obj2); 143 CHECK(lookup->SameValue(*val2)); 144 lookup = ordered_map->Lookup(obj3); 145 CHECK(lookup->SameValue(*val3)); 146 147 // Test growth 148 ordered_map = OrderedHashMap::Put(ordered_map, obj, val); 149 Handle<JSObject> obj4 = factory->NewJSObjectFromMap(map); 150 Handle<JSObject> val4 = factory->NewJSObjectFromMap(map); 151 ordered_map = OrderedHashMap::Put(ordered_map, obj4, val4); 152 lookup = ordered_map->Lookup(obj); 153 CHECK(lookup->SameValue(*val)); 154 lookup = ordered_map->Lookup(obj1); 155 CHECK(lookup->SameValue(*val1)); 156 lookup = ordered_map->Lookup(obj2); 157 CHECK(lookup->SameValue(*val2)); 158 lookup = ordered_map->Lookup(obj3); 159 CHECK(lookup->SameValue(*val3)); 160 lookup = ordered_map->Lookup(obj4); 161 CHECK(lookup->SameValue(*val4)); 162 CHECK_EQ(5, ordered_map->NumberOfElements()); 163 CHECK_EQ(4, ordered_map->NumberOfBuckets()); 164 165 // Test shrinking 166 ordered_map = OrderedHashMap::Remove(ordered_map, obj, &was_present); 167 CHECK(was_present); 168 ordered_map = OrderedHashMap::Remove(ordered_map, obj1, &was_present); 169 CHECK(was_present); 170 ordered_map = OrderedHashMap::Remove(ordered_map, obj2, &was_present); 171 CHECK(was_present); 172 ordered_map = OrderedHashMap::Remove(ordered_map, obj3, &was_present); 173 CHECK(was_present); 174 CHECK_EQ(1, ordered_map->NumberOfElements()); 175 CHECK_EQ(2, ordered_map->NumberOfBuckets()); 176} 177 178 179} 180