Typedefs | |
typedef struct _BloomFilter | BloomFilter |
A bloom filter structure. | |
typedef void * | BloomFilterValue |
A value stored in a BloomFilter. | |
typedef unsigned long(* | BloomFilterHashFunc )(BloomFilterValue data) |
Hash function used to generate hash values for values inserted into a bloom filter. | |
Functions | |
BloomFilter * | bloom_filter_new (unsigned int table_size, BloomFilterHashFunc hash_func, unsigned int num_functions) |
Create a new bloom filter. | |
void | bloom_filter_free (BloomFilter *bloomfilter) |
Destroy a bloom filter. | |
void | bloom_filter_insert (BloomFilter *bloomfilter, BloomFilterValue value) |
Insert a value into a bloom filter. | |
int | bloom_filter_query (BloomFilter *bloomfilter, BloomFilterValue value) |
Query a bloom filter for a particular value. | |
void | bloom_filter_read (BloomFilter *bloomfilter, unsigned char *array) |
Read the contents of a bloom filter into an array. | |
void | bloom_filter_load (BloomFilter *bloomfilter, unsigned char *array) |
Load the contents of a bloom filter from an array. | |
BloomFilter * | bloom_filter_union (BloomFilter *filter1, BloomFilter *filter2) |
Find the union of two bloom filters. | |
BloomFilter * | bloom_filter_intersection (BloomFilter *filter1, BloomFilter *filter2) |
Find the intersection of two bloom filters. |
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 unsigned long(* BloomFilterHashFunc)(BloomFilterValue data) |
Hash function used to generate hash values for values inserted into a bloom filter.
data | The value to generate a hash value for. |
void bloom_filter_free | ( | BloomFilter * | bloomfilter | ) |
Destroy a bloom filter.
bloomfilter | The bloom filter to destroy. |
void bloom_filter_insert | ( | BloomFilter * | bloomfilter, | |
BloomFilterValue | value | |||
) |
Insert a value into a bloom filter.
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.
filter1 | The first filter. | |
filter2 | The second filter. |
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.
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.
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. |
int bloom_filter_query | ( | BloomFilter * | bloomfilter, | |
BloomFilterValue | value | |||
) |
Query a bloom filter for a particular value.
bloomfilter | The bloom filter. | |
value | The value to look up. |
void bloom_filter_read | ( | BloomFilter * | bloomfilter, | |
unsigned char * | array | |||
) |
Read the contents of a bloom filter into an array.
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.
filter1 | The first filter. | |
filter2 | The second filter. |