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/assert.h" | 5 #include "platform/assert.h" |
6 #include "platform/globals.h" | 6 #include "platform/globals.h" |
7 #include "platform/hashmap.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 | 15 |
16 typedef uint32_t (*IntKeyHash)(uint32_t key); | 16 typedef uint32_t (*IntKeyHash)(uint32_t key); |
17 | 17 |
18 | 18 |
19 class IntSet { | 19 class IntSet { |
20 public: | 20 public: |
21 explicit IntSet(IntKeyHash hash) | 21 explicit IntSet(IntKeyHash hash) |
22 : hash_(hash), map_(HashMap::SamePointerValue, kInitialSize) {} | 22 : hash_(hash), map_(HashMap::SamePointerValue, kInitialSize) {} |
23 | 23 |
24 void Insert(int x) { | 24 void Insert(int x) { |
25 EXPECT_NE(0, x); // 0 corresponds to (void*)NULL - illegal key value | 25 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); | 26 HashMap::Entry* p = map_.Lookup(reinterpret_cast<void*>(x), hash_(x), true); |
27 EXPECT(p != NULL); // insert is set! | 27 EXPECT(p != NULL); // insert is set! |
28 EXPECT_EQ(reinterpret_cast<void*>(x), p->key); | 28 EXPECT_EQ(reinterpret_cast<void*>(x), p->key); |
29 // We don't care about p->value. | 29 // We don't care about p->value. |
30 } | 30 } |
31 | 31 |
32 void Remove(int x) { | 32 void Remove(int x) { |
33 EXPECT_NE(0, x); // 0 corresponds to (void*)NULL - illegal key value | 33 EXPECT_NE(0, x); // 0 corresponds to (void*)NULL - illegal key value |
34 map_.Remove(reinterpret_cast<void*>(x), hash_(x)); | 34 map_.Remove(reinterpret_cast<void*>(x), hash_(x)); |
35 } | 35 } |
36 | 36 |
37 bool Present(int x) { | 37 bool Present(int x) { |
38 HashMap::Entry* p = | 38 HashMap::Entry* p = |
39 map_.Lookup(reinterpret_cast<void*>(x), hash_(x), false); | 39 map_.Lookup(reinterpret_cast<void*>(x), hash_(x), false); |
40 if (p != NULL) { | 40 if (p != NULL) { |
41 EXPECT_EQ(reinterpret_cast<void*>(x), p->key); | 41 EXPECT_EQ(reinterpret_cast<void*>(x), p->key); |
42 } | 42 } |
43 return p != NULL; | 43 return p != NULL; |
44 } | 44 } |
45 | 45 |
46 void Clear() { | 46 void Clear() { map_.Clear(); } |
47 map_.Clear(); | |
48 } | |
49 | 47 |
50 uint32_t occupancy() const { | 48 uint32_t occupancy() const { |
51 uint32_t count = 0; | 49 uint32_t count = 0; |
52 for (HashMap::Entry* p = map_.Start(); p != NULL; p = map_.Next(p)) { | 50 for (HashMap::Entry* p = map_.Start(); p != NULL; p = map_.Next(p)) { |
53 count++; | 51 count++; |
54 } | 52 } |
55 EXPECT_EQ(map_.occupancy_, count); | 53 EXPECT_EQ(map_.occupancy_, count); |
56 return count; | 54 return count; |
57 } | 55 } |
58 | 56 |
59 private: | 57 private: |
60 IntKeyHash hash_; | 58 IntKeyHash hash_; |
61 HashMap map_; | 59 HashMap map_; |
62 }; | 60 }; |
63 | 61 |
64 | 62 |
65 static uint32_t WordHash(uint32_t key) { return dart::Utils::WordHash(key); } | 63 static uint32_t WordHash(uint32_t key) { |
66 static uint32_t Hash(uint32_t key) { return 23; } | 64 return dart::Utils::WordHash(key); |
67 static uint32_t CollisionHash1(uint32_t key) { return key & 0x3; } | 65 } |
68 static uint32_t CollisionHash2(uint32_t key) { return kInitialSize - 1; } | 66 static uint32_t Hash(uint32_t key) { |
69 static uint32_t CollisionHash3(uint32_t key) { return kInitialSize - 2; } | 67 return 23; |
70 static uint32_t CollisionHash4(uint32_t key) { return kInitialSize - 2; } | 68 } |
| 69 static uint32_t CollisionHash1(uint32_t key) { |
| 70 return key & 0x3; |
| 71 } |
| 72 static uint32_t CollisionHash2(uint32_t key) { |
| 73 return kInitialSize - 1; |
| 74 } |
| 75 static uint32_t CollisionHash3(uint32_t key) { |
| 76 return kInitialSize - 2; |
| 77 } |
| 78 static uint32_t CollisionHash4(uint32_t key) { |
| 79 return kInitialSize - 2; |
| 80 } |
71 | 81 |
72 | 82 |
73 void TestSet(IntKeyHash hash, int size) { | 83 void TestSet(IntKeyHash hash, int size) { |
74 IntSet set(hash); | 84 IntSet set(hash); |
75 EXPECT_EQ(0u, set.occupancy()); | 85 EXPECT_EQ(0u, set.occupancy()); |
76 | 86 |
77 set.Insert(1); | 87 set.Insert(1); |
78 set.Insert(2); | 88 set.Insert(2); |
79 set.Insert(3); | 89 set.Insert(3); |
80 set.Insert(4); | 90 set.Insert(4); |
(...skipping 83 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
164 UNIT_TEST_CASE(Set) { | 174 UNIT_TEST_CASE(Set) { |
165 TestSet(WordHash, 100); | 175 TestSet(WordHash, 100); |
166 TestSet(Hash, 100); | 176 TestSet(Hash, 100); |
167 TestSet(CollisionHash1, 50); | 177 TestSet(CollisionHash1, 50); |
168 TestSet(CollisionHash2, 50); | 178 TestSet(CollisionHash2, 50); |
169 TestSet(CollisionHash3, 50); | 179 TestSet(CollisionHash3, 50); |
170 TestSet(CollisionHash4, 50); | 180 TestSet(CollisionHash4, 50); |
171 } | 181 } |
172 | 182 |
173 } // namespace dart | 183 } // namespace dart |
OLD | NEW |