OLD | NEW |
---|---|
(Empty) | |
1 // Copyright (c) 2013 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 #include <string> | |
Ilya Sherman
2014/01/10 11:00:32
nit: Already included in the header file.
Steven Holte
2014/01/14 00:47:54
Done.
| |
6 | |
7 #include "base/logging.h" | |
8 #include "components/rappor/bloom_filter.h" | |
Ilya Sherman
2014/01/10 11:00:32
nit: This should be the *first* include in the imp
Steven Holte
2014/01/14 00:47:54
Done.
Steven Holte
2014/01/14 00:47:54
Done.
| |
9 #include "third_party/smhasher/src/MurmurHash3.h" | |
10 | |
11 namespace { | |
12 | |
13 // Distinct seeds are used to create unique hash functions for the bloom filter. | |
Ilya Sherman
2014/01/10 11:00:32
Might be worth mentioning how these specific seeds
Steven Holte
2014/01/15 04:53:44
Expanded the description.
| |
14 const uint32_t kHashSeeds[] = {0xd123957d, 0x6752fc9b, 0xcb6a0102, 0x1a82ea95}; | |
15 | |
16 uint32_t MurmurHash3String(const std::string& str, uint32_t seed) { | |
17 uint32_t output = 0; | |
18 // This function is optimized for x86_32, but should work on any platform. | |
19 MurmurHash3_x86_32(str.data(), str.size(), seed, &output); | |
20 return output; | |
21 } | |
22 | |
23 } // namespace | |
24 | |
25 namespace rappor { | |
26 | |
27 BloomFilter::BloomFilter(uint32_t bytes_size, uint32_t hash_count) | |
28 : bytes_(bytes_size), hash_count_(hash_count) { | |
29 DCHECK_LE(hash_count, arraysize(kHashSeeds)); | |
Ilya Sherman
2014/01/10 11:00:32
Please add an assertion that bytes_size > 0 (and p
Steven Holte
2014/01/14 00:47:54
Done.
| |
30 } | |
31 | |
32 BloomFilter::~BloomFilter() {} | |
33 | |
34 void BloomFilter::AddString(const std::string& str) { | |
35 for (size_t j = 0; j < hash_count_; ++j) { | |
Ilya Sherman
2014/01/10 11:00:32
nit: Why use |j| rather than |i| here?
Steven Holte
2014/01/14 00:47:54
Done.
| |
36 uint32_t index = MurmurHash3String(str, kHashSeeds[j]); | |
37 uint32_t byte_index = (index / 8) % bytes_.size(); | |
38 uint32_t bit_index = index % 8; | |
39 bytes_[byte_index] |= 1 << bit_index; | |
40 } | |
41 } | |
42 | |
43 void BloomFilter::AddStrings(const std::vector<std::string>& strings) { | |
44 for (size_t i = 0; i < strings.size(); ++i) | |
Ilya Sherman
2014/01/10 11:00:32
nit: Please include curly braces to enclose all lo
Alexei Svitkine (slow)
2014/01/10 12:51:02
Hmm, I advised the opposite. What's the reasoning
Ilya Sherman
2014/01/10 22:34:48
Sorry, I should have marked this as an optional ni
| |
45 AddString(strings[i]); | |
46 } | |
47 | |
48 } // namespace rappor | |
OLD | NEW |