How to write a better bloom filter in C April 12, 2016 on Drew DeVault's blog

This is in response to How to write a bloom filter in C++, which has good intentions, but is ultimately a less than ideal bloom filter implementation. I put together a better one in C in a few minutes, and I’ll explain the advantages of it.

The important differences are:

I chose C because (1) I prefer it over C++ and (2) I just think it’s a better choice for implementing low level data types, and C++ is better used in high level code.

I’m not going to explain the mechanics of a bloom filter or most of the details of why the code looks this way, since I think the original post did a fine job of that. I’ll just present my alternate implementation:

#ifndef _BLOOM_H
#define _BLOOM_H
#include <stddef.h>
#include <stdbool.h>

typedef unsigned int (*hash_function)(const void *data);
typedef struct bloom_filter * bloom_t;

/* Creates a new bloom filter with no hash functions and size * 8 bits. */
bloom_t bloom_create(size_t size);
/* Frees a bloom filter. */
void bloom_free(bloom_t filter);
/* Adds a hashing function to the bloom filter. You should add all of the
 * functions you intend to use before you add any items. */
void bloom_add_hash(bloom_t filter, hash_function func);
/* Adds an item to the bloom filter. */
void bloom_add(bloom_t filter, const void *item);
/* Tests if an item is in the bloom filter.
 *
 * Returns false if the item has definitely not been added before. Returns true
 * if the item was probably added before. */
bool bloom_test(bloom_t filter, const void *item);

#endif

Implementation

The implementation of this is pretty straightfoward. First, here’s the actual structs behind the opaque bloom_t type:

struct bloom_hash {
    hash_function func;
    struct bloom_hash *next;
};

struct bloom_filter {
    struct bloom_hash *func;
    void *bits;
    size_t size;
};

The hash functions are a linked list, but this isn’t important. You can make that anything you want. Otherwise we have a bit of memory called “bits” and the size of it. Now, for the easy functions:

bloom_t bloom_create(size_t size) {
	bloom_t res = calloc(1, sizeof(struct bloom_filter));
	res->size = size;
	res->bits = malloc(size);
	return res;
}

void bloom_free(bloom_t filter) {
	if (filter) {
		while (filter->func) {
			struct bloom_hash *h;
			filter->func = h->next;
			free(h);
		}
		free(filter->bits);
		free(filter);
	}
}

These should be fairly self explanatory. The first interesting function is here:

void bloom_add_hash(bloom_t filter, hash_function func) {
	struct bloom_hash *h = calloc(1, sizeof(struct bloom_hash));
	h->func = func;
	struct bloom_hash *last = filter->func;
	while (last && last->next) {
		last = last->next;
	}
	if (last) {
		last->next = h;
	} else {
		filter->func = h;
	}
}

Given a hashing function from the user, this just adds it to our linked list of hash functions. There’s a slightly different code path if we’re adding the first function. The functions so far don’t really do anything specific to bloom filters. The first one that does is this:

void bloom_add(bloom_t filter, const void *item) {
	struct bloom_hash *h = filter->func;
	uint8_t *bits = filter->bits;
	while (h) {
		unsigned int hash = h->func(item);
		hash %= filter->size * 8;
		bits[hash / 8] |= 1 << hash % 8;
		h = h->next;
	}
}

This iterates over each of the hash functions the user has provided and computes the hash of the data for that function (modulo the size of our bloom filter), then it adds this to the bloom filter with this line:

bits[hash / 8] |= 1 << hash % 8;

This just sets the nth bit of the filter where n is the hash. Finally, we have the test function:

bool bloom_test(bloom_t filter, const void *item) {
	struct bloom_hash *h = filter->func;
	uint8_t *bits = filter->bits;
	while (h) {
		unsigned int hash = h->func(item);
		hash %= filter->size * 8;
		if (!(bits[hash / 8] & 1 << hash % 8)) {
			return false;
		}
		h = h->next;
	}
	return true;
}

This function is extremely similar, but instead of setting the nth bit, it checks the nth bit and returns if it’s 0:

if (!(bits[hash / 8] & 1 << hash % 8)) {

That’s it! You have a bloom filter with arbitrary data types for insert and user-supplied hash functions. I wrote up some simple test code to demonstrate this, after googling for a couple of random hash functions:

#include "bloom.h"
#include <stdio.h>

unsigned int djb2(const void *_str) {
	const char *str = _str;
	unsigned int hash = 5381;
	char c;
	while ((c = *str++)) {
		hash = ((hash << 5) + hash) + c;
	}
	return hash;
}

unsigned int jenkins(const void *_str) {
	const char *key = _str;
	unsigned int hash, i;
	while (*key) {
		hash += *key;
		hash += (hash << 10);
		hash ^= (hash >> 6);
		key++;
	}
	hash += (hash << 3);
	hash ^= (hash >> 11);
	hash += (hash << 15);
	return hash;
}

int main() {
	bloom_t bloom = bloom_create(8);
	bloom_add_hash(bloom, djb2);
	bloom_add_hash(bloom, jenkins);
	printf("Should be 0: %d\n", bloom_test(bloom, "hello world"));
	bloom_add(bloom, "hello world");
	printf("Should be 1: %d\n", bloom_test(bloom, "hello world"));
	printf("Should (probably) be 0: %d\n", bloom_test(bloom, "world hello"));
	return 0;
}

The full code is available here.

Have a comment on one of my posts? Start a discussion in my public inbox by sending an email to ~sircmpwn/public-inbox@lists.sr.ht [mailing list etiquette]

Articles from blogs I read Generated by openring

What's cooking on SourceHut? January 2022

Hello and happy new year! After a bit of well-deserved rest during the holidays, our staff (and many of our contributors) have spun our work streams back up and development continues. Our userbase has grown this month by another 634 users, bringing the total…

via Blogs on Sourcehut January 17, 2022

Status update, January 2022

Hi all! This month’s status update will be quite shorter than usual, because I’ve been taking two weeks off. I’ve been in Strasbourg (a city in the east of France) for New Year’s Eve. We’ve cooked a bunch of local food, including a Kougelhopf: But let’s get b…

via emersion January 17, 2022

Two New Tutorials for 1.18

Two new tutorials have been published in preparation for the release of Go 1.18.

via The Go Blog January 14, 2022