closed_hash_map_unittest.cc 4.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166
  1. // Copyright 2016 The Chromium Authors. All rights reserved.
  2. // Use of this source code is governed by a BSD-style license that can be
  3. // found in the LICENSE file.
  4. #include "components/url_pattern_index/closed_hash_map.h"
  5. #include <string>
  6. #include <vector>
  7. #include "components/url_pattern_index/uint64_hasher.h"
  8. #include "testing/gtest/include/gtest/gtest.h"
  9. namespace url_pattern_index {
  10. namespace {
  11. template <typename MapType>
  12. void ExpectHashMapIntegrity(const MapType& map, uint32_t min_capacity = 0) {
  13. EXPECT_EQ(map.entries().size(), map.size());
  14. EXPECT_EQ(map.hash_table().size(), map.table_size());
  15. EXPECT_LE(map.size() * 2, map.table_size());
  16. EXPECT_LE(min_capacity * 2, map.table_size());
  17. std::vector<bool> entry_is_referenced(map.size());
  18. for (uint32_t i = 0; i < map.table_size(); ++i) {
  19. SCOPED_TRACE(testing::Message() << "Hash-table slot: " << i);
  20. const uint32_t entry_index = map.hash_table()[i];
  21. if (static_cast<uint32_t>(entry_index) >= map.size())
  22. continue;
  23. EXPECT_FALSE(entry_is_referenced[entry_index]);
  24. entry_is_referenced[entry_index] = true;
  25. }
  26. for (uint32_t i = 0; i < map.size(); ++i) {
  27. SCOPED_TRACE(testing::Message() << "Hash-table entry index: " << i);
  28. EXPECT_TRUE(entry_is_referenced[i]);
  29. }
  30. }
  31. template <typename MapType>
  32. void ExpectEmptyMap(const MapType& map, uint32_t min_capacity) {
  33. ExpectHashMapIntegrity(map, min_capacity);
  34. EXPECT_EQ(0u, map.size());
  35. }
  36. } // namespace
  37. TEST(ClosedHashMapTest, EmptyMapDefault) {
  38. HashMap<int, int> hm;
  39. ExpectEmptyMap(hm, 0);
  40. EXPECT_EQ(nullptr, hm.Get(0));
  41. EXPECT_EQ(nullptr, hm.Get(100500));
  42. EXPECT_GT(hm.table_size(), 0u);
  43. }
  44. TEST(ClosedHashMapTest, EmptyMapWithCapacity) {
  45. HashMap<int, int> hm(100);
  46. ExpectEmptyMap(hm, 100);
  47. EXPECT_EQ(nullptr, hm.Get(0));
  48. EXPECT_EQ(nullptr, hm.Get(100500));
  49. }
  50. TEST(ClosedHashMapTest, InsertDistinctAndGet) {
  51. HashMap<int, int> hm;
  52. static const int kKeys[] = {1, 5, 10, 3, -100500};
  53. for (int key : kKeys) {
  54. EXPECT_TRUE(hm.Insert(key, -key));
  55. ExpectHashMapIntegrity(hm);
  56. }
  57. for (int key : kKeys) {
  58. const int* value = hm.Get(key);
  59. ASSERT_NE(nullptr, value);
  60. EXPECT_EQ(-key, *value);
  61. }
  62. EXPECT_EQ(nullptr, hm.Get(1234567));
  63. }
  64. TEST(ClosedHashMapTest, InsertExistingAndGet) {
  65. HashMap<int, int> hm;
  66. EXPECT_TRUE(hm.Insert(123, -123));
  67. EXPECT_FALSE(hm.Insert(123, -124));
  68. ExpectHashMapIntegrity(hm);
  69. const int* value = hm.Get(123);
  70. ASSERT_NE(nullptr, value);
  71. EXPECT_EQ(-123, *value);
  72. }
  73. TEST(ClosedHashMapTest, InsertManyKeysWithCustomHasher) {
  74. using CustomProber = SimpleQuadraticProber<uint64_t, Uint64ToUint32Hasher>;
  75. ClosedHashMap<uint64_t, std::string, CustomProber> hm;
  76. ExpectEmptyMap(hm, 0);
  77. std::vector<std::pair<uint64_t, std::string>> entries;
  78. for (int key = 10, i = 0; key < 1000000; key += ++i) {
  79. entries.push_back(std::make_pair(key, std::to_string(key)));
  80. }
  81. uint32_t expected_size = 0;
  82. for (const auto& entry : entries) {
  83. EXPECT_TRUE(hm.Insert(entry.first, entry.second));
  84. EXPECT_FALSE(hm.Insert(entry.first, "-1"));
  85. ++expected_size;
  86. EXPECT_EQ(expected_size, hm.size());
  87. EXPECT_LE(expected_size * 2, hm.table_size());
  88. }
  89. ExpectHashMapIntegrity(hm);
  90. for (const auto& entry : entries) {
  91. const std::string* value = hm.Get(entry.first);
  92. ASSERT_NE(nullptr, value);
  93. EXPECT_EQ(entry.second, *value);
  94. }
  95. }
  96. TEST(ClosedHashMapTest, OperatorBrackets) {
  97. HashMap<int, int> hm;
  98. for (int i = 0; i < 5; ++i) {
  99. const uint32_t expected_size = i ? 1 : 0;
  100. EXPECT_EQ(expected_size, hm.size());
  101. int expected_value = (i + 1) * 10;
  102. hm[123] = expected_value;
  103. EXPECT_EQ(1u, hm.size());
  104. const int* value_ptr = hm.Get(123);
  105. ASSERT_NE(nullptr, value_ptr);
  106. EXPECT_EQ(expected_value, *value_ptr);
  107. EXPECT_EQ(expected_value, hm[123]);
  108. EXPECT_EQ(1u, hm.size());
  109. expected_value *= 100;
  110. hm[123] = expected_value;
  111. EXPECT_EQ(expected_value, hm[123]);
  112. }
  113. }
  114. TEST(ClosedHashMapTest, ManualRehash) {
  115. HashMap<int, int> hm(3);
  116. const uint32_t expected_table_size = hm.table_size();
  117. static const int kKeys[] = {1, 5, 10};
  118. for (int key : kKeys) {
  119. EXPECT_TRUE(hm.Insert(key, -key));
  120. }
  121. // No rehashing occurred.
  122. EXPECT_EQ(expected_table_size, hm.table_size());
  123. for (int i = 1; i <= 2; ++i) {
  124. for (int key : kKeys) {
  125. const int* value = hm.Get(key);
  126. ASSERT_NE(nullptr, value);
  127. EXPECT_EQ(-key, *value);
  128. }
  129. hm.Rehash(100 * i);
  130. ExpectHashMapIntegrity(hm, 100 * i);
  131. }
  132. }
  133. } // namespace url_pattern_index