Efficient implementation of a Bloom filter in C?

Question

This question has been asked previously but there was no answer for it at that time so I decided to ask it again.

I need an efficient implementation of a Bloom filter in C (not C++). If there is no such thing available, I would not mind implementing one, if given some good reference so that it doesn't take too much of my time.

I want to use this data structure for inserts and tests in a ratio (1:20k), so primarily it is test-intensive. The data to be tested is 64 bit integers.

Answer 1

I have a stand-alone plain C library here which may be of use: https://github.com/jvirkki/libbloom

Answer 2

Not to do too much self-promotion, but I've written a plugin for the Geany editor/IDE that filters out duplicate text lines, it uses a Bloom filter.

The implementation is in C, and you can find it right here on GitHub. It's GPL v3, so depending on your exact needs you may or may not be able to use it.

Some notes about my implementation:

• It's designed to filter strings, and doesn't abstract the key type. This means you're going to have to modify the key handling to suit your needs.
• It supports un-characteristic semantics, you can actually use it for totally non-probabilistic existance-testing if you want to (see the BloomContains callback function pointer used by bloom_filter_new()). Just pass NULL to get a "pure" filter.
• The string hash function is MurmurHash2 by Austin Appleby. I evaluated the more current MurmurHash3, but version 2 was easier to work with.
• To fit in the Geany eco system, this code uses GLib types throughout.

It hasn't been heavily tuned for performance, but should be okay. I would appreciate any feedback you might have after testing it, of course!