ssp_bfilter.h File Reference

The API for a bloom filter. More...

#include "ssp_items.h"
#include <apr_pools.h>

Go to the source code of this file.

Data Structures
struct	ssp_bfilter_s
	The bloom filter including bitmap, hash functions, etc. etc. More...
Typedefs
typedef ssp_bfilter_s	ssp_bfilter_t
	The type ssp_bfilter_t is the cornerstone of this API.
Functions
ssp_bfilter_t *	ssp_bfilter_create (apr_pool_t *pool, ssp_hash_function_t *h1, ssp_hash_function_t *h2, apr_uint16_t filter_scale, apr_uint16_t filter_phase)
	Create a ssp_bfilter_t, i.e. bloom filter.
apr_uint32_t	ssp_bfilter_density (ssp_bfilter_t *f)
void	ssp_bfilter_insert (ssp_bfilter_t *b, void *symbol)
	Insert a symbol into the filter.
int	ssp_bfilter_member_p (ssp_bfilter_t *h, void *symbol)
	Return false if symbol is not a member of the set.

---

Detailed Description

The API for a bloom filter.

This API defines an opaque type ssp_bfilter_t used to represent a set of symbols, but with only two operations on that set. membership, and insert.

That algorithum used is known as a Bloom filter, see <> for additional info. As such it is possible for the membership query to return false positives.

---

Typedef Documentation

typedef struct ssp_bfilter_s ssp_bfilter_t

The type ssp_bfilter_t is the cornerstone of this API. Instances are allocated in an APR pool and survive until that pool is cleared. You may insert symbols into the set, and enquire if a symbol is a member of a set.

---

Function Documentation

ssp_bfilter_t* ssp_bfilter_create (  apr_pool_t *  pool, ssp_hash_function_t *  h1, ssp_hash_function_t *  h2, apr_uint16_t  filter_scale, apr_uint16_t  filter_phase )

Create a ssp_bfilter_t, i.e. bloom filter. Instantiate a fresh ssp_bfilter_t in the pool given. The user provides two hash functions that will be used to map symbols into the state of the filter. Two parameters filter_scale and filter_phase configure how accurate the filter is. Scales, a small integer, sets the size of the bit map. The bit map is 2^scale in size. While the phase sets how many bits are set in the bitmap for each symbol inserted.

apr_uint32_t ssp_bfilter_density (  ssp_bfilter_t *  f  )

The number of one bits in the underlying bitmap. Since 2^scale is the total number of bits you can use this to get a feel for how likely false positives are becoming. This can be used to compute how saturated the filter is, and in combination with the phase estimate the chance for false positives.

void ssp_bfilter_insert (  ssp_bfilter_t *  b, void *  symbol )

Insert a symbol into the filter. Calls on bloom_insert adds a symbol to the set of symbols in the bloom filter.

int ssp_bfilter_member_p (  ssp_bfilter_t *  h, void *  symbol )

Return false if symbol is not a member of the set. This never returns a false negative but may occationally return a false positive.

---