GCSFilter Class Reference

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

#include <blockfilter.h>

Collaboration diagram for GCSFilter:

Classes
struct	Params

Public Types
typedef std::vector< uint8_t >	Element
typedef std::unordered_set< Element, ByteVectorHash >	ElementSet

Public Member Functions
	GCSFilter (const Params &params=Params())
	Constructs an empty filter. More...
	GCSFilter (const Params &params, std::vector< uint8_t > encoded_filter)
	Reconstructs an already-created filter from an encoding. More...
	GCSFilter (const Params &params, const ElementSet &elements)
	Builds a new filter from the params and set of elements. More...
uint32_t	GetN () const
const Params &	GetParams () const
const std::vector< uint8_t > &	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
Params	m_params
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< uint8_t >	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 25 of file blockfilter.h.

Member Typedef Documentation

Element

typedef std::vector<uint8_t> GCSFilter::Element

Definition at line 27 of file blockfilter.h.

ElementSet

typedef std::unordered_set<Element, ByteVectorHash> GCSFilter::ElementSet

Definition at line 28 of file blockfilter.h.

Constructor & Destructor Documentation

GCSFilter() [1/3]

GCSFilter::GCSFilter ( const Params &  params = Params() )

explicit

Constructs an empty filter.

Definition at line 46 of file blockfilter.cpp.

GCSFilter() [2/3]

GCSFilter::GCSFilter	(	const Params &	params,
		std::vector< uint8_t >	encoded_filter
	)

Reconstructs an already-created filter from an encoding.

Definition at line 49 of file blockfilter.cpp.

Here is the call graph for this function:

GCSFilter() [3/3]

GCSFilter::GCSFilter	(	const Params &	params,
		const ElementSet &	elements
	)

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

Definition at line 72 of file blockfilter.cpp.

Here is the call graph for this function:

Member Function Documentation

BuildHashedSet()

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

private

Definition at line 36 of file blockfilter.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

GetEncoded()

const std::vector< uint8_t > & GCSFilter::GetEncoded ( ) const

inline

Definition at line 69 of file blockfilter.h.

Here is the caller graph for this function:

GetN()

uint32_t GCSFilter::GetN ( ) const

inline

Definition at line 67 of file blockfilter.h.

GetParams()

const Params & GCSFilter::GetParams ( ) const

inline

Definition at line 68 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 28 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 133 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 138 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 101 of file blockfilter.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

m_encoded

std::vector<uint8_t> GCSFilter::m_encoded

private

Definition at line 46 of file blockfilter.h.

m_F

uint64_t GCSFilter::m_F

private

Range of element hashes, F = N * M.

Definition at line 45 of file blockfilter.h.

m_N

uint32_t GCSFilter::m_N

private

Number of elements in the filter.

Definition at line 44 of file blockfilter.h.

m_params

Params GCSFilter::m_params

private

Definition at line 43 of file blockfilter.h.

---

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

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