GCSFilter Class Reference

This implements a Golomb-coded set as defined in BIP 158. More...

#include <blockfilter.h>

Public Types
typedef std::vector< unsigned char >	Element
typedef std::set< Element >	ElementSet

Public Member Functions
	GCSFilter (uint64_t siphash_k0=0, uint64_t siphash_k1=0, uint8_t P=0, uint32_t M=0)
	Constructs an empty filter. More...
	GCSFilter (uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, uint32_t M, std::vector< unsigned char > encoded_filter)
	Reconstructs an already-created filter from an encoding. More...
	GCSFilter (uint64_t siphash_k0, uint64_t siphash_k1, uint8_t P, uint32_t M, const ElementSet &elements)
	Builds a new filter from the params and set of elements. More...
uint8_t	GetP () const
uint32_t	GetN () const
uint32_t	GetM () const
const std::vector< unsigned char > &	GetEncoded () const
bool	Match (const Element &element) const
	Checks if the element may be in the set. More...
bool	MatchAny (const ElementSet &elements) const
	Checks if any of the given elements may be in the set. More...

Private Member Functions
uint64_t	HashToRange (const Element &element) const
	Hash a data element to an integer in the range [0, N * M). More...
std::vector< uint64_t >	BuildHashedSet (const ElementSet &elements) const
bool	MatchInternal (const uint64_t *sorted_element_hashes, size_t size) const
	Helper method used to implement Match and MatchAny. More...

Private Attributes
uint64_t	m_siphash_k0
uint64_t	m_siphash_k1
uint8_t	m_P
	Golomb-Rice coding parameter. More...
uint32_t	m_M
	Inverse false positive rate. More...
uint32_t	m_N
	Number of elements in the filter. More...
uint64_t	m_F
	Range of element hashes, F = N * M. More...
std::vector< unsigned char >	m_encoded

Detailed Description

This implements a Golomb-coded set as defined in BIP 158.

It is a compact, probabilistic data structure for testing set membership.

Definition at line 21 of file blockfilter.h.

Member Typedef Documentation

Element

typedef std::vector<unsigned char> GCSFilter::Element

Definition at line 24 of file blockfilter.h.

ElementSet

typedef std::set<Element> GCSFilter::ElementSet

Definition at line 25 of file blockfilter.h.

Constructor & Destructor Documentation

GCSFilter() [1/3]

GCSFilter::GCSFilter	(	uint64_t	siphash_k0 = 0,
		uint64_t	siphash_k1 = 0,
		uint8_t	P = 0,
		uint32_t	M = 0
	)

Constructs an empty filter.

Definition at line 98 of file blockfilter.cpp.

GCSFilter() [2/3]

GCSFilter::GCSFilter	(	uint64_t	siphash_k0,
		uint64_t	siphash_k1,
		uint8_t	P,
		uint32_t	M,
		std::vector< unsigned char >	encoded_filter
	)

Reconstructs an already-created filter from an encoding.

Definition at line 102 of file blockfilter.cpp.

GCSFilter() [3/3]

GCSFilter::GCSFilter	(	uint64_t	siphash_k0,
		uint64_t	siphash_k1,
		uint8_t	P,
		uint32_t	M,
		const ElementSet &	elements
	)

Builds a new filter from the params and set of elements.

Definition at line 128 of file blockfilter.cpp.

Member Function Documentation

BuildHashedSet()

std::vector< uint64_t > GCSFilter::BuildHashedSet ( const ElementSet &  elements ) const

private

Definition at line 87 of file blockfilter.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

GetEncoded()

const std::vector<unsigned char>& GCSFilter::GetEncoded ( ) const

inline

Definition at line 60 of file blockfilter.h.

Here is the caller graph for this function:

GetM()

uint32_t GCSFilter::GetM ( ) const

inline

Definition at line 59 of file blockfilter.h.

GetN()

uint32_t GCSFilter::GetN ( ) const

inline

Definition at line 58 of file blockfilter.h.

GetP()

uint8_t GCSFilter::GetP ( ) const

inline

Definition at line 57 of file blockfilter.h.

HashToRange()

uint64_t GCSFilter::HashToRange ( const Element &  element ) const

private

Hash a data element to an integer in the range [0, N * M).

Definition at line 79 of file blockfilter.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Match()

bool GCSFilter::Match

(

const Element &

element

)

const

Checks if the element may be in the set.

False positives are possible with probability 1/M.

Definition at line 191 of file blockfilter.cpp.

Here is the call graph for this function:

MatchAny()

bool GCSFilter::MatchAny

(

const ElementSet &

elements

)

const

Checks if any of the given elements may be in the set.

False positives are possible with probability 1/M per element checked. This is more efficient that checking Match on multiple elements separately.

Definition at line 197 of file blockfilter.cpp.

Here is the call graph for this function:

MatchInternal()

bool GCSFilter::MatchInternal ( const uint64_t *  sorted_element_hashes, size_t  size  ) const

private

Helper method used to implement Match and MatchAny.

Definition at line 159 of file blockfilter.cpp.

Here is the caller graph for this function:

Member Data Documentation

m_encoded

std::vector<unsigned char> GCSFilter::m_encoded

private

Definition at line 34 of file blockfilter.h.

m_F

uint64_t GCSFilter::m_F

private

Range of element hashes, F = N * M.

Definition at line 33 of file blockfilter.h.

m_M

uint32_t GCSFilter::m_M

private

Inverse false positive rate.

Definition at line 31 of file blockfilter.h.

m_N

uint32_t GCSFilter::m_N

private

Number of elements in the filter.

Definition at line 32 of file blockfilter.h.

m_P

uint8_t GCSFilter::m_P

private

Golomb-Rice coding parameter.

Definition at line 30 of file blockfilter.h.

m_siphash_k0

uint64_t GCSFilter::m_siphash_k0

private

Definition at line 28 of file blockfilter.h.

m_siphash_k1

uint64_t GCSFilter::m_siphash_k1

private

Definition at line 29 of file blockfilter.h.

---

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

• src/blockfilter.h
• src/blockfilter.cpp