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 |