bloomfilt.c File Reference

Uses bitarray_t to implement a bloom filter. More...

#include <stdlib.h>
#include "lib/malloc/malloc.h"
#include "lib/container/bloomfilt.h"
#include "lib/intmath/bits.h"
#include "lib/log/util_bug.h"
#include "ext/siphash.h"

Go to the source code of this file.

Data Structures
struct	digestset_t

Macros
#define	N_BITS_PER_ITEM   (BLOOMFILT_N_HASHES * 2)
#define	BIT(set, n)   ((n) & (set)->mask)

Functions
void	bloomfilt_add (bloomfilt_t *set, const void *item)
int	bloomfilt_probably_contains (const bloomfilt_t *set, const void *item)
bloomfilt_t *	bloomfilt_new (int max_elements, bloomfilt_hash_fn hashfn, const uint8_t *random_key)
void	bloomfilt_free_ (bloomfilt_t *set)

Detailed Description

Uses bitarray_t to implement a bloom filter.

Definition in file bloomfilt.c.

Macro Definition Documentation

N_BITS_PER_ITEM

#define N_BITS_PER_ITEM   (BLOOMFILT_N_HASHES * 2)

How many bloom-filter bits we set per address. This is twice the BLOOMFILT_N_HASHES value, since we split the siphash output into two 32-bit values.

Definition at line 22 of file bloomfilt.c.

Function Documentation

bloomfilt_add()

void bloomfilt_add	(	bloomfilt_t *	set,
		const void *	item
	)

Add the element item to set.

Definition at line 38 of file bloomfilt.c.

Referenced by address_set_add(), and digestset_add().

bloomfilt_free_()

void bloomfilt_free_

(

bloomfilt_t *

set

)

Free all storage held in set.

Definition at line 107 of file bloomfilt.c.

bloomfilt_new()

bloomfilt_t* bloomfilt_new	(	int	max_elements,
		bloomfilt_hash_fn	hashfn,
		const uint8_t *	random_key
	)

Return a newly allocated bloomfilt_t, optimized to hold a total of max_elements elements with a reasonably low false positive weight.

Uses the siphash-based function hashfn to compute hard-to-collide functions of the items, and the key material random_key to key the hash. There must be BLOOMFILT_KEY_LEN bytes in the supplied key.

Definition at line 78 of file bloomfilt.c.

bloomfilt_probably_contains()

int bloomfilt_probably_contains	(	const bloomfilt_t *	set,
		const void *	item
	)

If item is in set, return nonzero. Otherwise, probably return zero.

Definition at line 54 of file bloomfilt.c.

Referenced by address_set_probably_contains(), and digestset_probably_contains().