cs_CuckooFilter.h

Go to the documentation of this file.

 
#pragma once
 
#include <protocol/cs_CuckooFilterStructs.h>
#include <util/cs_FilterInterface.h>
 
class CuckooFilter : public FilterInterface {
public:
    // -------------------------------------------------------------
    // Interface methods.
    // -------------------------------------------------------------
 
    bool isValid() override;
 
    bool contains(const void* key, size_t keyLengthInBytes) override {
        return contains(getExtendedFingerprint(key, keyLengthInBytes));
    }
 
    constexpr size_t size() { return size(bucketCount(), _data->nestsPerBucket); }
 
    // -------------------------------------------------------------
    // These might be useful for fingerprints coming from the mesh.
    // -------------------------------------------------------------
    bool add(cuckoo_fingerprint_t finger, cuckoo_index_t bucketIndex) {
        return add(getExtendedFingerprint(finger, bucketIndex));
    }
 
    bool remove(cuckoo_fingerprint_t finger, cuckoo_index_t bucketIndex) {
        return remove(getExtendedFingerprint(finger, bucketIndex));
    }
 
    bool contains(cuckoo_fingerprint_t finger, cuckoo_index_t bucketIndex) {
        return contains(getExtendedFingerprint(finger, bucketIndex));
    }
 
    // -------------------------------------------------------------
    // these might be useful for stuff that comes in from commands
    // -------------------------------------------------------------
 
    bool add(cuckoo_key_t key, size_t keyLengthInBytes) { return add(getExtendedFingerprint(key, keyLengthInBytes)); }
 
    bool remove(cuckoo_key_t key, size_t keyLengthInBytes) {
        return remove(getExtendedFingerprint(key, keyLengthInBytes));
    }
 
    cuckoo_compressed_fingerprint_t getCompressedFingerprint(cuckoo_key_t key, size_t keyLengthInBytes);
 
    // -------------------------------------------------------------
    // Init/deinit like stuff.
    // -------------------------------------------------------------
 
    CuckooFilter(cuckoo_filter_data_t* data) : _data(data) {}
 
    CuckooFilter() : _data(nullptr) {}
 
    void clear();
 
    void init(cuckoo_index_t bucketCount, cuckoo_index_t nestsPerBucket);
 
    // -------------------------------------------------------------
    // Sizing helpers
    // -------------------------------------------------------------
 
    static constexpr size_t fingerprintCount(size_t bucketCount, cuckoo_index_t nestsPerBucket) {
        return bucketCount * nestsPerBucket;
    }
 
    static constexpr size_t bufferSize(size_t bucketCount, cuckoo_index_t nestsPerBucket) {
        return fingerprintCount(bucketCount, nestsPerBucket) * sizeof(cuckoo_fingerprint_t);
    }
 
    static constexpr size_t size(cuckoo_index_t bucketCount, cuckoo_index_t nestsPerBucket) {
        return sizeof(cuckoo_filter_data_t) + bufferSize(bucketCount, nestsPerBucket);
    }
 
    constexpr size_t bucketCount() { return 1 << _data->bucketCountLog2; }
 
    constexpr size_t bufferSize() { return bufferSize(bucketCount(), _data->nestsPerBucket); }
 
private:
    // -------------------------------------------------------------
    // Compile time settings
    // -------------------------------------------------------------
 
    static constexpr size_t MAX_KICK_ATTEMPTS = 100;
 
    // -------------------------------------------------------------
    // Run time variables
    // -------------------------------------------------------------
 
    cuckoo_filter_data_t* _data;
 
    // -------------------------------------------------------------
    // ----- Private methods -----
    // -------------------------------------------------------------
 
    cuckoo_extended_fingerprint_t getExtendedFingerprint(cuckoo_key_t key, size_t keyLengthInBytes);
 
    cuckoo_extended_fingerprint_t getExtendedFingerprint(cuckoo_fingerprint_t fingerprint, cuckoo_index_t bucketIndex);
 
    cuckoo_fingerprint_t filterHash();
 
    cuckoo_fingerprint_t hashToFingerprint(cuckoo_key_t key, size_t keyLengthInBytes);
 
    cuckoo_fingerprint_t hashToBucket(cuckoo_key_t key, size_t keyLengthInBytes);
 
    cuckoo_fingerprint_t& lookupFingerprint(cuckoo_index_t bucketIndex, cuckoo_index_t fingerIndex) {
        // TODO @ArrowAcrobatics: Please, check if there's no alignment bug here
        return (cuckoo_fingerprint_t&)_data->bucketArray[(bucketIndex * _data->nestsPerBucket) + fingerIndex];
    }
 
    bool addFingerprintToBucket(cuckoo_fingerprint_t fingerprint, cuckoo_index_t bucketIndex);
 
    bool removeFingerprintFromBucket(cuckoo_fingerprint_t fingerprint, cuckoo_index_t bucketIndex);
 
    /*
     * Puts the fingerprint in the filter, moving aside anything that is in the way unless it takes
     * more than max_kick_attempts. return true on success, false when max kick attempts was
     * reached. This doesn't check if the given fingerprint is already contained in the filter.
     */
    bool move(cuckoo_extended_fingerprint_t entryToInsert);
 
    // -------------------------------------------------------------
    // Core methods for manipulating this->data
    // -------------------------------------------------------------
 
    bool add(cuckoo_extended_fingerprint_t efp);
    bool remove(cuckoo_extended_fingerprint_t efp);
    bool contains(cuckoo_extended_fingerprint_t efp);
};