bloom_filter_unittest.cc 3.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
  1. // Copyright 2018 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/optimization_guide/core/bloom_filter.h"
  5. #include <stdint.h>
  6. #include <string>
  7. #include "build/build_config.h"
  8. #include "testing/gtest/include/gtest/gtest.h"
  9. namespace optimization_guide {
  10. namespace {
  11. int CountBits(const ByteVector& vector) {
  12. int bit_count = 0;
  13. for (size_t i = 0; i < vector.size(); ++i) {
  14. uint8_t byte = vector[i];
  15. for (int j = 0; j < 8; ++j) {
  16. if (byte & (1 << j))
  17. bit_count++;
  18. }
  19. }
  20. return bit_count;
  21. }
  22. } // namespace
  23. TEST(BloomFilterTest, SingleHash) {
  24. BloomFilter filter(1 /* num_hash_functions */, 16 /* num_bits */);
  25. EXPECT_EQ(2u, filter.bytes().size());
  26. EXPECT_EQ(0, CountBits(filter.bytes()));
  27. EXPECT_FALSE(filter.Contains("Alfa"));
  28. EXPECT_FALSE(filter.Contains("Bravo"));
  29. EXPECT_FALSE(filter.Contains("Charlie"));
  30. filter.Add("Alfa");
  31. EXPECT_EQ(1, CountBits(filter.bytes()));
  32. EXPECT_TRUE(filter.Contains("Alfa"));
  33. EXPECT_FALSE(filter.Contains("Bravo"));
  34. EXPECT_FALSE(filter.Contains("Charlie"));
  35. filter.Add("Bravo");
  36. filter.Add("Chuck");
  37. EXPECT_EQ(3, CountBits(filter.bytes()));
  38. EXPECT_TRUE(filter.Contains("Alfa"));
  39. EXPECT_TRUE(filter.Contains("Bravo"));
  40. EXPECT_FALSE(filter.Contains("Charlie"));
  41. }
  42. TEST(BloomFilterTest, FalsePositivesWithSingleBitFilterCollisions) {
  43. BloomFilter filter(1 /* num_hash_functions */, 1 /* num_bits */);
  44. EXPECT_EQ(1u, filter.bytes().size());
  45. EXPECT_FALSE(filter.Contains("Alfa"));
  46. EXPECT_FALSE(filter.Contains("Bravo"));
  47. EXPECT_FALSE(filter.Contains("Charlie"));
  48. filter.Add("Alfa");
  49. EXPECT_TRUE(filter.Contains("Alfa"));
  50. EXPECT_TRUE(filter.Contains("Bravo"));
  51. EXPECT_TRUE(filter.Contains("Charlie"));
  52. }
  53. TEST(BloomFilterTest, MultiHash) {
  54. // Provide zero-ed filter data.
  55. std::string data(10, 0);
  56. BloomFilter filter(3 /* num_hash_functions */, 75 /* num_bits */, data);
  57. EXPECT_EQ(10u, filter.bytes().size());
  58. EXPECT_EQ(0, CountBits(filter.bytes()));
  59. EXPECT_FALSE(filter.Contains("Alfa"));
  60. EXPECT_FALSE(filter.Contains("Bravo"));
  61. EXPECT_FALSE(filter.Contains("Charlie"));
  62. filter.Add("Alfa");
  63. EXPECT_EQ(3, CountBits(filter.bytes()));
  64. EXPECT_TRUE(filter.Contains("Alfa"));
  65. EXPECT_FALSE(filter.Contains("Bravo"));
  66. EXPECT_FALSE(filter.Contains("Charlie"));
  67. filter.Add("Bravo");
  68. filter.Add("Chuck");
  69. EXPECT_EQ(9, CountBits(filter.bytes()));
  70. EXPECT_TRUE(filter.Contains("Alfa"));
  71. EXPECT_TRUE(filter.Contains("Bravo"));
  72. EXPECT_FALSE(filter.Contains("Charlie"));
  73. }
  74. TEST(BloomFilterTest, EverythingMatches) {
  75. // Provide filter data with all bits set ON.
  76. std::string data(1024, 0xff);
  77. BloomFilter filter(7 /* num_hash_functions */, 8191 /* num_bits */, data);
  78. EXPECT_TRUE(filter.Contains("Alfa"));
  79. EXPECT_TRUE(filter.Contains("Bravo"));
  80. EXPECT_TRUE(filter.Contains("Charlie"));
  81. EXPECT_TRUE(filter.Contains("Delta"));
  82. EXPECT_TRUE(filter.Contains("Echo"));
  83. }
  84. // Disable this test in configurations that don't print CHECK failures.
  85. #if !BUILDFLAG(IS_IOS) && !(defined(OFFICIAL_BUILD) && defined(NDEBUG))
  86. TEST(BloomFilterTest, ByteVectorTooSmall) {
  87. std::string data(1023, 0xff);
  88. EXPECT_DEATH(
  89. {
  90. BloomFilter filter(7 /* num_hash_functions */, 8191 /* num_bits */,
  91. data);
  92. },
  93. "Check failed");
  94. }
  95. #endif
  96. } // namespace optimization_guide