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