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.

Articles from blogs I read Generated by openring

Go Developer Survey 2023 Q1 Results

An analysis of the results from the 2023 Q1 Go Developer Survey.

via The Go Blog May 11, 2023

Summary of changes for April 2023

Hey everyone! This is the list of all the changes we've done to our projects and apps during the month of April. We'll also be reporting in our on position in the world, and on our future plans. Summary Of Changes 100r.co, added charging electro…

via Hundred Rabbits May 1, 2023

HDR hackfest wrap-up

Last week I’ve been attending the HDR hackfest organized by Red Hat. The trip to Prague was rather chaotic: the morning right after the SourceHut DoS incident, I got a notification that my plane was cancelled, so had to re-book a new flight and hotel. Then a…

via emersion May 1, 2023