| 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 |