diff options
| author | Andres Freund | 2018-04-01 00:49:41 +0000 |
|---|---|---|
| committer | Andres Freund | 2018-04-01 00:49:41 +0000 |
| commit | 51bc271790eb234a1ba4d14d3e6530f70de92ab5 (patch) | |
| tree | b97cc7b4a80b6b288a532aa8907ef4eb28b0ce0a /src/include | |
| parent | ed69864350a59c51c8570900601ebd335956b638 (diff) | |
Add Bloom filter implementation.
A Bloom filter is a space-efficient, probabilistic data structure that
can be used to test set membership. Callers will sometimes incur false
positives, but never false negatives. The rate of false positives is a
function of the total number of elements and the amount of memory
available for the Bloom filter.
Two classic applications of Bloom filters are cache filtering, and data
synchronization testing. Any user of Bloom filters must accept the
possibility of false positives as a cost worth paying for the benefit in
space efficiency.
This commit adds a test harness extension module, test_bloomfilter. It
can be used to get a sense of how the Bloom filter implementation
performs under varying conditions.
This is infrastructure for the upcoming "heapallindexed" amcheck patch,
which verifies the consistency of a heap relation against one of its
indexes.
Author: Peter Geoghegan
Reviewed-By: Andrey Borodin, Michael Paquier, Thomas Munro, Andres Freund
Discussion: https://postgr.es/m/CAH2-Wzm5VmG7cu1N-H=nnS57wZThoSDQU+F5dewx3o84M+jY=g@mail.gmail.com
Diffstat (limited to 'src/include')
| -rw-r--r-- | src/include/lib/bloomfilter.h | 27 |
1 files changed, 27 insertions, 0 deletions
diff --git a/src/include/lib/bloomfilter.h b/src/include/lib/bloomfilter.h new file mode 100644 index 0000000000..6cbdd9bfd9 --- /dev/null +++ b/src/include/lib/bloomfilter.h @@ -0,0 +1,27 @@ +/*------------------------------------------------------------------------- + * + * bloomfilter.h + * Space-efficient set membership testing + * + * Copyright (c) 2018, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/include/lib/bloomfilter.h + * + *------------------------------------------------------------------------- + */ +#ifndef BLOOMFILTER_H +#define BLOOMFILTER_H + +typedef struct bloom_filter bloom_filter; + +extern bloom_filter *bloom_create(int64 total_elems, int bloom_work_mem, + uint64 seed); +extern void bloom_free(bloom_filter *filter); +extern void bloom_add_element(bloom_filter *filter, unsigned char *elem, + size_t len); +extern bool bloom_lacks_element(bloom_filter *filter, unsigned char *elem, + size_t len); +extern double bloom_prop_bits_set(bloom_filter *filter); + +#endif /* BLOOMFILTER_H */ |