/cvmfs/atlas.cern.ch/repo/sw/ASG/AnalysisBase/2.4.28/CxxUtils/CxxUtils/libcalg/bloom-filter.h File Reference

Bloom filter. More...

Go to the source code of this file.

Typedefs
typedef struct _BloomFilter	BloomFilter
typedef void *	BloomFilterValue
typedef unsigned long(*	BloomFilterHashFunc )(BloomFilterValue data)
Functions
BloomFilter *	bloom_filter_new (unsigned int table_size, BloomFilterHashFunc hash_func, unsigned int num_functions)
void	bloom_filter_free (BloomFilter *bloomfilter)
void	bloom_filter_insert (BloomFilter *bloomfilter, BloomFilterValue value)
int	bloom_filter_query (BloomFilter *bloomfilter, BloomFilterValue value)
void	bloom_filter_read (BloomFilter *bloomfilter, unsigned char *array)
void	bloom_filter_load (BloomFilter *bloomfilter, unsigned char *array)
BloomFilter *	bloom_filter_union (BloomFilter *filter1, BloomFilter *filter2)
BloomFilter *	bloom_filter_intersection (BloomFilter *filter1, BloomFilter *filter2)

---

Detailed Description

Bloom filter.

A bloom filter is a space efficient data structure that can be used to test whether a given element is part of a set. Lookups will occasionally generate false positives, but never false negatives.

To create a bloom filter, use bloom_filter_new. To destroy a bloom filter, use bloom_filter_free.

To insert a value into a bloom filter, use bloom_filter_insert.

To query whether a value is part of the set, use bloom_filter_query.

---

Typedef Documentation

typedef struct _BloomFilter BloomFilter

A bloom filter structure.

typedef unsigned long(* BloomFilterHashFunc)(BloomFilterValue data)

Hash function used to generate hash values for values inserted into a bloom filter.

Parameters:

data

The value to generate a hash value for.

Returns:

The hash value.

typedef void* BloomFilterValue

A value stored in a BloomFilter.

---

Function Documentation

void bloom_filter_free

(

BloomFilter *

bloomfilter

)

Destroy a bloom filter.

Parameters:

bloomfilter

The bloom filter to destroy.

void bloom_filter_insert	(	BloomFilter *	bloomfilter,
		BloomFilterValue	value
	)

Insert a value into a bloom filter.

Parameters:

	bloomfilter	The bloom filter.
	value	The value to insert.

BloomFilter* bloom_filter_intersection	(	BloomFilter *	filter1,
		BloomFilter *	filter2
	)

Find the intersection of two bloom filters. Values are only ever present in the resulting filter if they are present in both of the original filters.

Both of the original filters must have been created using the same parameters to bloom_filter_new.

Parameters:

	filter1	The first filter.
	filter2	The second filter.

Returns:

A new filter which is an intersection of the two filters, or NULL if it was not possible to allocate memory for the new filter, or if the two filters specified were created with different parameters.

void bloom_filter_load	(	BloomFilter *	bloomfilter,
		unsigned char *	array
	)

Load the contents of a bloom filter from an array. The data loaded should be the output read from bloom_filter_read, from a bloom filter created using the same arguments used to create the original filter.

Parameters:

	bloomfilter	The bloom filter.
	array	Pointer to the array to load from. This should be (table_size + 7) / 8 bytes in length.

BloomFilter* bloom_filter_new	(	unsigned int	table_size,
		BloomFilterHashFunc	hash_func,
		unsigned int	num_functions
	)

Create a new bloom filter.

Parameters:

	table_size	The size of the bloom filter. The greater the table size, the more elements can be stored, and the lesser the chance of false positives.
	hash_func	Hash function to use on values stored in the filter.
	num_functions	Number of hash functions to apply to each element on insertion. This running time for insertion and queries is proportional to this value. The more functions applied, the lesser the chance of false positives. The maximum number of functions is 64.

Returns:

A new hash table structure, or NULL if it was not possible to allocate the new bloom filter.

int bloom_filter_query	(	BloomFilter *	bloomfilter,
		BloomFilterValue	value
	)

Query a bloom filter for a particular value.

Parameters:

	bloomfilter	The bloom filter.
	value	The value to look up.

Returns:

Zero if the value was definitely not inserted into the filter. Non-zero indicates that it either may or may not have been inserted.

void bloom_filter_read	(	BloomFilter *	bloomfilter,
		unsigned char *	array
	)

Read the contents of a bloom filter into an array.

Parameters:

	bloomfilter	The bloom filter.
	array	Pointer to the array to read into. This should be (table_size + 7) / 8 bytes in length.

BloomFilter* bloom_filter_union	(	BloomFilter *	filter1,
		BloomFilter *	filter2
	)

Find the union of two bloom filters. Values are present in the resulting filter if they are present in either of the original filters.

Both of the original filters must have been created using the same parameters to bloom_filter_new.

Parameters:

	filter1	The first filter.
	filter2	The second filter.

Returns:

A new filter which is an intersection of the two filters, or NULL if it was not possible to allocate memory for the new filter, or if the two filters specified were created with different parameters.