gatb.core-API-1.4.2
Public Member Functions | List of all members
BloomCacheCoherent< Item > Class Template Reference

Bloom filter implementation with CPU cache consideration. More...

#include <Bloom.hpp>

Inheritance diagram for BloomCacheCoherent< Item >:
Inheritance graph

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 ()
 

Detailed Description

template<typename Item>
class gatb::core::tools::collections::impl::BloomCacheCoherent< Item >

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.

Constructor & Destructor Documentation

BloomCacheCoherent ( u_int64_t  tai_bloom,
size_t  nbHash = 4,
size_t  block_nbits = 12 
)
inline

Constructor.

Parameters
[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)

Member Function Documentation

bool contains ( const Item &  item)
inlinevirtual

Reimplemented from BloomContainer< Item >.

Reimplemented in BloomNeighborCoherent< Item >.

u_int64_t getBitSize ( )
inlinevirtual

Get the size of the Bloom filter (in bits).

Returns
the size of the bit set of the Bloom filter

Reimplemented from BloomContainer< Item >.

Reimplemented in BloomExtendedNeighborCoherent< Item >, and BloomNeighborCoherent< Item >.

std::string getName ( ) const
inlinevirtual

Get the name of the implementation class.

Returns
the class name.

Reimplemented from Bloom< Item >.

Reimplemented in BloomExtendedNeighborCoherent< Item >, and BloomNeighborCoherent< Item >.

void insert ( const Item &  item)
inlinevirtual

Reimplemented from Bloom< Item >.

Reimplemented in BloomExtendedNeighborCoherent< Item >, and BloomNeighborCoherent< Item >.

unsigned long weight ( )
inlinevirtual

Return the number of 1's in the Bloom (nibble by nibble)

Returns
the weight of the Bloom filter

Reimplemented from Bloom< Item >.

The documentation for this class was generated from the following file: