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