Bitcoin Core  0.18.99
P2P Digital Currency
Classes | Public Types | Public Member Functions | Private Member Functions | Private Attributes | List of all members
GCSFilter Class Reference

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

#include <blockfilter.h>

Collaboration diagram for GCSFilter:
[legend]

Classes

struct  Params
 

Public Types

typedef std::vector< unsigned char > Element
 
typedef std::unordered_set< Element, ByteVectorHashElementSet
 

Public Member Functions

 GCSFilter (const Params &params=Params())
 Constructs an empty filter. More...
 
 GCSFilter (const Params &params, std::vector< unsigned char > 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 ParamsGetParams () 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

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.

Definition at line 23 of file blockfilter.h.

Member Typedef Documentation

◆ Element

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

Definition at line 26 of file blockfilter.h.

◆ ElementSet

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

Definition at line 27 of file blockfilter.h.

Constructor & Destructor Documentation

◆ GCSFilter() [1/3]

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

Constructs an empty filter.

Definition at line 106 of file blockfilter.cpp.

Here is the caller graph for this function:

◆ GCSFilter() [2/3]

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

Reconstructs an already-created filter from an encoding.

Definition at line 110 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 133 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 95 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 68 of file blockfilter.h.

Here is the call graph for this function:
Here is the caller graph for this function:

◆ GetN()

uint32_t GCSFilter::GetN ( ) const
inline

Definition at line 66 of file blockfilter.h.

◆ GetParams()

const Params& GCSFilter::GetParams ( ) const
inline

Definition at line 67 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 87 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 195 of file blockfilter.cpp.

Here is the call graph for this function:
Here is the caller 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 201 of file blockfilter.cpp.

Here is the call graph for this function:
Here is the caller 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 163 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<unsigned char> GCSFilter::m_encoded
private

Definition at line 45 of file blockfilter.h.

◆ m_F

uint64_t GCSFilter::m_F
private

Range of element hashes, F = N * M.

Definition at line 44 of file blockfilter.h.

◆ m_N

uint32_t GCSFilter::m_N
private

Number of elements in the filter.

Definition at line 43 of file blockfilter.h.

◆ m_params

Params GCSFilter::m_params
private

Definition at line 42 of file blockfilter.h.


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