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 "platform/hashmap.h"
6#include "platform/assert.h"
7#include "platform/globals.h"
8#include "vm/unit_test.h"
9
10namespace dart {
11
12// Default initial size of hashmaps used in these tests.
13static intptr_t kInitialSize = 8;
14
15typedef uint32_t (*IntKeyHash)(uint32_t key);
16
17class IntSet {
18 public:
19 explicit IntSet(IntKeyHash hash)
20 : hash_(hash), map_(SimpleHashMap::SamePointerValue, kInitialSize) {}
21
22 void Insert(int x) {
23 EXPECT_NE(0, x); // 0 corresponds to (void*)nullptr - illegal key value
24 SimpleHashMap::Entry* p =
25 map_.Lookup(key: reinterpret_cast<void*>(x), hash: hash_(x), insert: true);
26 EXPECT(p != nullptr); // insert is set!
27 EXPECT_EQ(reinterpret_cast<void*>(x), p->key);
28 // We don't care about p->value.
29 }
30
31 void Remove(int x) {
32 EXPECT_NE(0, x); // 0 corresponds to (void*)nullptr - illegal key value
33 map_.Remove(key: reinterpret_cast<void*>(x), hash: hash_(x));
34 }
35
36 bool Present(int x) {
37 SimpleHashMap::Entry* p =
38 map_.Lookup(key: reinterpret_cast<void*>(x), hash: hash_(x), insert: false);
39 if (p != nullptr) {
40 EXPECT_EQ(reinterpret_cast<void*>(x), p->key);
41 }
42 return p != nullptr;
43 }
44
45 void Clear() { map_.Clear(); }
46
47 uint32_t occupancy() const {
48 uint32_t count = 0;
49 for (SimpleHashMap::Entry* p = map_.Start(); p != nullptr;
50 p = map_.Next(p)) {
51 count++;
52 }
53 EXPECT_EQ(map_.occupancy_, count);
54 return count;
55 }
56
57 private:
58 IntKeyHash hash_;
59 SimpleHashMap map_;
60};
61
62static uint32_t WordHash(uint32_t key) {
63 return dart::Utils::WordHash(key);
64}
65static uint32_t Hash(uint32_t key) {
66 return 23;
67}
68static uint32_t CollisionHash1(uint32_t key) {
69 return key & 0x3;
70}
71static uint32_t CollisionHash2(uint32_t key) {
72 return kInitialSize - 1;
73}
74static uint32_t CollisionHash3(uint32_t key) {
75 return kInitialSize - 2;
76}
77static uint32_t CollisionHash4(uint32_t key) {
78 return kInitialSize - 2;
79}
80
81void TestSet(IntKeyHash hash, int size) {
82 IntSet set(hash);
83 EXPECT_EQ(0u, set.occupancy());
84
85 set.Insert(x: 1);
86 set.Insert(x: 2);
87 set.Insert(x: 3);
88 set.Insert(x: 4);
89 EXPECT_EQ(4u, set.occupancy());
90
91 set.Insert(x: 2);
92 set.Insert(x: 3);
93 EXPECT_EQ(4u, set.occupancy());
94
95 EXPECT(set.Present(1));
96 EXPECT(set.Present(2));
97 EXPECT(set.Present(3));
98 EXPECT(set.Present(4));
99 EXPECT(!set.Present(5));
100 EXPECT_EQ(4u, set.occupancy());
101
102 set.Remove(x: 1);
103 EXPECT(!set.Present(1));
104 EXPECT(set.Present(2));
105 EXPECT(set.Present(3));
106 EXPECT(set.Present(4));
107 EXPECT_EQ(3u, set.occupancy());
108
109 set.Remove(x: 3);
110 EXPECT(!set.Present(1));
111 EXPECT(set.Present(2));
112 EXPECT(!set.Present(3));
113 EXPECT(set.Present(4));
114 EXPECT_EQ(2u, set.occupancy());
115
116 set.Remove(x: 4);
117 EXPECT(!set.Present(1));
118 EXPECT(set.Present(2));
119 EXPECT(!set.Present(3));
120 EXPECT(!set.Present(4));
121 EXPECT_EQ(1u, set.occupancy());
122
123 set.Clear();
124 EXPECT_EQ(0u, set.occupancy());
125
126 // Insert a long series of values.
127 const uint32_t start = 453;
128 const uint32_t factor = 13;
129 const uint32_t offset = 7;
130 const uint32_t n = size;
131
132 uint32_t x = start;
133 for (uint32_t i = 0; i < n; i++) {
134 EXPECT_EQ(i, set.occupancy());
135 set.Insert(x);
136 x = x * factor + offset;
137 }
138 EXPECT_EQ(n, set.occupancy());
139
140 // Verify the same sequence of values.
141 x = start;
142 for (uint32_t i = 0; i < n; i++) {
143 EXPECT(set.Present(x));
144 x = x * factor + offset;
145 }
146 EXPECT_EQ(n, set.occupancy());
147
148 // Remove all these values.
149 x = start;
150 for (uint32_t i = 0; i < n; i++) {
151 EXPECT_EQ(n - i, set.occupancy());
152 EXPECT(set.Present(x));
153 set.Remove(x);
154 EXPECT(!set.Present(x));
155 x = x * factor + offset;
156
157 // Verify the expected values are still there.
158 int y = start;
159 for (uint32_t j = 0; j < n; j++) {
160 if (j <= i) {
161 EXPECT(!set.Present(y));
162 } else {
163 EXPECT(set.Present(y));
164 }
165 y = y * factor + offset;
166 }
167 }
168 EXPECT_EQ(0u, set.occupancy());
169}
170
171VM_UNIT_TEST_CASE(SimpleHashMap_Basic) {
172 TestSet(hash: WordHash, size: 100);
173 TestSet(hash: Hash, size: 100);
174 TestSet(hash: CollisionHash1, size: 50);
175 TestSet(hash: CollisionHash2, size: 50);
176 TestSet(hash: CollisionHash3, size: 50);
177 TestSet(hash: CollisionHash4, size: 50);
178}
179
180} // namespace dart
181

source code of dart_sdk/runtime/bin/hashmap_test.cc