1 // Copyright 2008 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 "v8.h"
31 #include "hashmap.h"
32 #include "cctest.h"
33
34 using namespace v8::internal;
35
DefaultMatchFun(void * a,void * b)36 static bool DefaultMatchFun(void* a, void* b) {
37 return a == b;
38 }
39
40
41 typedef uint32_t (*IntKeyHash)(uint32_t key);
42
43
44 class IntSet {
45 public:
IntSet(IntKeyHash hash)46 explicit IntSet(IntKeyHash hash) : hash_(hash), map_(DefaultMatchFun) {}
47
Insert(int x)48 void Insert(int x) {
49 CHECK_NE(0, x); // 0 corresponds to (void*)NULL - illegal key value
50 HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), hash_(x), true);
51 CHECK(p != NULL); // insert is set!
52 CHECK_EQ(reinterpret_cast<void*>(x), p->key);
53 // we don't care about p->value
54 }
55
Remove(int x)56 void Remove(int x) {
57 CHECK_NE(0, x); // 0 corresponds to (void*)NULL - illegal key value
58 map_.Remove(reinterpret_cast<void*>(x), hash_(x));
59 }
60
Present(int x)61 bool Present(int x) {
62 HashMap::Entry* p =
63 map_.Lookup(reinterpret_cast<void*>(x), hash_(x), false);
64 if (p != NULL) {
65 CHECK_EQ(reinterpret_cast<void*>(x), p->key);
66 }
67 return p != NULL;
68 }
69
Clear()70 void Clear() {
71 map_.Clear();
72 }
73
occupancy() const74 uint32_t occupancy() const {
75 uint32_t count = 0;
76 for (HashMap::Entry* p = map_.Start(); p != NULL; p = map_.Next(p)) {
77 count++;
78 }
79 CHECK_EQ(map_.occupancy(), static_cast<double>(count));
80 return count;
81 }
82
83 private:
84 IntKeyHash hash_;
85 HashMap map_;
86 };
87
88
Hash(uint32_t key)89 static uint32_t Hash(uint32_t key) { return 23; }
CollisionHash(uint32_t key)90 static uint32_t CollisionHash(uint32_t key) { return key & 0x3; }
91
92
TestSet(IntKeyHash hash,int size)93 void TestSet(IntKeyHash hash, int size) {
94 IntSet set(hash);
95 CHECK_EQ(0, set.occupancy());
96
97 set.Insert(1);
98 set.Insert(2);
99 set.Insert(3);
100 CHECK_EQ(3, set.occupancy());
101
102 set.Insert(2);
103 set.Insert(3);
104 CHECK_EQ(3, set.occupancy());
105
106 CHECK(set.Present(1));
107 CHECK(set.Present(2));
108 CHECK(set.Present(3));
109 CHECK(!set.Present(4));
110 CHECK_EQ(3, set.occupancy());
111
112 set.Remove(1);
113 CHECK(!set.Present(1));
114 CHECK(set.Present(2));
115 CHECK(set.Present(3));
116 CHECK_EQ(2, set.occupancy());
117
118 set.Remove(3);
119 CHECK(!set.Present(1));
120 CHECK(set.Present(2));
121 CHECK(!set.Present(3));
122 CHECK_EQ(1, set.occupancy());
123
124 set.Clear();
125 CHECK_EQ(0, set.occupancy());
126
127 // Insert a long series of values.
128 const int start = 453;
129 const int factor = 13;
130 const int offset = 7;
131 const uint32_t n = size;
132
133 int x = start;
134 for (uint32_t i = 0; i < n; i++) {
135 CHECK_EQ(i, static_cast<double>(set.occupancy()));
136 set.Insert(x);
137 x = x * factor + offset;
138 }
139 CHECK_EQ(n, static_cast<double>(set.occupancy()));
140
141 // Verify the same sequence of values.
142 x = start;
143 for (uint32_t i = 0; i < n; i++) {
144 CHECK(set.Present(x));
145 x = x * factor + offset;
146 }
147 CHECK_EQ(n, static_cast<double>(set.occupancy()));
148
149 // Remove all these values.
150 x = start;
151 for (uint32_t i = 0; i < n; i++) {
152 CHECK_EQ(n - i, static_cast<double>(set.occupancy()));
153 CHECK(set.Present(x));
154 set.Remove(x);
155 CHECK(!set.Present(x));
156 x = x * factor + offset;
157
158 // Verify the the expected values are still there.
159 int y = start;
160 for (uint32_t j = 0; j < n; j++) {
161 if (j <= i) {
162 CHECK(!set.Present(y));
163 } else {
164 CHECK(set.Present(y));
165 }
166 y = y * factor + offset;
167 }
168 }
169 CHECK_EQ(0, set.occupancy());
170 }
171
172
TEST(Set)173 TEST(Set) {
174 TestSet(Hash, 100);
175 TestSet(CollisionHash, 50);
176 }
177