components/rappor/bloom_filter.h

   1 // Copyright 2014 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
   5 #ifndef COMPONENTS_RAPPOR_BLOOM_FILTER_H_
   6 #define COMPONENTS_RAPPOR_BLOOM_FILTER_H_
   7
   8 #include <string>
   9
  10 #include "base/basictypes.h"
  11 #include "base/macros.h"
  12 #include "components/rappor/byte_vector_utils.h"
  13
  14 namespace rappor {
  15
  16 // BloomFilter is a simple Bloom filter for keeping track of a set of strings.
  17 class BloomFilter {
  18  public:
  19   // Constructs a BloomFilter using |bytes_size| bytes of Bloom filter bits,
  20   // and |hash_function_count| hash functions to set bits in the filter. The
  21   // hash functions will be generated by using seeds in the range
  22   // |hash_seed_offset| to (|hash_seed_offset| + |hash_function_count|).
  23   BloomFilter(uint32_t bytes_size,
  24               uint32_t hash_function_count,
  25               uint32_t hash_seed_offset);
  26   ~BloomFilter();
  27
  28   // Sets the Bloom filter bits to contain a single string.
  29   void SetString(const std::string& str);
  30
  31   // Returns the current value of the Bloom filter's bit array.
  32   const ByteVector& bytes() const { return bytes_; };
  33
  34   // Sets bytes for testing purposes.
  35   void SetBytesForTesting(const ByteVector& bytes);
  36
  37  private:
  38   // Stores the byte array of the Bloom filter.
  39   ByteVector bytes_;
  40
  41   // The number of bits to set for each string added.
  42   uint32_t hash_function_count_;
  43
  44   // A number add to a hash function index to get a seed for that hash function.
  45   uint32_t hash_seed_offset_;
  46
  47   DISALLOW_COPY_AND_ASSIGN(BloomFilter);
  48 };
  49
  50
  51 namespace internal {
  52
  53 // A function for getting bloom filters less than or equal to 64 bits.
  54 uint64_t GetBloomBits(uint32_t bytes_size,
  55                       uint32_t hash_function_count,
  56                       uint32_t hash_seed_offset,
  57                       const std::string& str);
  58
  59 }  // namespace internal
  60
  61 }  // namespace rappor
  62
  63 #endif  // COMPONENTS_RAPPOR_BLOOM_FILTER_H_