nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator > Struct Template Reference

Detailed description

template< typename Hash1, typename Hash2, typename Iterator, typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>
struct nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >

A blocked Bloom filter implementation. This class is storage-free, and can used both from the host and the device. Constructing a Bloom filter can be done incrementally calling insert(), either sequentially or in parallel. The block size is determined by the value_type of the storage Iterator: e.g. a uint4 or a uint64_2 will cause the Bloom filter to use 128-bit blocks, whereas a uint64_4 will cause it to use 256-bit blocks.

Template Parameters

Hash1	the first hash function
Hash2	the second hash function
Iterator	the iterator to the internal filter storage, iterator_traits<iterator>::value_type must be one of {uint32|uint2|uint4|uint64|uint64_2|uint64_4}
OrOperator	the binary functor used to OR the filter's words with the inserted keys; NOTE: this operation must be performed atomically if the filter is constructed in parallel

Definition at line 327 of file bloom_filter.h.

#include <bloom_filter.h>

Public Types
typedef std::iterator_traits < Iterator >::value_type	block_type
typedef vector_traits < block_type >::value_type	word_type
typedef StaticVector < word_type, BLOCK_DIM >	vector_type

Public Methods
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE	blocked_bloom_filter (const uint32 k, const uint64 size, Iterator storage, const Hash1 hash1=Hash1(), const Hash2 hash2=Hash2())
template<typename Key >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void	insert (const Key key, const OrOperator or_op=OrOperator())
template<typename Key >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE bool	has (const Key key) const
template<typename Key >
NVBIO_FORCEINLINE NVBIO_HOST_DEVICE bool	operator[] (const Key key) const
template<typename Key >
void	insert (const Key key, const OrOperator or_op)
template<typename Key >
bool	has (const Key key) const

Public Members
uint32	m_k
uint64	m_size
Iterator	m_storage
Hash1	m_hash1
Hash2	m_hash2

Static Public Members
static const uint32	BLOCK_DIM = vector_traits<block_type>::DIM
static const uint32	BLOCK_SIZE = sizeof(block_type)*8u
static const uint32	WORD_SIZE = sizeof(word_type)*8u

Member Typedef Documentation

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

typedef std::iterator_traits<Iterator>::value_type nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::block_type

Definition at line 329 of file bloom_filter.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

typedef StaticVector<word_type,BLOCK_DIM> nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::vector_type

Definition at line 336 of file bloom_filter.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

typedef vector_traits<block_type>::value_type nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::word_type

Definition at line 330 of file bloom_filter.h.

Constructor & Destructor Documentation

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator >

nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::blocked_bloom_filter	(	const uint32	k,
		const uint64	size,
		Iterator	storage,
		const Hash1	hash1 = Hash1(),
		const Hash2	hash2 = Hash2()
	)

constructor

Parameters

size	the Bloom filter's storage size, in bits
storage	the Bloom filter's internal storage
hash1	the first hashing function
hash2	the second hashing function

Definition at line 106 of file bloom_filter_inl.h.

Member Function Documentation

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

template<typename Key >

bool nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::has

(

const Key

key)

const

Definition at line 155 of file bloom_filter_inl.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

template<typename Key >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE bool nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::has

(

const Key

key)

const

check for a key

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

template<typename Key >

void nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::insert	(	const Key	key,
		const OrOperator	or_op
	)

Definition at line 124 of file bloom_filter_inl.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

template<typename Key >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE void nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::insert	(	const Key	key,
		const OrOperator	or_op = OrOperator()
	)

insert a key

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

template<typename Key >

NVBIO_FORCEINLINE NVBIO_HOST_DEVICE bool nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::operator[] ( const Key  key) const

inline

check for a key

Definition at line 369 of file bloom_filter.h.

Member Data Documentation

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

const uint32 nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::BLOCK_DIM = vector_traits<block_type>::DIM

static

Definition at line 332 of file bloom_filter.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

const uint32 nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::BLOCK_SIZE = sizeof(block_type)*8u

static

Definition at line 333 of file bloom_filter.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

Hash1 nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::m_hash1

Definition at line 374 of file bloom_filter.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

Hash2 nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::m_hash2

Definition at line 375 of file bloom_filter.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

uint32 nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::m_k

Definition at line 371 of file bloom_filter.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

uint64 nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::m_size

Definition at line 372 of file bloom_filter.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

Iterator nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::m_storage

Definition at line 373 of file bloom_filter.h.

template<typename Hash1 , typename Hash2 , typename Iterator , typename OrOperator = inplace_or<typename std::iterator_traits<Iterator>::value_type>>

const uint32 nvbio::blocked_bloom_filter< Hash1, Hash2, Iterator, OrOperator >::WORD_SIZE = sizeof(word_type)*8u

static

Definition at line 334 of file bloom_filter.h.

---

The documentation for this struct was generated from the following files:

• E:/git/nvbio/nvbio/basic/bloom_filter.h
• E:/git/nvbio/nvbio/basic/bloom_filter_inl.h