gatb.core-API-0.0.0
|
Bloom filter implementation with CPU cache consideration. More...
#include <Bloom.hpp>
Public Member Functions | |
BloomCacheCoherent (u_int64_t tai_bloom, size_t nbHash=4, size_t block_nbits=12) | |
void | insert (const Item &item) |
std::string | getName () const |
u_int64_t | getBitSize () |
bool | contains (const Item &item) |
unsigned long | weight () |
Public Member Functions inherited from Bloom< Item > | |
Bloom (u_int64_t tai_bloom, size_t nbHash=4) | |
void | flush () |
void | dump (const char *filename) |
Public Member Functions inherited from BloomContainer< Item > | |
BloomContainer (u_int64_t tai_bloom, size_t nbHash=4) | |
virtual | ~BloomContainer () |
size_t | getNbHash () const |
virtual std::bitset< 4 > | contains4 (const Item &item, bool right) |
virtual std::bitset< 8 > | contains8 (const Item &item) |
virtual u_int8_t *& | getArray () |
virtual u_int64_t | getSize () |
Public Member Functions inherited from IBloom< Item > | |
virtual | ~IBloom () |
Public Member Functions inherited from Container< Item > | |
virtual | ~Container () |
Public Member Functions inherited from ISmartPointer | |
virtual | ~ISmartPointer () |
Public Member Functions inherited from Bag< Item > | |
virtual void | insert (const std::vector< Item > &items, size_t length=0) |
virtual void | insert (const Item *items, size_t length) |
Public Member Functions inherited from SmartPointer | |
void | use () |
void | forget () |
Additional Inherited Members | |
Protected Member Functions inherited from SmartPointer | |
SmartPointer () | |
virtual | ~SmartPointer () |
Bloom filter implementation with CPU cache consideration.
This implementation tries to avoid CPU cache misses by improving memory locality.
The idea is to compute the first hash function as usual. Then the other hash functions are computed in order to return values near to the first value.
The proximity is defined by a block size. Note that a too small block will produce more false positive than usual.
|
inline |
Constructor.
[in] | tai_bloom | : size (in bits) of the bloom filter. |
[in] | nbHash | : number of hash functions to use |
[in] | block_nbits | : size of the block (actual 2^nbits) |
|
inlinevirtual |
Reimplemented from BloomContainer< Item >.
Reimplemented in BloomNeighborCoherent< Item >.
|
inlinevirtual |
Get the size of the Bloom filter (in bits).
Reimplemented from BloomContainer< Item >.
Reimplemented in BloomExtendedNeighborCoherent< Item >, and BloomNeighborCoherent< Item >.
|
inlinevirtual |
Get the name of the implementation class.
Reimplemented from Bloom< Item >.
Reimplemented in BloomExtendedNeighborCoherent< Item >, and BloomNeighborCoherent< Item >.
|
inlinevirtual |
Reimplemented from Bloom< Item >.
Reimplemented in BloomExtendedNeighborCoherent< Item >, and BloomNeighborCoherent< Item >.
|
inlinevirtual |
Return the number of 1's in the Bloom (nibble by nibble)
Reimplemented from Bloom< Item >.