Macros | Typedefs | Functions
bloomfilt.h File Reference
#include "orconfig.h"
#include "lib/cc/torint.h"
#include "lib/container/bitarray.h"

Go to the source code of this file.


#define bloomfilt_free(set)   FREE_AND_NULL(bloomfilt_t, bloomfilt_free_, (set))


typedef struct bloomfilt_t bloomfilt_t
typedef uint64_t(* bloomfilt_hash_fn) (const struct sipkey *key, const void *item)


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

Detailed Description

Header for bloomfilt.c.

Definition in file bloomfilt.h.

Macro Definition Documentation



How much key material do we need to randomize hashes?

Definition at line 26 of file bloomfilt.h.

Referenced by address_set_new(), and digestset_new().



How many 64-bit siphash values to extract per item.

Definition at line 23 of file bloomfilt.h.

Referenced by bloomfilt_add(), and bloomfilt_probably_contains().

Typedef Documentation

◆ bloomfilt_t

typedef struct bloomfilt_t bloomfilt_t

A set of elements, implemented as a Bloom filter.

Definition at line 20 of file bloomfilt.h.

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.

References bitarray_set(), and BLOOMFILT_N_HASHES.

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.

Referenced by address_set_new(), and digestset_new().

◆ 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.

References bitarray_is_set(), and BLOOMFILT_N_HASHES.

Referenced by address_set_probably_contains(), and digestset_probably_contains().