OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2011 Google Inc. All rights reserved. | 2 * Copyright (C) 2011 Google Inc. All rights reserved. |
3 * | 3 * |
4 * Redistribution and use in source and binary forms, with or without | 4 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 5 * modification, are permitted provided that the following conditions |
6 * are met: | 6 * are met: |
7 * 1. Redistributions of source code must retain the above copyright | 7 * 1. Redistributions of source code must retain the above copyright |
8 * notice, this list of conditions and the following disclaimer. | 8 * notice, this list of conditions and the following disclaimer. |
9 * 2. Redistributions in binary form must reproduce the above copyright | 9 * 2. Redistributions in binary form must reproduce the above copyright |
10 * notice, this list of conditions and the following disclaimer in the | 10 * notice, this list of conditions and the following disclaimer in the |
(...skipping 50 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
61 | 61 |
62 using DoubleHashMap = | 62 using DoubleHashMap = |
63 HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits>; | 63 HashMap<double, int64_t, DefaultHash<double>::Hash, TestDoubleHashTraits>; |
64 | 64 |
65 int bucketForKey(double key) { | 65 int bucketForKey(double key) { |
66 return DefaultHash<double>::Hash::hash(key) & | 66 return DefaultHash<double>::Hash::hash(key) & |
67 (TestDoubleHashTraits::minimumTableSize - 1); | 67 (TestDoubleHashTraits::minimumTableSize - 1); |
68 } | 68 } |
69 | 69 |
70 TEST(HashMapTest, DoubleHashCollisions) { | 70 TEST(HashMapTest, DoubleHashCollisions) { |
71 // The "clobber" key here is one that ends up stealing the bucket that the -0
key | 71 // The "clobber" key here is one that ends up stealing the bucket that the -0 |
72 // originally wants to be in. This makes the 0 and -0 keys collide and the tes
t then | 72 // key originally wants to be in. This makes the 0 and -0 keys collide and |
73 // fails unless the FloatHash::equals() implementation can distinguish them. | 73 // the test then fails unless the FloatHash::equals() implementation can |
| 74 // distinguish them. |
74 const double clobberKey = 6; | 75 const double clobberKey = 6; |
75 const double zeroKey = 0; | 76 const double zeroKey = 0; |
76 const double negativeZeroKey = -zeroKey; | 77 const double negativeZeroKey = -zeroKey; |
77 | 78 |
78 DoubleHashMap map; | 79 DoubleHashMap map; |
79 | 80 |
80 map.add(clobberKey, 1); | 81 map.add(clobberKey, 1); |
81 map.add(zeroKey, 2); | 82 map.add(zeroKey, 2); |
82 map.add(negativeZeroKey, 3); | 83 map.add(negativeZeroKey, 3); |
83 | 84 |
(...skipping 203 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
287 TEST(HashMapTest, ValueTypeDestructed) { | 288 TEST(HashMapTest, ValueTypeDestructed) { |
288 InstanceCounter::counter = 0; | 289 InstanceCounter::counter = 0; |
289 HashMap<int, InstanceCounter> map; | 290 HashMap<int, InstanceCounter> map; |
290 map.set(1, InstanceCounter()); | 291 map.set(1, InstanceCounter()); |
291 map.clear(); | 292 map.clear(); |
292 EXPECT_EQ(0, InstanceCounter::counter); | 293 EXPECT_EQ(0, InstanceCounter::counter); |
293 } | 294 } |
294 | 295 |
295 class MoveOnly { | 296 class MoveOnly { |
296 public: | 297 public: |
297 // kEmpty and kDeleted have special meanings when MoveOnly is used as the key
of a hash table. | 298 // kEmpty and kDeleted have special meanings when MoveOnly is used as the key |
| 299 // of a hash table. |
298 enum { kEmpty = 0, kDeleted = -1, kMovedOut = -2 }; | 300 enum { kEmpty = 0, kDeleted = -1, kMovedOut = -2 }; |
299 | 301 |
300 explicit MoveOnly(int value = kEmpty) : m_value(value) {} | 302 explicit MoveOnly(int value = kEmpty) : m_value(value) {} |
301 MoveOnly(MoveOnly&& other) : m_value(other.m_value) { | 303 MoveOnly(MoveOnly&& other) : m_value(other.m_value) { |
302 other.m_value = kMovedOut; | 304 other.m_value = kMovedOut; |
303 } | 305 } |
304 MoveOnly& operator=(MoveOnly&& other) { | 306 MoveOnly& operator=(MoveOnly&& other) { |
305 m_value = other.m_value; | 307 m_value = other.m_value; |
306 other.m_value = kMovedOut; | 308 other.m_value = kMovedOut; |
307 return *this; | 309 return *this; |
308 } | 310 } |
309 | 311 |
310 int value() const { return m_value; } | 312 int value() const { return m_value; } |
311 | 313 |
312 private: | 314 private: |
313 MoveOnly(const MoveOnly&) = delete; | 315 MoveOnly(const MoveOnly&) = delete; |
314 MoveOnly& operator=(const MoveOnly&) = delete; | 316 MoveOnly& operator=(const MoveOnly&) = delete; |
315 | 317 |
316 int m_value; | 318 int m_value; |
317 }; | 319 }; |
318 | 320 |
319 struct MoveOnlyHashTraits : public GenericHashTraits<MoveOnly> { | 321 struct MoveOnlyHashTraits : public GenericHashTraits<MoveOnly> { |
320 // This is actually true, but we pretend that it's false to disable the optimi
zation. | 322 // This is actually true, but we pretend that it's false to disable the |
| 323 // optimization. |
321 static const bool emptyValueIsZero = false; | 324 static const bool emptyValueIsZero = false; |
322 | 325 |
323 static const bool hasIsEmptyValueFunction = true; | 326 static const bool hasIsEmptyValueFunction = true; |
324 static bool isEmptyValue(const MoveOnly& value) { | 327 static bool isEmptyValue(const MoveOnly& value) { |
325 return value.value() == MoveOnly::kEmpty; | 328 return value.value() == MoveOnly::kEmpty; |
326 } | 329 } |
327 static void constructDeletedValue(MoveOnly& slot, bool) { | 330 static void constructDeletedValue(MoveOnly& slot, bool) { |
328 slot = MoveOnly(MoveOnly::kDeleted); | 331 slot = MoveOnly(MoveOnly::kDeleted); |
329 } | 332 } |
330 static bool isDeletedValue(const MoveOnly& value) { | 333 static bool isDeletedValue(const MoveOnly& value) { |
(...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
402 | 405 |
403 MoveOnly oneThirty(map.take(13)); | 406 MoveOnly oneThirty(map.take(13)); |
404 EXPECT_EQ(130, oneThirty.value()); | 407 EXPECT_EQ(130, oneThirty.value()); |
405 iter = map.find(13); | 408 iter = map.find(13); |
406 EXPECT_TRUE(iter == map.end()); | 409 EXPECT_TRUE(iter == map.end()); |
407 | 410 |
408 map.clear(); | 411 map.clear(); |
409 } | 412 } |
410 | 413 |
411 TEST(HashMapTest, MoveOnlyKeyType) { | 414 TEST(HashMapTest, MoveOnlyKeyType) { |
412 // The content of this test is similar to the test above, except that the type
s of key and value are swapped. | 415 // The content of this test is similar to the test above, except that the |
| 416 // types of key and value are swapped. |
413 using TheMap = HashMap<MoveOnly, int>; | 417 using TheMap = HashMap<MoveOnly, int>; |
414 TheMap map; | 418 TheMap map; |
415 { | 419 { |
416 TheMap::AddResult addResult = map.add(MoveOnly(1), 10); | 420 TheMap::AddResult addResult = map.add(MoveOnly(1), 10); |
417 EXPECT_TRUE(addResult.isNewEntry); | 421 EXPECT_TRUE(addResult.isNewEntry); |
418 EXPECT_EQ(1, addResult.storedValue->key.value()); | 422 EXPECT_EQ(1, addResult.storedValue->key.value()); |
419 EXPECT_EQ(10, addResult.storedValue->value); | 423 EXPECT_EQ(10, addResult.storedValue->value); |
420 } | 424 } |
421 auto iter = map.find(MoveOnly(1)); | 425 auto iter = map.find(MoveOnly(1)); |
422 ASSERT_TRUE(iter != map.end()); | 426 ASSERT_TRUE(iter != map.end()); |
(...skipping 222 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
645 EXPECT_EQ(130, oneThirty); | 649 EXPECT_EQ(130, oneThirty); |
646 iter = map.find(Pair(MoveOnly(13), -13)); | 650 iter = map.find(Pair(MoveOnly(13), -13)); |
647 EXPECT_TRUE(iter == map.end()); | 651 EXPECT_TRUE(iter == map.end()); |
648 | 652 |
649 map.clear(); | 653 map.clear(); |
650 } | 654 } |
651 | 655 |
652 } // anonymous namespace | 656 } // anonymous namespace |
653 | 657 |
654 } // namespace WTF | 658 } // namespace WTF |
OLD | NEW |