bloom.c File Reference

Trivial bloom filter. More...

#include <stdlib.h>
#include "utils/bloom.h"
#include "utils/utils.h"

Include dependency graph for bloom.c:

Go to the source code of this file.

Data Structures
struct	bloom_filter

Functions
static uint32_t	fnv (const char *datum, size_t len)
	Hash a string, returning a 32bit value. More...
struct bloom_filter *	bloom_create (size_t size)
	Create a new bloom filter. More...
void	bloom_destroy (struct bloom_filter *b)
	Destroy a previously-created bloom filter. More...
void	bloom_insert_str (struct bloom_filter *b, const char *s, size_t z)
	Insert a string of given length (may include NULs) into the filter, using an internal hash function. More...
void	bloom_insert_hash (struct bloom_filter *b, uint32_t hash)
	Insert a given hash value into the filter, should you already have one to hand. More...
bool	bloom_search_str (struct bloom_filter *b, const char *s, size_t z)
	Search the filter for the given string, assuming it was added by bloom_insert_str(). More...
bool	bloom_search_hash (struct bloom_filter *b, uint32_t hash)
	Search the filter for the given hash value, assuming it was added by bloom_insert_hash(). More...
uint32_t	bloom_items (struct bloom_filter *b)
	Find out how many items have been added to this bloom filter. More...

Detailed Description

Trivial bloom filter.

Definition in file bloom.c.

Function Documentation

bloom_create()

struct bloom_filter * bloom_create

(

size_t

size

)

Create a new bloom filter.

Parameters

size	Size of bloom filter in bytes

Returns

Handle for newly-created bloom filter, or NULL

Definition at line 59 of file bloom.c.

References bloom_filter::size.

Referenced by urldb_add_url(), and urldb_load().

Here is the caller graph for this function:

bloom_destroy()

void bloom_destroy

(

struct bloom_filter *

b

)

Destroy a previously-created bloom filter.

Parameters

b	Bloom filter to destroy

Definition at line 71 of file bloom.c.

Referenced by urldb_destroy().

Here is the caller graph for this function:

bloom_insert_hash()

void bloom_insert_hash	(	struct bloom_filter *	b,
		uint32_t	hash
	)

Insert a given hash value into the filter, should you already have one to hand.

Parameters

b	Bloom filter to add to
hash	Value to add

Definition at line 82 of file bloom.c.

References bloom_filter::filter, bloom_filter::items, and bloom_filter::size.

Referenced by bloom_insert_str(), urldb_add_url(), and urldb_load().

Here is the caller graph for this function:

bloom_insert_str()

void bloom_insert_str	(	struct bloom_filter *	b,
		const char *	s,
		size_t	z
	)

Insert a string of given length (may include NULs) into the filter, using an internal hash function.

Parameters

b	Bloom filter to add to
s	Pointer to data
z	Length of data

Definition at line 76 of file bloom.c.

References bloom_insert_hash(), and fnv().

Here is the call graph for this function:

bloom_items()

uint32_t bloom_items

(

struct bloom_filter *

b

)

Find out how many items have been added to this bloom filter.

This is useful for deciding the size of a new bloom filter should you need to rehash it.

Parameters

b	Bloom filter to examine

Returns

Number of items that have been added

Definition at line 107 of file bloom.c.

References bloom_filter::items.

bloom_search_hash()

bool bloom_search_hash	(	struct bloom_filter *	b,
		uint32_t	hash
	)

Search the filter for the given hash value, assuming it was added by bloom_insert_hash().

May return false-positives.

Parameters

b	Bloom filter to search
hash	Hash value to search for

Returns

False if never added, True if it might have been.

Definition at line 98 of file bloom.c.

References bloom_filter::filter, and bloom_filter::size.

Referenced by bloom_search_str(), and urldb_find_url().

Here is the caller graph for this function:

bloom_search_str()

bool bloom_search_str	(	struct bloom_filter *	b,
		const char *	s,
		size_t	z
	)

Search the filter for the given string, assuming it was added by bloom_insert_str().

May return false-positives.

Parameters

b	Bloom filter to search
s	Pointer to data to search for
z	Length of data

Returns

False if never added, True if it might have been.

Definition at line 92 of file bloom.c.

References bloom_search_hash(), and fnv().

Here is the call graph for this function:

fnv()

static uint32_t fnv ( const char *  datum, size_t  len  )

inlinestatic

Hash a string, returning a 32bit value.

The hash algorithm used is Fowler Noll Vo - a very fast and simple hash, ideal for short strings. See http://en.wikipedia.org/wiki/Fowler_Noll_Vo_hash for more details.

Parameters

datum	The string to hash.
len	size_t of data length.

Returns

The calculated hash value for the datum.

Definition at line 38 of file bloom.c.

Referenced by bloom_insert_str(), and bloom_search_str().

Here is the caller graph for this function: