Author: Crownstone Team Copyright: Crownstone (https://crownstone.rocks) Date: 02 Apr., 2021 License: LGPLv3+, Apache License 2.0, and/or MIT (triple-licensed) More...

#include <cs_CuckooFilter.h>

Inheritance diagram for CuckooFilter:

[legend]

Collaboration diagram for CuckooFilter:

[legend]

Public Member Functions
bool	isValid () override

bool	contains (const void *key, size_t keyLengthInBytes) override

constexpr size_t	size ()
	Total number of bytes this instance occypies. More...

bool	add (cuckoo_fingerprint_t finger, cuckoo_index_t bucketIndex)

bool	remove (cuckoo_fingerprint_t finger, cuckoo_index_t bucketIndex)

bool	contains (cuckoo_fingerprint_t finger, cuckoo_index_t bucketIndex)

bool	add (cuckoo_key_t key, size_t keyLengthInBytes)

bool	remove (cuckoo_key_t key, size_t keyLengthInBytes)

cuckoo_compressed_fingerprint_t	getCompressedFingerprint (cuckoo_key_t key, size_t keyLengthInBytes)
	Reduces a key (element) to a compressed fingerprint, consisting of the fingerprint of the key and its associated primary position in the fingerprint array. More...

	CuckooFilter (cuckoo_filter_data_t *data)
	Wraps a data struct into a CuckooFilter object. More...

	CuckooFilter ()
	Use this with loads of care, _data is never checked to be non-nullptr in this class. More...

void	clear ()
	Memsets the bucket_array to 0x00 and sets victim to 0. More...

void	init (cuckoo_index_t bucketCount, cuckoo_index_t nestsPerBucket)
	Sets the size parameters and then clear()s this object so that the bucket_array is filled with precisely enough 0x00s to represent an empty filter. More...

constexpr size_t	bucketCount ()
	Actual bucket count value may be bigger than a cuckoo_index_t can hold. More...

constexpr size_t	bufferSize ()

Public Member Functions inherited from FilterInterface
virtual	~FilterInterface ()=default

virtual bool	contains (const void *key, size_t keyLengthInBytes)=0

virtual size_t	size ()=0

virtual bool	isValid ()=0

Static Public Member Functions
static constexpr size_t	fingerprintCount (size_t bucketCount, cuckoo_index_t nestsPerBucket)

static constexpr size_t	bufferSize (size_t bucketCount, cuckoo_index_t nestsPerBucket)
	Size of the byte buffer in bytes. More...

static constexpr size_t	size (cuckoo_index_t bucketCount, cuckoo_index_t nestsPerBucket)
	Total number of bytes a CuckooFilter with the given parameters would occupy. More...

Private Member Functions
cuckoo_extended_fingerprint_t	getExtendedFingerprint (cuckoo_key_t key, size_t keyLengthInBytes)
	Reduces a key (element) to an extended fingerprint, consisting of the fingerprint of the key and its associated positions in the fingerprint array. More...

cuckoo_extended_fingerprint_t	getExtendedFingerprint (cuckoo_fingerprint_t fingerprint, cuckoo_index_t bucketIndex)
	Expands a fingerprint and the index where it is placed into an extended fingerprint, by computing the alternative index in the fingerprint array. More...

cuckoo_fingerprint_t	filterHash ()
	A crc16 hash of this filters current contents (_data). More...

cuckoo_fingerprint_t	hashToFingerprint (cuckoo_key_t key, size_t keyLengthInBytes)
	Hashes the given key into a fingerprint. More...

cuckoo_fingerprint_t	hashToBucket (cuckoo_key_t key, size_t keyLengthInBytes)
	Hashes the given key to obtain an (untruncated) bucket index. More...

cuckoo_fingerprint_t &	lookupFingerprint (cuckoo_index_t bucketIndex, cuckoo_index_t fingerIndex)
	Returns a reference to the fingerprint at the given coordinates. More...

bool	addFingerprintToBucket (cuckoo_fingerprint_t fingerprint, cuckoo_index_t bucketIndex)
	Returns true if there was an empty space in the bucket and placement was successful, returns false otherwise. More...

bool	removeFingerprintFromBucket (cuckoo_fingerprint_t fingerprint, cuckoo_index_t bucketIndex)
	Returns true if found and removed, returns false if not found. More...

bool	move (cuckoo_extended_fingerprint_t entryToInsert)

bool	add (cuckoo_extended_fingerprint_t efp)

bool	remove (cuckoo_extended_fingerprint_t efp)

bool	contains (cuckoo_extended_fingerprint_t efp)

Private Attributes
cuckoo_filter_data_t *	_data

Static Private Attributes
static constexpr size_t	MAX_KICK_ATTEMPTS = 100

Detailed Description

Author: Crownstone Team Copyright: Crownstone (https://crownstone.rocks) Date: 02 Apr., 2021 License: LGPLv3+, Apache License 2.0, and/or MIT (triple-licensed)

This library is forked from the public github repository and initially added to bluenet on 19-02-2021. Code has been extensively refactored for idiomatic use of C++ and many implementation details have changed e.g. to fix implicit narrowing/widening of integers, large recursion and type punning in allocations.

Those changes have been made by the Crownstone Team and fall under the project license mentioned above.

The original code and the extent to which is required by applicable law is left under its original license included below and is attributed to the original author Jonah H. Harris jonah.nosp@m..har.nosp@m.ris@g.nosp@m.mail.nosp@m..com.

The MIT License

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. A CuckooFilter is a probabilistic datatype is made for approximate membership queries.

This implementation consists of the POD data structure cuckoo_filter_data_t and a 'view class' Cuckoofilter, which is used to manipulate the data struct.

The cuckoo_filter_data_t struct is not aware of its size. That must be managed by the owning scope, which can query the required size in bytes for the given amount of fingerprints through the CuckooFilter class.

The 'elements' that one can add to a CuckooFilter are of type cuckoo_key_t which are simply sequences of bytes. To check if an element is contained in a filter, refer to the contains methods.

CuckooFilter data contents are stored in an array of fingerprints which is segmented into 'buckets'. These buckets are used for indexing, and although for an element, the bucket index and fingerprint are deterministic, the index inside the bucket is dependent on order of insertion.

More details can be found in https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf. "Cuckoo Filter: Better Than Bloom" by Bin Fan, Dave Andersen, and Michael Kaminsky

Constructor & Destructor Documentation

◆ CuckooFilter() [1/2]

CuckooFilter::CuckooFilter ( cuckoo_filter_data_t * data )

inline

Wraps a data struct into a CuckooFilter object.

◆ CuckooFilter() [2/2]

CuckooFilter::CuckooFilter ( )

inline

Use this with loads of care, _data is never checked to be non-nullptr in this class.

Member Function Documentation

◆ add() [1/3]

bool CuckooFilter::add ( cuckoo_extended_fingerprint_t efp )

private

◆ add() [2/3]

bool CuckooFilter::add	(	cuckoo_fingerprint_t	finger,
		cuckoo_index_t	bucketIndex
	)

inline

◆ add() [3/3]

bool CuckooFilter::add	(	cuckoo_key_t	key,
		size_t	keyLengthInBytes
	)

inline

◆ addFingerprintToBucket()

bool CuckooFilter::addFingerprintToBucket	(	cuckoo_fingerprint_t	fingerprint,
		cuckoo_index_t	bucketIndex
	)

private

Returns true if there was an empty space in the bucket and placement was successful, returns false otherwise.

Does not check for duplicates.

◆ bucketCount()

constexpr size_t CuckooFilter::bucketCount ( )

inlineconstexpr

Actual bucket count value may be bigger than a cuckoo_index_t can hold.

◆ bufferSize() [1/2]

constexpr size_t CuckooFilter::bufferSize ( )

inlineconstexpr

◆ bufferSize() [2/2]

static constexpr size_t CuckooFilter::bufferSize	(	size_t	bucketCount,
		cuckoo_index_t	nestsPerBucket
	)

inlinestaticconstexpr

Size of the byte buffer in bytes.

◆ clear()

void CuckooFilter::clear ( )

Memsets the bucket_array to 0x00 and sets victim to 0.

No changes are made to size.

◆ contains() [1/3]

bool CuckooFilter::contains	(	const void *	key,
		size_t	keyLengthInBytes
	)

inlineoverridevirtual

Implements FilterInterface.

◆ contains() [2/3]

bool CuckooFilter::contains ( cuckoo_extended_fingerprint_t efp )

private

◆ contains() [3/3]

bool CuckooFilter::contains	(	cuckoo_fingerprint_t	finger,
		cuckoo_index_t	bucketIndex
	)

inline

◆ filterHash()

cuckoo_fingerprint_t CuckooFilter::filterHash ( )

private

A crc16 hash of this filters current contents (_data).

◆ fingerprintCount()

static constexpr size_t CuckooFilter::fingerprintCount	(	size_t	bucketCount,
		cuckoo_index_t	nestsPerBucket
	)

inlinestaticconstexpr

◆ getCompressedFingerprint()

cuckoo_compressed_fingerprint_t CuckooFilter::getCompressedFingerprint	(	cuckoo_key_t	key,
		size_t	keyLengthInBytes
	)

Reduces a key (element) to a compressed fingerprint, consisting of the fingerprint of the key and its associated primary position in the fingerprint array.

◆ getExtendedFingerprint() [1/2]

cuckoo_extended_fingerprint_t CuckooFilter::getExtendedFingerprint	(	cuckoo_fingerprint_t	fingerprint,
		cuckoo_index_t	bucketIndex
	)

private

Expands a fingerprint and the index where it is placed into an extended fingerprint, by computing the alternative index in the fingerprint array.

Note: bucketCount must be a power of two. (which is validated at construction/init)

◆ getExtendedFingerprint() [2/2]

cuckoo_extended_fingerprint_t CuckooFilter::getExtendedFingerprint	(	cuckoo_key_t	key,
		size_t	keyLengthInBytes
	)

private

Reduces a key (element) to an extended fingerprint, consisting of the fingerprint of the key and its associated positions in the fingerprint array.

Note: bucketCount must be a power of two. (which is validated at construction/init)

◆ hashToBucket()

cuckoo_fingerprint_t CuckooFilter::hashToBucket	(	cuckoo_key_t	key,
		size_t	keyLengthInBytes
	)

private

Hashes the given key to obtain an (untruncated) bucket index.

◆ hashToFingerprint()

cuckoo_fingerprint_t CuckooFilter::hashToFingerprint	(	cuckoo_key_t	key,
		size_t	keyLengthInBytes
	)

private

Hashes the given key into a fingerprint.

◆ init()

void CuckooFilter::init	(	cuckoo_index_t	bucketCount,
		cuckoo_index_t	nestsPerBucket
	)

Sets the size parameters and then clear()s this object so that the bucket_array is filled with precisely enough 0x00s to represent an empty filter.

Parameters

[in] bucket_count_log2 number of buckets allocated will be rounde up to nearest power of 2 because of theoretical requirements.

◆ isValid()

bool CuckooFilter::isValid ( )

overridevirtual

Implements FilterInterface.

◆ lookupFingerprint()

cuckoo_fingerprint_t & CuckooFilter::lookupFingerprint	(	cuckoo_index_t	bucketIndex,
		cuckoo_index_t	fingerIndex
	)

inlineprivate

Returns a reference to the fingerprint at the given coordinates.

◆ move()

bool CuckooFilter::move ( cuckoo_extended_fingerprint_t entryToInsert )

private

◆ remove() [1/3]

bool CuckooFilter::remove ( cuckoo_extended_fingerprint_t efp )

private

◆ remove() [2/3]

bool CuckooFilter::remove	(	cuckoo_fingerprint_t	finger,
		cuckoo_index_t	bucketIndex
	)

inline

◆ remove() [3/3]

bool CuckooFilter::remove	(	cuckoo_key_t	key,
		size_t	keyLengthInBytes
	)

inline

◆ removeFingerprintFromBucket()

bool CuckooFilter::removeFingerprintFromBucket	(	cuckoo_fingerprint_t	fingerprint,
		cuckoo_index_t	bucketIndex
	)

private

Returns true if found and removed, returns false if not found.

◆ size() [1/2]

constexpr size_t CuckooFilter::size ( )

inlineconstexprvirtual

Total number of bytes this instance occypies.

Use this function instead of sizeof for this class to take the buffer into account.

Implements FilterInterface.

◆ size() [2/2]

static constexpr size_t CuckooFilter::size	(	cuckoo_index_t	bucketCount,
		cuckoo_index_t	nestsPerBucket
	)

inlinestaticconstexpr

Total number of bytes a CuckooFilter with the given parameters would occupy.

As per cppreference.com: "sizeof, and the assignment operator ignore the flexible array member." https://en.cppreference.com/w/c/language/struct

Member Data Documentation

◆ _data

cuckoo_filter_data_t* CuckooFilter::_data

private

◆ MAX_KICK_ATTEMPTS

constexpr size_t CuckooFilter::MAX_KICK_ATTEMPTS = 100

staticconstexprprivate

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

source/include/util/cs_CuckooFilter.h

Public Member Functions

Static Public Member Functions

Private Member Functions

Private Attributes

Static Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ CuckooFilter() [1/2]

◆ CuckooFilter() [2/2]

Member Function Documentation

◆ add() [1/3]

◆ add() [2/3]

◆ add() [3/3]

◆ addFingerprintToBucket()

◆ bucketCount()

◆ bufferSize() [1/2]

◆ bufferSize() [2/2]

◆ clear()

◆ contains() [1/3]

◆ contains() [2/3]

◆ contains() [3/3]

◆ filterHash()

◆ fingerprintCount()

◆ getCompressedFingerprint()

◆ getExtendedFingerprint() [1/2]

◆ getExtendedFingerprint() [2/2]

◆ hashToBucket()

◆ hashToFingerprint()

◆ init()

◆ isValid()

◆ lookupFingerprint()

◆ move()

◆ remove() [1/3]

◆ remove() [2/3]

◆ remove() [3/3]

◆ removeFingerprintFromBucket()

◆ size() [1/2]

◆ size() [2/2]

Member Data Documentation

◆ _data

◆ MAX_KICK_ATTEMPTS