bloom_filter.h 2.0 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364
  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. #ifndef COMPONENTS_OPTIMIZATION_GUIDE_CORE_BLOOM_FILTER_H_
  5. #define COMPONENTS_OPTIMIZATION_GUIDE_CORE_BLOOM_FILTER_H_
  6. #include <stdint.h>
  7. #include <string>
  8. #include <vector>
  9. #include "base/sequence_checker.h"
  10. namespace optimization_guide {
  11. // A vector of bytes (or 8-bit integers).
  12. typedef std::vector<uint8_t> ByteVector;
  13. // BloomFilter is a simple Bloom filter for keeping track of a set of strings.
  14. // The implementation is specifically defined to be compatible with data
  15. // and details provided from a server using the OptimizationGuide hints.proto.
  16. class BloomFilter {
  17. public:
  18. // Constructs a Bloom filter of |num_bits| size with zero-ed data and using
  19. //|num_hash_functions| per entry.
  20. BloomFilter(uint32_t num_hash_functions, uint32_t num_bits);
  21. // Constructs a Bloom filter of |num_bits| size with data initialized from
  22. // the |filter_data| string (which is the C++ type for protobuffer |bytes|
  23. // type) and using |num_hash_functions| per entry.
  24. BloomFilter(uint32_t num_hash_functions,
  25. uint32_t num_bits,
  26. std::string filter_data);
  27. BloomFilter(const BloomFilter&) = delete;
  28. BloomFilter& operator=(const BloomFilter&) = delete;
  29. ~BloomFilter();
  30. // Returns whether this Bloom filter contains |str|.
  31. bool Contains(const std::string& str) const;
  32. // Adds |str| to this Bloom filter.
  33. void Add(const std::string& str);
  34. // Returns the bit array data of this Bloom filter as vector of bytes.
  35. const ByteVector& bytes() const { return bytes_; }
  36. private:
  37. // Number of bits to set for each added string.
  38. uint32_t num_hash_functions_;
  39. // Number of bits in the filter.
  40. uint32_t num_bits_;
  41. // Byte data for the filter.
  42. ByteVector bytes_;
  43. SEQUENCE_CHECKER(sequence_checker_);
  44. };
  45. } // namespace optimization_guide
  46. #endif // COMPONENTS_OPTIMIZATION_GUIDE_CORE_BLOOM_FILTER_H_