libfilter

libfilter copied to clipboard

This repository provides implementations of various Bloom filters and taffy filters for C, C++, Java, Python, and Go.

If you need a basic filter and you know ahead of time which keys will be in it, use a static filter.

If you don't know what the keys will be, but you know approximately how many there are, use a block filter.

Otherwise, use a taffy filter, which can grow as you add more keys to it.

Example usage of block filter in C:

#include <filter/block.h>

unsigned ndv = 1000000;
double fpp = 0.0065;
uint64_t hash = 0xfeedbadbee52b055;

libfilter_block filter;

unsigned bytes = libfilter_block_bytes_needed(ndv, fpp);
libfilter_block_init(bytes, &filter);
libfilter_block_add_hash(hash, &filter);
assert(libfilter_block_find_hash(hash, &filter));
libfilter_block_destruct(&filter);

in C++:

#include <filter/block.hpp>

unsigned ndv = 1000000;
double fpp = 0.0065;
uint64_t hash = 0xfeedbadbee52b055;

auto filter = filter::BlockFilter::CreateWithNdvFpp(ndv, fpp);
filter.InsertHash(hash);
assert(filter.FindHash(hash));

in Java

import com.github.jbapple.libfilter.BlockFilter;

int ndv = 1000000;
double fpp = 0.0065;
long hash = (((long) 0xfeedbadb) << 32) | (long) 0xee52b055;

BlockFilter = BlockFilter.CreateWithNdvFpp(ndv, fpp);
filter.AddHash64(hash);
assert filter.FindHash64(hash)

in Go

import ("github.com/jbapple/libfilter")

b := NewBlockFilter(BlockBytesNeeded(1000000, 0.0065))
var hash uint64
hash = 0xfeedbadbee52b055
b.AddHash(hash)
if !b.FindHash(hash) {
    panic("uhoh!")
}

in Python

import block

b = block.Block(1000000, 0.0065)
hash = 0xfeedbadbee52b055
b += hash
assert (hash in b)

To install:

make
# probably needs a sudo:
make install
make java-world
mvn -f ./java/ install -Dmaven.test.skip=true
[optional: copy java/target/libfilter-*.jar to your classpath]
make python-world
make go-world

The C and C++ libraries can also be installed with CMake:

cmake -B build -S . -DCMAKE_INSTALL_PATH=<where/to/install>
cmake --build build
# probably needs a sudo:
cmake --install build

The library targets are exported and can be used in CMakeLists.txt:

find_package(libfilter)
# The C API:
target_link_libraries(mylib PRIVATE libfilter::c)
# The C++ API:
target_link_libraries(mylib PRIVATE libfilter::cxx)