2 +----------------------------------------------------------------------+
4 +----------------------------------------------------------------------+
5 | Copyright (c) 2010-present Facebook, Inc. (http://www.facebook.com) |
6 +----------------------------------------------------------------------+
7 | This source file is subject to version 3.01 of the PHP license, |
8 | that is bundled with this package in the file LICENSE, and is |
9 | available through the world-wide-web at the following url: |
10 | http://www.php.net/license/3_01.txt |
11 | If you did not receive a copy of the PHP license and are unable to |
12 | obtain it through the world-wide-web, please send a note to |
13 | license@php.net so we can mail you a copy immediately. |
14 +----------------------------------------------------------------------+
16 #ifndef HPHP_BLOOM_FILTER_H
17 #define HPHP_BLOOM_FILTER_H
19 #include <boost/dynamic_bitset.hpp>
21 #include "hphp/util/hash.h"
25 template<size_t NBITS
> struct BloomFilter
{
26 BloomFilter() : bits_
{NBITS
} {}
27 using T
= const void*;
28 static size_t h1(size_t h
) { return h
% NBITS
; }
29 static size_t h2(size_t h
) { return (h
/ NBITS
) % NBITS
; }
31 auto h
= hash_int64(intptr_t(x
));
32 bits_
.set(h1(h
)).set(h2(h
));
34 bool test(T x
) const {
35 auto h
= hash_int64(intptr_t(x
));
36 return bits_
.test(h1(h
)) & bits_
.test(h2(h
));
40 static_assert(NBITS
< (1LL << 32), "");
43 boost::dynamic_bitset
<> bits_
;
47 #endif // HPHP_BLOOM_FILTER_H