| 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 "vm/hash_map.h" |
| 5 #include "platform/assert.h" | 6 #include "platform/assert.h" |
| 6 #include "vm/unit_test.h" | 7 #include "vm/unit_test.h" |
| 7 #include "vm/hash_map.h" | |
| 8 | 8 |
| 9 namespace dart { | 9 namespace dart { |
| 10 | 10 |
| 11 class TestValue { | 11 class TestValue { |
| 12 public: | 12 public: |
| 13 explicit TestValue(intptr_t x) : x_(x) {} | 13 explicit TestValue(intptr_t x) : x_(x) {} |
| 14 intptr_t Hashcode() const { return x_ & 1; } | 14 intptr_t Hashcode() const { return x_ & 1; } |
| 15 bool Equals(TestValue* other) { return x_ == other->x_; } | 15 bool Equals(TestValue* other) { return x_ == other->x_; } |
| 16 | 16 |
| 17 private: | 17 private: |
| 18 intptr_t x_; | 18 intptr_t x_; |
| 19 }; | 19 }; |
| 20 | 20 |
| 21 | |
| 22 TEST_CASE(DirectChainedHashMap) { | 21 TEST_CASE(DirectChainedHashMap) { |
| 23 DirectChainedHashMap<PointerKeyValueTrait<TestValue> > map; | 22 DirectChainedHashMap<PointerKeyValueTrait<TestValue> > map; |
| 24 EXPECT(map.IsEmpty()); | 23 EXPECT(map.IsEmpty()); |
| 25 TestValue v1(0); | 24 TestValue v1(0); |
| 26 TestValue v2(1); | 25 TestValue v2(1); |
| 27 TestValue v3(0); | 26 TestValue v3(0); |
| 28 map.Insert(&v1); | 27 map.Insert(&v1); |
| 29 EXPECT(map.LookupValue(&v1) == &v1); | 28 EXPECT(map.LookupValue(&v1) == &v1); |
| 30 map.Insert(&v2); | 29 map.Insert(&v2); |
| 31 EXPECT(map.LookupValue(&v1) == &v1); | 30 EXPECT(map.LookupValue(&v1) == &v1); |
| 32 EXPECT(map.LookupValue(&v2) == &v2); | 31 EXPECT(map.LookupValue(&v2) == &v2); |
| 33 EXPECT(map.LookupValue(&v3) == &v1); | 32 EXPECT(map.LookupValue(&v3) == &v1); |
| 34 EXPECT(map.Remove(&v1)); | 33 EXPECT(map.Remove(&v1)); |
| 35 EXPECT(map.Lookup(&v1) == NULL); | 34 EXPECT(map.Lookup(&v1) == NULL); |
| 36 map.Insert(&v1); | 35 map.Insert(&v1); |
| 37 DirectChainedHashMap<PointerKeyValueTrait<TestValue> > map2(map); | 36 DirectChainedHashMap<PointerKeyValueTrait<TestValue> > map2(map); |
| 38 EXPECT(map2.LookupValue(&v1) == &v1); | 37 EXPECT(map2.LookupValue(&v1) == &v1); |
| 39 EXPECT(map2.LookupValue(&v2) == &v2); | 38 EXPECT(map2.LookupValue(&v2) == &v2); |
| 40 EXPECT(map2.LookupValue(&v3) == &v1); | 39 EXPECT(map2.LookupValue(&v3) == &v1); |
| 41 } | 40 } |
| 42 | 41 |
| 43 | |
| 44 TEST_CASE(DirectChainedHashMapInsertRemove) { | 42 TEST_CASE(DirectChainedHashMapInsertRemove) { |
| 45 DirectChainedHashMap<PointerKeyValueTrait<TestValue> > map; | 43 DirectChainedHashMap<PointerKeyValueTrait<TestValue> > map; |
| 46 EXPECT(map.IsEmpty()); | 44 EXPECT(map.IsEmpty()); |
| 47 TestValue v1(1); | 45 TestValue v1(1); |
| 48 TestValue v2(3); // Note: v1, v2, v3 should have the same hash. | 46 TestValue v2(3); // Note: v1, v2, v3 should have the same hash. |
| 49 TestValue v3(5); | 47 TestValue v3(5); |
| 50 | 48 |
| 51 // Start with adding and removing the same element. | 49 // Start with adding and removing the same element. |
| 52 map.Insert(&v1); | 50 map.Insert(&v1); |
| 53 EXPECT(map.LookupValue(&v1) == &v1); | 51 EXPECT(map.LookupValue(&v1) == &v1); |
| (...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 91 EXPECT(map.LookupValue(&v1) == &v1); | 89 EXPECT(map.LookupValue(&v1) == &v1); |
| 92 EXPECT(map.Lookup(&v2) == NULL); | 90 EXPECT(map.Lookup(&v2) == NULL); |
| 93 EXPECT(map.LookupValue(&v3) == &v3); | 91 EXPECT(map.LookupValue(&v3) == &v3); |
| 94 | 92 |
| 95 EXPECT(map.Remove(&v1)); | 93 EXPECT(map.Remove(&v1)); |
| 96 EXPECT(map.Remove(&v3)); | 94 EXPECT(map.Remove(&v3)); |
| 97 | 95 |
| 98 EXPECT(map.IsEmpty()); | 96 EXPECT(map.IsEmpty()); |
| 99 } | 97 } |
| 100 | 98 |
| 101 | |
| 102 TEST_CASE(MallocDirectChainedHashMap) { | 99 TEST_CASE(MallocDirectChainedHashMap) { |
| 103 MallocDirectChainedHashMap<PointerKeyValueTrait<TestValue> > map; | 100 MallocDirectChainedHashMap<PointerKeyValueTrait<TestValue> > map; |
| 104 EXPECT(map.IsEmpty()); | 101 EXPECT(map.IsEmpty()); |
| 105 TestValue v1(0); | 102 TestValue v1(0); |
| 106 TestValue v2(1); | 103 TestValue v2(1); |
| 107 TestValue v3(0); | 104 TestValue v3(0); |
| 108 map.Insert(&v1); | 105 map.Insert(&v1); |
| 109 EXPECT(map.LookupValue(&v1) == &v1); | 106 EXPECT(map.LookupValue(&v1) == &v1); |
| 110 map.Insert(&v2); | 107 map.Insert(&v2); |
| 111 EXPECT(map.LookupValue(&v1) == &v1); | 108 EXPECT(map.LookupValue(&v1) == &v1); |
| 112 EXPECT(map.LookupValue(&v2) == &v2); | 109 EXPECT(map.LookupValue(&v2) == &v2); |
| 113 EXPECT(map.LookupValue(&v3) == &v1); | 110 EXPECT(map.LookupValue(&v3) == &v1); |
| 114 MallocDirectChainedHashMap<PointerKeyValueTrait<TestValue> > map2(map); | 111 MallocDirectChainedHashMap<PointerKeyValueTrait<TestValue> > map2(map); |
| 115 EXPECT(map2.LookupValue(&v1) == &v1); | 112 EXPECT(map2.LookupValue(&v1) == &v1); |
| 116 EXPECT(map2.LookupValue(&v2) == &v2); | 113 EXPECT(map2.LookupValue(&v2) == &v2); |
| 117 EXPECT(map2.LookupValue(&v3) == &v1); | 114 EXPECT(map2.LookupValue(&v3) == &v1); |
| 118 } | 115 } |
| 119 | 116 |
| 120 | |
| 121 class IntptrPair { | 117 class IntptrPair { |
| 122 public: | 118 public: |
| 123 IntptrPair() : first_(-1), second_(-1) {} | 119 IntptrPair() : first_(-1), second_(-1) {} |
| 124 IntptrPair(intptr_t first, intptr_t second) | 120 IntptrPair(intptr_t first, intptr_t second) |
| 125 : first_(first), second_(second) {} | 121 : first_(first), second_(second) {} |
| 126 | 122 |
| 127 intptr_t first() const { return first_; } | 123 intptr_t first() const { return first_; } |
| 128 intptr_t second() const { return second_; } | 124 intptr_t second() const { return second_; } |
| 129 | 125 |
| 130 bool operator==(const IntptrPair& other) { | 126 bool operator==(const IntptrPair& other) { |
| 131 return (first_ == other.first_) && (second_ == other.second_); | 127 return (first_ == other.first_) && (second_ == other.second_); |
| 132 } | 128 } |
| 133 | 129 |
| 134 bool operator!=(const IntptrPair& other) { | 130 bool operator!=(const IntptrPair& other) { |
| 135 return (first_ != other.first_) || (second_ != other.second_); | 131 return (first_ != other.first_) || (second_ != other.second_); |
| 136 } | 132 } |
| 137 | 133 |
| 138 private: | 134 private: |
| 139 intptr_t first_; | 135 intptr_t first_; |
| 140 intptr_t second_; | 136 intptr_t second_; |
| 141 }; | 137 }; |
| 142 | 138 |
| 143 | |
| 144 TEST_CASE(DirectChainedHashMapIterator) { | 139 TEST_CASE(DirectChainedHashMapIterator) { |
| 145 IntptrPair p1(1, 1); | 140 IntptrPair p1(1, 1); |
| 146 IntptrPair p2(2, 2); | 141 IntptrPair p2(2, 2); |
| 147 IntptrPair p3(3, 3); | 142 IntptrPair p3(3, 3); |
| 148 IntptrPair p4(4, 4); | 143 IntptrPair p4(4, 4); |
| 149 IntptrPair p5(5, 5); | 144 IntptrPair p5(5, 5); |
| 150 DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair> > map; | 145 DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair> > map; |
| 151 EXPECT(map.IsEmpty()); | 146 EXPECT(map.IsEmpty()); |
| 152 DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair> >::Iterator it = | 147 DirectChainedHashMap<NumbersKeyValueTrait<IntptrPair> >::Iterator it = |
| 153 map.GetIterator(); | 148 map.GetIterator(); |
| (...skipping 17 matching lines...) Expand all Loading... |
| 171 } | 166 } |
| 172 count++; | 167 count++; |
| 173 sum += p->second(); | 168 sum += p->second(); |
| 174 } | 169 } |
| 175 | 170 |
| 176 EXPECT(count == 5); | 171 EXPECT(count == 5); |
| 177 EXPECT(sum == 15); | 172 EXPECT(sum == 15); |
| 178 } | 173 } |
| 179 | 174 |
| 180 } // namespace dart | 175 } // namespace dart |
| OLD | NEW |