GCSFilter Class Reference

#include <blockfilter.h>

Classes
struct	Params

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

Public Member Functions
	GCSFilter (const Params &params=Params())
	GCSFilter (const Params &params, std::vector< unsigned char > encoded_filter)
	GCSFilter (const Params &params, const ElementSet &elements)
uint32_t	GetN () const
const Params &	GetParams () const
const std::vector< unsigned char > &	GetEncoded () const
bool	Match (const Element &element) const
bool	MatchAny (const ElementSet &elements) const

Private Member Functions
uint64_t	HashToRange (const Element &element) const
std::vector< uint64_t >	BuildHashedSet (const ElementSet &elements) const
bool	MatchInternal (const uint64_t *sorted_element_hashes, size_t size) const

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< 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.

Member Typedef Documentation

Element

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

ElementSet

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

Constructor & Destructor Documentation

GCSFilter() [1/3]

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

explicit

Constructs an empty filter.

GCSFilter() [2/3]

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

Reconstructs an already-created filter from an encoding.

GCSFilter() [3/3]

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

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

Member Function Documentation

BuildHashedSet()

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

private

GetEncoded()

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

inline

GetN()

uint32_t GCSFilter::GetN ( ) const

inline

GetParams()

const Params& GCSFilter::GetParams ( ) const

inline

HashToRange()

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

private

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

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.

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.

MatchInternal()

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

private

Helper method used to implement Match and MatchAny

Member Data Documentation

m_encoded

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

private

m_F

uint64_t GCSFilter::m_F

private

Range of element hashes, F = N * M.

m_N

uint32_t GCSFilter::m_N

private

Number of elements in the filter.

m_params

Params GCSFilter::m_params

private

---

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

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