tor  0.4.1.0-alpha-dev
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.

Macros

#define BLOOMFILT_N_HASHES   2
 
#define BLOOMFILT_KEY_LEN   (BLOOMFILT_N_HASHES * 16)
 
#define bloomfilt_free(set)   FREE_AND_NULL(bloomfilt_t, bloomfilt_free_, (set))
 

Typedefs

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

Functions

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

◆ BLOOMFILT_KEY_LEN

#define BLOOMFILT_KEY_LEN   (BLOOMFILT_N_HASHES * 16)

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().

◆ BLOOMFILT_N_HASHES

#define BLOOMFILT_N_HASHES   2

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().