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
35 namespace {
36
37 using namespace v8::internal;
38
39
TEST(Set)40 TEST(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
TEST(Map)105 TEST(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