OLD | NEW |
1 // Copyright (c) 2014, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2014, 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 <algorithm> | 5 #include <algorithm> |
6 #include <cstring> | 6 #include <cstring> |
7 #include <map> | 7 #include <map> |
8 #include <set> | 8 #include <set> |
9 #include <string> | 9 #include <string> |
10 #include <utility> | 10 #include <utility> |
(...skipping 42 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
53 num_deleted -= table.IsDeleted(i); | 53 num_deleted -= table.IsDeleted(i); |
54 } | 54 } |
55 EXPECT_EQ(0, num_unused); | 55 EXPECT_EQ(0, num_unused); |
56 EXPECT_EQ(0, num_occupied); | 56 EXPECT_EQ(0, num_occupied); |
57 EXPECT_EQ(0, num_deleted); | 57 EXPECT_EQ(0, num_deleted); |
58 } | 58 } |
59 | 59 |
60 | 60 |
61 TEST_CASE(HashTable) { | 61 TEST_CASE(HashTable) { |
62 typedef HashTable<TestTraits, 2, 1> Table; | 62 typedef HashTable<TestTraits, 2, 1> Table; |
63 Table table(Array::Handle(HashTables::New<Table>(5))); | 63 Table table(HashTables::New<Table>(5)); |
64 // Ensure that we did get at least 5 entries. | 64 // Ensure that we did get at least 5 entries. |
65 EXPECT_LE(5, table.NumEntries()); | 65 EXPECT_LE(5, table.NumEntries()); |
66 EXPECT_EQ(0, table.NumOccupied()); | 66 EXPECT_EQ(0, table.NumOccupied()); |
67 Validate(table); | 67 Validate(table); |
68 EXPECT_EQ(-1, table.FindKey("a")); | 68 EXPECT_EQ(-1, table.FindKey("a")); |
69 | 69 |
70 // Insertion and lookup. | 70 // Insertion and lookup. |
71 intptr_t a_entry = -1; | 71 intptr_t a_entry = -1; |
72 EXPECT(!table.FindKeyOrDeletedOrUnused("a", &a_entry)); | 72 EXPECT(!table.FindKeyOrDeletedOrUnused("a", &a_entry)); |
73 EXPECT_NE(-1, a_entry); | 73 EXPECT_NE(-1, a_entry); |
(...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
114 k = String::New("f"); | 114 k = String::New("f"); |
115 table.InsertKey(entry, k); | 115 table.InsertKey(entry, k); |
116 EXPECT_EQ(5, table.NumOccupied()); | 116 EXPECT_EQ(5, table.NumOccupied()); |
117 } | 117 } |
118 table.Release(); | 118 table.Release(); |
119 } | 119 } |
120 | 120 |
121 | 121 |
122 TEST_CASE(EnumIndexHashMap) { | 122 TEST_CASE(EnumIndexHashMap) { |
123 typedef EnumIndexHashMap<TestTraits> Table; | 123 typedef EnumIndexHashMap<TestTraits> Table; |
124 Table table(Array::Handle(HashTables::New<Table>(5))); | 124 Table table(HashTables::New<Table>(5)); |
125 table.UpdateOrInsert(String::Handle(String::New("a")), | 125 table.UpdateOrInsert(String::Handle(String::New("a")), |
126 String::Handle(String::New("A"))); | 126 String::Handle(String::New("A"))); |
127 EXPECT(table.ContainsKey("a")); | 127 EXPECT(table.ContainsKey("a")); |
128 table.UpdateValue("a", String::Handle(String::New("AAA"))); | 128 table.UpdateValue("a", String::Handle(String::New("AAA"))); |
129 String& a_value = String::Handle(); | 129 String& a_value = String::Handle(); |
130 a_value ^= table.GetOrNull("a"); | 130 a_value ^= table.GetOrNull("a"); |
131 EXPECT(a_value.Equals("AAA")); | 131 EXPECT(a_value.Equals("AAA")); |
132 Object& null_value = Object::Handle(table.GetOrNull("0")); | 132 Object& null_value = Object::Handle(table.GetOrNull("0")); |
133 EXPECT(null_value.IsNull()); | 133 EXPECT(null_value.IsNull()); |
134 | 134 |
(...skipping 86 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
221 value ^= entries.At(2 * i + 1); | 221 value ^= entries.At(2 * i + 1); |
222 EXPECT(expected_vec[i].first == ToStdString(key)); | 222 EXPECT(expected_vec[i].first == ToStdString(key)); |
223 EXPECT_EQ(expected_vec[i].second, value.Value()); | 223 EXPECT_EQ(expected_vec[i].second, value.Value()); |
224 } | 224 } |
225 } | 225 } |
226 | 226 |
227 | 227 |
228 template<typename Set> | 228 template<typename Set> |
229 void TestSet(intptr_t initial_capacity, bool ordered) { | 229 void TestSet(intptr_t initial_capacity, bool ordered) { |
230 std::set<std::string> expected; | 230 std::set<std::string> expected; |
231 Set actual(Array::Handle(HashTables::New<Set>(initial_capacity))); | 231 Set actual(HashTables::New<Set>(initial_capacity)); |
232 // Insert the following strings twice: | 232 // Insert the following strings twice: |
233 // aaa...aaa (length 26) | 233 // aaa...aaa (length 26) |
234 // bbb..bbb | 234 // bbb..bbb |
235 // ... | 235 // ... |
236 // yy | 236 // yy |
237 // z | 237 // z |
238 for (int i = 0; i < 2; ++i) { | 238 for (int i = 0; i < 2; ++i) { |
239 for (char ch = 'a'; ch <= 'z'; ++ch) { | 239 for (char ch = 'a'; ch <= 'z'; ++ch) { |
240 std::string key('z' - ch + 1, ch); | 240 std::string key('z' - ch + 1, ch); |
241 expected.insert(key); | 241 expected.insert(key); |
242 bool present = actual.Insert(String::Handle(String::New(key.c_str()))); | 242 bool present = actual.Insert(String::Handle(String::New(key.c_str()))); |
243 EXPECT_EQ((i != 0), present); | 243 EXPECT_EQ((i != 0), present); |
244 Validate(actual); | 244 Validate(actual); |
245 VerifyStringSetsEqual(expected, actual, ordered); | 245 VerifyStringSetsEqual(expected, actual, ordered); |
246 } | 246 } |
247 } | 247 } |
248 // TODO(koda): Delete all entries. | 248 // TODO(koda): Delete all entries. |
249 actual.Release(); | 249 actual.Release(); |
250 } | 250 } |
251 | 251 |
252 | 252 |
253 template<typename Map> | 253 template<typename Map> |
254 void TestMap(intptr_t initial_capacity, bool ordered) { | 254 void TestMap(intptr_t initial_capacity, bool ordered) { |
255 std::map<std::string, int> expected; | 255 std::map<std::string, int> expected; |
256 Map actual(Array::Handle(HashTables::New<Map>(initial_capacity))); | 256 Map actual(HashTables::New<Map>(initial_capacity)); |
257 // Insert the following (strings, int) mapping: | 257 // Insert the following (strings, int) mapping: |
258 // aaa...aaa -> 26 | 258 // aaa...aaa -> 26 |
259 // bbb..bbb -> 25 | 259 // bbb..bbb -> 25 |
260 // ... | 260 // ... |
261 // yy -> 2 | 261 // yy -> 2 |
262 // z -> 1 | 262 // z -> 1 |
263 for (int i = 0; i < 2; ++i) { | 263 for (int i = 0; i < 2; ++i) { |
264 for (char ch = 'a'; ch <= 'z'; ++ch) { | 264 for (char ch = 'a'; ch <= 'z'; ++ch) { |
265 int length = 'z' - ch + 1; | 265 int length = 'z' - ch + 1; |
266 std::string key(length, ch); | 266 std::string key(length, ch); |
(...skipping 26 matching lines...) Expand all Loading... |
293 TEST_CASE(Maps) { | 293 TEST_CASE(Maps) { |
294 for (intptr_t initial_capacity = 0; | 294 for (intptr_t initial_capacity = 0; |
295 initial_capacity < 32; | 295 initial_capacity < 32; |
296 ++initial_capacity) { | 296 ++initial_capacity) { |
297 TestMap<UnorderedHashMap<TestTraits> >(initial_capacity, false); | 297 TestMap<UnorderedHashMap<TestTraits> >(initial_capacity, false); |
298 TestMap<EnumIndexHashMap<TestTraits> >(initial_capacity, true); | 298 TestMap<EnumIndexHashMap<TestTraits> >(initial_capacity, true); |
299 } | 299 } |
300 } | 300 } |
301 | 301 |
302 } // namespace dart | 302 } // namespace dart |
OLD | NEW |