OLD | NEW |
1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
| 5 #include "platform/hashmap.h" |
5 #include "platform/assert.h" | 6 #include "platform/assert.h" |
6 #include "platform/globals.h" | 7 #include "platform/globals.h" |
7 #include "platform/hashmap.h" | |
8 #include "vm/unit_test.h" | 8 #include "vm/unit_test.h" |
9 | 9 |
10 namespace dart { | 10 namespace dart { |
11 | 11 |
12 // Default initial size of hashmaps used in these tests. | 12 // Default initial size of hashmaps used in these tests. |
13 static intptr_t kInitialSize = 8; | 13 static intptr_t kInitialSize = 8; |
14 | 14 |
15 | |
16 typedef uint32_t (*IntKeyHash)(uint32_t key); | 15 typedef uint32_t (*IntKeyHash)(uint32_t key); |
17 | 16 |
18 | |
19 class IntSet { | 17 class IntSet { |
20 public: | 18 public: |
21 explicit IntSet(IntKeyHash hash) | 19 explicit IntSet(IntKeyHash hash) |
22 : hash_(hash), map_(HashMap::SamePointerValue, kInitialSize) {} | 20 : hash_(hash), map_(HashMap::SamePointerValue, kInitialSize) {} |
23 | 21 |
24 void Insert(int x) { | 22 void Insert(int x) { |
25 EXPECT_NE(0, x); // 0 corresponds to (void*)NULL - illegal key value | 23 EXPECT_NE(0, x); // 0 corresponds to (void*)NULL - illegal key value |
26 HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), hash_(x), true); | 24 HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), hash_(x), true); |
27 EXPECT(p != NULL); // insert is set! | 25 EXPECT(p != NULL); // insert is set! |
28 EXPECT_EQ(reinterpret_cast<void*>(x), p->key); | 26 EXPECT_EQ(reinterpret_cast<void*>(x), p->key); |
(...skipping 23 matching lines...) Expand all Loading... |
52 } | 50 } |
53 EXPECT_EQ(map_.occupancy_, count); | 51 EXPECT_EQ(map_.occupancy_, count); |
54 return count; | 52 return count; |
55 } | 53 } |
56 | 54 |
57 private: | 55 private: |
58 IntKeyHash hash_; | 56 IntKeyHash hash_; |
59 HashMap map_; | 57 HashMap map_; |
60 }; | 58 }; |
61 | 59 |
62 | |
63 static uint32_t WordHash(uint32_t key) { | 60 static uint32_t WordHash(uint32_t key) { |
64 return dart::Utils::WordHash(key); | 61 return dart::Utils::WordHash(key); |
65 } | 62 } |
66 static uint32_t Hash(uint32_t key) { | 63 static uint32_t Hash(uint32_t key) { |
67 return 23; | 64 return 23; |
68 } | 65 } |
69 static uint32_t CollisionHash1(uint32_t key) { | 66 static uint32_t CollisionHash1(uint32_t key) { |
70 return key & 0x3; | 67 return key & 0x3; |
71 } | 68 } |
72 static uint32_t CollisionHash2(uint32_t key) { | 69 static uint32_t CollisionHash2(uint32_t key) { |
73 return kInitialSize - 1; | 70 return kInitialSize - 1; |
74 } | 71 } |
75 static uint32_t CollisionHash3(uint32_t key) { | 72 static uint32_t CollisionHash3(uint32_t key) { |
76 return kInitialSize - 2; | 73 return kInitialSize - 2; |
77 } | 74 } |
78 static uint32_t CollisionHash4(uint32_t key) { | 75 static uint32_t CollisionHash4(uint32_t key) { |
79 return kInitialSize - 2; | 76 return kInitialSize - 2; |
80 } | 77 } |
81 | 78 |
82 | |
83 void TestSet(IntKeyHash hash, int size) { | 79 void TestSet(IntKeyHash hash, int size) { |
84 IntSet set(hash); | 80 IntSet set(hash); |
85 EXPECT_EQ(0u, set.occupancy()); | 81 EXPECT_EQ(0u, set.occupancy()); |
86 | 82 |
87 set.Insert(1); | 83 set.Insert(1); |
88 set.Insert(2); | 84 set.Insert(2); |
89 set.Insert(3); | 85 set.Insert(3); |
90 set.Insert(4); | 86 set.Insert(4); |
91 EXPECT_EQ(4u, set.occupancy()); | 87 EXPECT_EQ(4u, set.occupancy()); |
92 | 88 |
(...skipping 70 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
163 EXPECT(!set.Present(y)); | 159 EXPECT(!set.Present(y)); |
164 } else { | 160 } else { |
165 EXPECT(set.Present(y)); | 161 EXPECT(set.Present(y)); |
166 } | 162 } |
167 y = y * factor + offset; | 163 y = y * factor + offset; |
168 } | 164 } |
169 } | 165 } |
170 EXPECT_EQ(0u, set.occupancy()); | 166 EXPECT_EQ(0u, set.occupancy()); |
171 } | 167 } |
172 | 168 |
173 | |
174 VM_UNIT_TEST_CASE(HashMap_Basic) { | 169 VM_UNIT_TEST_CASE(HashMap_Basic) { |
175 TestSet(WordHash, 100); | 170 TestSet(WordHash, 100); |
176 TestSet(Hash, 100); | 171 TestSet(Hash, 100); |
177 TestSet(CollisionHash1, 50); | 172 TestSet(CollisionHash1, 50); |
178 TestSet(CollisionHash2, 50); | 173 TestSet(CollisionHash2, 50); |
179 TestSet(CollisionHash3, 50); | 174 TestSet(CollisionHash3, 50); |
180 TestSet(CollisionHash4, 50); | 175 TestSet(CollisionHash4, 50); |
181 } | 176 } |
182 | 177 |
183 } // namespace dart | 178 } // namespace dart |
OLD | NEW |