1// Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#include "vm/hash_map.h"
6#include "platform/assert.h"
7#include "vm/unit_test.h"
8
9namespace dart {
10
11class TestValue {
12 public:
13 explicit TestValue(intptr_t x) : x_(x) {}
14 intptr_t Hashcode() const { return x_ & 1; }
15 bool Equals(TestValue* other) { return x_ == other->x_; }
16
17 private:
18 intptr_t x_;
19};
20
21TEST_CASE(DirectChainedHashMap) {
22 DirectChainedHashMap<PointerKeyValueTrait<TestValue> > map;
23 EXPECT(map.IsEmpty());
24 TestValue v1(0);
25 TestValue v2(1);
26 TestValue v3(0);
27 map.Insert(&v1);
28 EXPECT(map.LookupValue(&v1) == &v1);
29 map.Insert(&v2);
30 EXPECT(map.LookupValue(&v1) == &v1);
31 EXPECT(map.LookupValue(&v2) == &v2);
32 EXPECT(map.LookupValue(&v3) == &v1);
33 EXPECT(map.Remove(&v1));
34 EXPECT(map.Lookup(&v1) == NULL);
35 map.Insert(&v1);
36 DirectChainedHashMap<PointerKeyValueTrait<TestValue> > map2(map);
37 EXPECT(map2.LookupValue(&v1) == &v1);
38 EXPECT(map2.LookupValue(&v2) == &v2);
39 EXPECT(map2.LookupValue(&v3) == &v1);
40}
41
42TEST_CASE(DirectChainedHashMapInsertRemove) {
43 DirectChainedHashMap<PointerKeyValueTrait<TestValue> > map;
44 EXPECT(map.IsEmpty());
45 TestValue v1(1);
46 TestValue v2(3); // Note: v1, v2, v3 should have the same hash.
47 TestValue v3(5);
48
49 // Start with adding and removing the same element.
50 map.Insert(&v1);
51 EXPECT(map.LookupValue(&v1) == &v1);
52 EXPECT(map.Remove(&v1));
53 EXPECT(map.Lookup(&v1) == NULL);
54
55 // Inserting v2 first should put it at the head of the list.
56 map.Insert(&v2);
57 map.Insert(&v1);
58 EXPECT(map.LookupValue(&v2) == &v2);
59 EXPECT(map.LookupValue(&v1) == &v1);
60
61 // Check to see if removing the head of the list causes issues.
62 EXPECT(map.Remove(&v2));
63 EXPECT(map.Lookup(&v2) == NULL);
64 EXPECT(map.LookupValue(&v1) == &v1);
65
66 // Reinsert v2, which will place it at the back of the hash map list.
67 map.Insert(&v2);
68 EXPECT(map.LookupValue(&v2) == &v2);
69
70 // Remove from the back of the hash map list.
71 EXPECT(map.Remove(&v2));
72 EXPECT(map.Lookup(&v2) == NULL);
73 EXPECT(map.Remove(&v1));
74 EXPECT(map.Lookup(&v1) == NULL);
75
76 // Check to see that removing an invalid element returns false.
77 EXPECT(!map.Remove(&v1));
78
79 // One last case: remove from the middle of a hash map list.
80 map.Insert(&v1);
81 map.Insert(&v2);
82 map.Insert(&v3);
83
84 EXPECT(map.LookupValue(&v1) == &v1);
85 EXPECT(map.LookupValue(&v2) == &v2);
86 EXPECT(map.LookupValue(&v3) == &v3);
87
88 EXPECT(map.Remove(&v2));
89 EXPECT(map.LookupValue(&v1) == &v1);
90 EXPECT(map.Lookup(&v2) == NULL);
91 EXPECT(map.LookupValue(&v3) == &v3);
92
93 EXPECT(map.Remove(&v1));
94 EXPECT(map.Remove(&v3));
95
96 EXPECT(map.IsEmpty());
97}
98
99TEST_CASE(MallocDirectChainedHashMap) {
100 MallocDirectChainedHashMap<PointerKeyValueTrait<TestValue> > map;
101 EXPECT(map.IsEmpty());
102 TestValue v1(0);
103 TestValue v2(1);
104 TestValue v3(0);
105 map.Insert(&v1);
106 EXPECT(map.LookupValue(&v1) == &v1);
107 map.Insert(&v2);
108 EXPECT(map.LookupValue(&v1) == &v1);
109 EXPECT(map.LookupValue(&v2) == &v2);
110 EXPECT(map.LookupValue(&v3) == &v1);
111 MallocDirectChainedHashMap<PointerKeyValueTrait<TestValue> > map2(map);
112 EXPECT(map2.LookupValue(&v1) == &v1);
113 EXPECT(map2.LookupValue(&v2) == &v2);
114 EXPECT(map2.LookupValue(&v3) == &v1);
115}
116
117class IntptrPair {
118 public:
119 IntptrPair() : first_(-1), second_(-1) {}
120 IntptrPair(intptr_t first, intptr_t second)
121 : first_(first), second_(second) {}
122
123 intptr_t first() const { return first_; }
124 intptr_t second() const { return second_; }
125
126 bool operator==(const IntptrPair& other) {
127 return (first_ == other.first_) && (second_ == other.second_);
128 }
129
130 bool operator!=(const IntptrPair& other) {
131 return (first_ != other.first_) || (second_ != other.second_);
132 }
133
134 private:
135 intptr_t first_;
136 intptr_t second_;
137};
138
139TEST_CASE(DirectChainedHashMapIterator) {
140 IntptrPair p1(1, 1);
141 IntptrPair p2(2, 2);
142 IntptrPair p3(3, 3);
143 IntptrPair p4(4, 4);
144 IntptrPair p5(5, 5);
145 DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair> > map;
146 EXPECT(map.IsEmpty());
147 DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair> >::Iterator it =
148 map.GetIterator();
149 EXPECT(it.Next() == NULL);
150 it.Reset();
151
152 map.Insert(p1);
153 EXPECT(*it.Next() == p1);
154 it.Reset();
155
156 map.Insert(p2);
157 map.Insert(p3);
158 map.Insert(p4);
159 map.Insert(p5);
160 intptr_t count = 0;
161 intptr_t sum = 0;
162 while (true) {
163 IntptrPair* p = it.Next();
164 if (p == NULL) {
165 break;
166 }
167 count++;
168 sum += p->second();
169 }
170
171 EXPECT(count == 5);
172 EXPECT(sum == 15);
173}
174
175TEST_CASE(DirectChainedHashMapIteratorWithCollisionInLastBucket) {
176 intptr_t values[] = {65, 325, 329, 73, 396, 207, 215, 93, 227, 39,
177 431, 112, 176, 313, 188, 317, 61, 127, 447};
178 IntMap<intptr_t> map;
179
180 for (intptr_t value : values) {
181 map.Insert(value, value);
182 }
183
184 bool visited[ARRAY_SIZE(values)] = {};
185 intptr_t count = 0;
186 auto it = map.GetIterator();
187 for (auto* p = it.Next(); p != nullptr; p = it.Next()) {
188 ++count;
189 bool found = false;
190 intptr_t i = 0;
191 for (intptr_t v : values) {
192 if (v == p->key) {
193 EXPECT(v == p->value);
194 EXPECT(!visited[i]);
195 visited[i] = true;
196 found = true;
197 break;
198 }
199 ++i;
200 }
201 EXPECT(found);
202 }
203 EXPECT(count == ARRAY_SIZE(values));
204 for (bool is_visited : visited) {
205 EXPECT(is_visited);
206 }
207}
208
209TEST_CASE(CStringMap) {
210 const char* const kConst1 = "test";
211 const char* const kConst2 = "test 2";
212
213 char* const str1 = OS::SCreate(nullptr, "%s", kConst1);
214 char* const str2 = OS::SCreate(nullptr, "%s", kConst2);
215 char* const str3 = OS::SCreate(nullptr, "%s", kConst1);
216
217 // Make sure these strings are pointer-distinct, but C-string-equal.
218 EXPECT_NE(str1, str3);
219 EXPECT_STREQ(str1, str3);
220
221 const intptr_t i1 = 1;
222 const intptr_t i2 = 2;
223
224 CStringMap<intptr_t> map;
225 EXPECT(map.IsEmpty());
226
227 map.Insert({str1, i1});
228 EXPECT_NOTNULL(map.Lookup(str1));
229 EXPECT_EQ(i1, map.LookupValue(str1));
230 EXPECT_NULLPTR(map.Lookup(str2));
231 EXPECT_NOTNULL(map.Lookup(str3));
232 EXPECT_EQ(i1, map.LookupValue(str3));
233
234 map.Insert({str2, i2});
235 EXPECT_NOTNULL(map.Lookup(str1));
236 EXPECT_EQ(i1, map.LookupValue(str1));
237 EXPECT_NOTNULL(map.Lookup(str2));
238 EXPECT_EQ(i2, map.LookupValue(str2));
239 EXPECT_NOTNULL(map.Lookup(str3));
240 EXPECT_EQ(i1, map.LookupValue(str3));
241
242 EXPECT(map.Remove(str3));
243 EXPECT_NULLPTR(map.Lookup(str1));
244 EXPECT_NOTNULL(map.Lookup(str2));
245 EXPECT_EQ(i2, map.LookupValue(str2));
246 EXPECT_NULLPTR(map.Lookup(str3));
247
248 EXPECT(!map.Remove(str3));
249 EXPECT(map.Remove(str2));
250 EXPECT(map.IsEmpty());
251
252 free(str3);
253 free(str2);
254 free(str1);
255}
256
257TEST_CASE(CStringMapUpdate) {
258 const char* const kConst1 = "test";
259 const char* const kConst2 = "test 2";
260
261 char* str1 = OS::SCreate(nullptr, "%s", kConst1);
262 char* str2 = OS::SCreate(nullptr, "%s", kConst2);
263 char* str3 = OS::SCreate(nullptr, "%s", kConst1);
264 char* str4 = OS::SCreate(nullptr, "%s", kConst1); // Only used for lookup.
265
266 // Make sure these strings are pointer-distinct, but C-string-equal.
267 EXPECT_NE(str1, str3);
268 EXPECT_NE(str1, str4);
269 EXPECT_NE(str3, str4);
270 EXPECT_STREQ(str1, str3);
271 EXPECT_STREQ(str1, str4);
272
273 CStringKeyValueTrait<intptr_t>::Pair p1 = {str1, 1};
274 CStringKeyValueTrait<intptr_t>::Pair p2 = {str2, 2};
275 CStringKeyValueTrait<intptr_t>::Pair p3 = {str3, 3};
276
277 CStringMap<intptr_t> map;
278 EXPECT(map.IsEmpty());
279
280 map.Update(p1);
281 EXPECT_NOTNULL(map.Lookup(str1));
282 EXPECT_EQ(p1.value, map.LookupValue(str1));
283 EXPECT_NULLPTR(map.Lookup(str2));
284 EXPECT_NOTNULL(map.Lookup(str3));
285 EXPECT_EQ(p1.value, map.LookupValue(str3));
286 EXPECT_NOTNULL(map.Lookup(str4));
287 EXPECT_EQ(p1.value, map.LookupValue(str4));
288
289 map.Update(p2);
290 EXPECT_NOTNULL(map.Lookup(str1));
291 EXPECT_EQ(p1.value, map.LookupValue(str1));
292 EXPECT_NOTNULL(map.Lookup(str2));
293 EXPECT_EQ(p2.value, map.LookupValue(str2));
294 EXPECT_NOTNULL(map.Lookup(str3));
295 EXPECT_EQ(p1.value, map.LookupValue(str3));
296 EXPECT_NOTNULL(map.Lookup(str4));
297 EXPECT_EQ(p1.value, map.LookupValue(str4));
298
299 // Check Lookup after Update.
300 map.Update(p3);
301 EXPECT_NOTNULL(map.Lookup(str1));
302 EXPECT_EQ(p3.value, map.LookupValue(str1));
303 EXPECT_NOTNULL(map.Lookup(str2));
304 EXPECT_EQ(p2.value, map.LookupValue(str2));
305 EXPECT_NOTNULL(map.Lookup(str3));
306 EXPECT_EQ(p3.value, map.LookupValue(str3));
307 EXPECT_NOTNULL(map.Lookup(str4));
308 EXPECT_EQ(p3.value, map.LookupValue(str4));
309
310 // Check that single Remove after only Updates ensures Lookup fails after.
311 EXPECT(map.Remove(str3));
312 EXPECT_NULLPTR(map.Lookup(str1));
313 EXPECT_NOTNULL(map.Lookup(str2));
314 EXPECT_EQ(p2.value, map.LookupValue(str2));
315 EXPECT_NULLPTR(map.Lookup(str3));
316 EXPECT_NULLPTR(map.Lookup(str4));
317
318 EXPECT(!map.Remove(str3));
319 EXPECT(map.Remove(str2));
320 EXPECT(map.IsEmpty());
321
322 // Quick double-check that these weren't side-effected by the implementation
323 // of hash maps (p1 especially).
324 EXPECT_EQ(str1, p1.key);
325 EXPECT_EQ(1, p1.value);
326 EXPECT_EQ(str2, p2.key);
327 EXPECT_EQ(2, p2.value);
328 EXPECT_EQ(str3, p3.key);
329 EXPECT_EQ(3, p3.value);
330
331 free(str4);
332 free(str3);
333 free(str2);
334 free(str1);
335}
336
337} // namespace dart
338