Go to the documentation of this file. 1 #ifndef _BLOOM_FILTER_HPP_
2 #define _BLOOM_FILTER_HPP_ "$Id: bloom_filter.hpp 454 2020-07-23 20:22:23Z geoff $"
61 #define SHIFT_N_BITS_TO_POSITION(v,n,f,t) (((f >= t) ? ((v) >> (f - t)) : ((v) << (t - f))) & (((1 << n) - 1) << t))
67 KEYTYPE k2 = key + k1;
68 HASHTYPE result = (key + k2) & ((1 << (
BIT_WIDTH - 2)) - 1);
87 HASHTYPE result = ((k1 ^ k2 ^ k3 ^ k4) + key) &
HASH_MASK;
89 if (
sizeof(KEYTYPE) == 8) {
94 result = ((k5 ^ k6 ^ k7 ^ k8) + key) &
HASH_MASK;
101 HASHTYPE result = (key - k1) & ((1 << (
BIT_WIDTH - 2)) - 1);
107 uint32_t sub = hashedVal >> 6;
109 uint32_t bit = hashedVal & 63;
114 uint32_t sub = hashedVal >> 6;
116 uint32_t bit = hashedVal & 63;
117 uint64_t bitVal =
presenceTable[sub] & (
static_cast<uint64_t
>(1) << bit);
118 return ((bitVal != 0));
140 HASHTYPE h1 =
hash1(key);
141 HASHTYPE h2 =
hash2(key);
142 HASHTYPE h3 =
hash3(key);
158 HASHTYPE h1 =
hash1(key);
162 HASHTYPE h2 =
hash2(key);
166 HASHTYPE h3 =
hash3(key);
@ BIT_WIDTH
Definition: bloom_filter.hpp:49
uint64_t presenceTable[TBL_SIZE/64]
Definition: bloom_filter.hpp:53
void setPresenceBit(HASHTYPE hashedVal)
Definition: bloom_filter.hpp:106
Templated Bloom filter.
Definition: bloom_filter.hpp:46
@ HASH_MASK
Definition: bloom_filter.hpp:51
bool couldBeSelected(KEYTYPE key) const OME_ALWAYS_INLINE
Test to see if key could be of interest.
Definition: bloom_filter.hpp:157
void clear()
Clear all presence bits from the Bloom filter.
Definition: bloom_filter.hpp:131
#define OME_PREFETCH(addr, rw, locality)
Macro to request prefetch.
Definition: compiler_hints.h:362
HASHTYPE hash3(KEYTYPE key) const OME_CONST_FUNCTION
Definition: bloom_filter.hpp:99
HASHTYPE hash1(KEYTYPE key) const OME_CONST_FUNCTION
Hash 1 for Bloom filter.
Definition: bloom_filter.hpp:65
@ TBL_SIZE
Definition: bloom_filter.hpp:50
HASHTYPE hash2(KEYTYPE key) const OME_CONST_FUNCTION
Definition: bloom_filter.hpp:73
void addKey(KEYTYPE key) OME_ALWAYS_INLINE
Add a key to the Bloom filter.
Definition: bloom_filter.hpp:139
#define OME_CONST_FUNCTION
Mark as an idempotent function that only accesses arguments – no global data.
Definition: compiler_hints.h:390
bool isPresenceBitSet(HASHTYPE hashedVal) const
Definition: bloom_filter.hpp:113
#define SHIFT_N_BITS_TO_POSITION(v, n, f, t)
Definition: bloom_filter.hpp:61
Compiler-specific macros to provide performance-related hints.
#define OME_ALWAYS_INLINE
Tell the compiler to alway inline a function, regardless of optimization level.
Definition: compiler_hints.h:364
BloomFilterForKey()
Construct a Bloom filter.
Definition: bloom_filter.hpp:123
~BloomFilterForKey()
Definition: bloom_filter.hpp:127