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*)NULL - illegal key value
24 SimpleHashMap::Entry* p =
25 map_.Lookup(reinterpret_cast<void*>(x), hash_(x), true);
26 EXPECT(p != NULL); // 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*)NULL - illegal key value
33 map_.Remove(reinterpret_cast<void*>(x), hash_(x));
34 }
35
36 bool Present(int x) {
37 SimpleHashMap::Entry* p =
38 map_.Lookup(reinterpret_cast<void*>(x), hash_(x), false);
39 if (p != NULL) {
40 EXPECT_EQ(reinterpret_cast<void*>(x), p->key);
41 }
42 return p != NULL;
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 != NULL; p = map_.Next(p)) {
50 count++;
51 }
52 EXPECT_EQ(map_.occupancy_, count);
53 return count;
54 }
55
56 private:
57 IntKeyHash hash_;
58 SimpleHashMap map_;
59};
60
61static uint32_t WordHash(uint32_t key) {
62 return dart::Utils::WordHash(key);
63}
64static uint32_t Hash(uint32_t key) {
65 return 23;
66}
67static uint32_t CollisionHash1(uint32_t key) {
68 return key & 0x3;
69}
70static uint32_t CollisionHash2(uint32_t key) {
71 return kInitialSize - 1;
72}
73static uint32_t CollisionHash3(uint32_t key) {
74 return kInitialSize - 2;
75}
76static uint32_t CollisionHash4(uint32_t key) {
77 return kInitialSize - 2;
78}
79
80void TestSet(IntKeyHash hash, int size) {
81 IntSet set(hash);
82 EXPECT_EQ(0u, set.occupancy());
83
84 set.Insert(1);
85 set.Insert(2);
86 set.Insert(3);
87 set.Insert(4);
88 EXPECT_EQ(4u, set.occupancy());
89
90 set.Insert(2);
91 set.Insert(3);
92 EXPECT_EQ(4u, set.occupancy());
93
94 EXPECT(set.Present(1));
95 EXPECT(set.Present(2));
96 EXPECT(set.Present(3));
97 EXPECT(set.Present(4));
98 EXPECT(!set.Present(5));
99 EXPECT_EQ(4u, set.occupancy());
100
101 set.Remove(1);
102 EXPECT(!set.Present(1));
103 EXPECT(set.Present(2));
104 EXPECT(set.Present(3));
105 EXPECT(set.Present(4));
106 EXPECT_EQ(3u, set.occupancy());
107
108 set.Remove(3);
109 EXPECT(!set.Present(1));
110 EXPECT(set.Present(2));
111 EXPECT(!set.Present(3));
112 EXPECT(set.Present(4));
113 EXPECT_EQ(2u, set.occupancy());
114
115 set.Remove(4);
116 EXPECT(!set.Present(1));
117 EXPECT(set.Present(2));
118 EXPECT(!set.Present(3));
119 EXPECT(!set.Present(4));
120 EXPECT_EQ(1u, set.occupancy());
121
122 set.Clear();
123 EXPECT_EQ(0u, set.occupancy());
124
125 // Insert a long series of values.
126 const uint32_t start = 453;
127 const uint32_t factor = 13;
128 const uint32_t offset = 7;
129 const uint32_t n = size;
130
131 uint32_t x = start;
132 for (uint32_t i = 0; i < n; i++) {
133 EXPECT_EQ(i, set.occupancy());
134 set.Insert(x);
135 x = x * factor + offset;
136 }
137 EXPECT_EQ(n, set.occupancy());
138
139 // Verify the same sequence of values.
140 x = start;
141 for (uint32_t i = 0; i < n; i++) {
142 EXPECT(set.Present(x));
143 x = x * factor + offset;
144 }
145 EXPECT_EQ(n, set.occupancy());
146
147 // Remove all these values.
148 x = start;
149 for (uint32_t i = 0; i < n; i++) {
150 EXPECT_EQ(n - i, set.occupancy());
151 EXPECT(set.Present(x));
152 set.Remove(x);
153 EXPECT(!set.Present(x));
154 x = x * factor + offset;
155
156 // Verify the expected values are still there.
157 int y = start;
158 for (uint32_t j = 0; j < n; j++) {
159 if (j <= i) {
160 EXPECT(!set.Present(y));
161 } else {
162 EXPECT(set.Present(y));
163 }
164 y = y * factor + offset;
165 }
166 }
167 EXPECT_EQ(0u, set.occupancy());
168}
169
170VM_UNIT_TEST_CASE(SimpleHashMap_Basic) {
171 TestSet(WordHash, 100);
172 TestSet(Hash, 100);
173 TestSet(CollisionHash1, 50);
174 TestSet(CollisionHash2, 50);
175 TestSet(CollisionHash3, 50);
176 TestSet(CollisionHash4, 50);
177}
178
179} // namespace dart
180