-
Notifications
You must be signed in to change notification settings - Fork 0
/
BloomFilter.h
130 lines (112 loc) · 3.15 KB
/
BloomFilter.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
#ifndef BLOOM_FILTER_H
#define BLOOM_FILTER_H
#include <vector>
#include <cmath>
#include "DatabaseMacros.h"
/**
* Bloom Filter Configurations options
*/
struct BloomFilterOptions {
/**
* Method used to set the Bloom filter parameters (number of bits and number of hash functions)
*/
std::string parameter_setting;
/**
* Configure bloom filter paramters to ensure given False positivity rate
*/
double false_positive_rate;
/**
* Bits per entry the bloom filter parameters should be configured to use
*/
int bits_per_entry;
};
/**
* This class represents a Bloom Filter
*/
class BloomFilter {
public:
/**
* Construct a new Bloom Filter object
*
* @param num_keys
* @param options
*/
BloomFilter(int num_keys, BloomFilterOptions options);
/**
* Given a vector of key-value pairs, insert all keys into the Bloom Filter
*
* @param pairs Key-Value pairs
*
* @return 0 if insert successful, -1 otherwose
*/
int insert_keys(std::vector<std::pair<long, long>> pairs);
/**
* Check if key was inserted into the Bloom Filter
*
* @param key The key to check
*
* @return true - The key may or may not have been inserted into the Bloom Filter, subject to false positivity rate
* @return false - The key was not inserted into the Bloom Filter
*/
bool contains_key(long key);
/**
* Convert the bits in a vector of long type representation
*
* Note: Unused function, used for Bloom Filter persistence which was not implemented
*
* @param arr
*
* @return 0 if insert successful, -1 otherwose
*/
int convert_bits_to_long_array(std::vector<unsigned long> &arr);
/**
* Read in the bits of the Bloom Filter from a vector of long types representation of the bits
*
* Note: Unused function, used for Bloom Filter persistence which was not implemented
*
* @param arr Vector of longs containing the bits in order
* @param num_bits_to_add Number of bits to read
*
* @return 0 if insert successful, -1 otherwose
*/
int load_bits(std::vector<unsigned long> arr, int num_bits_to_add);
/**
* Read in the seed values of the Hash functions
*
* @param arr Vector of seed values
* @param num_seed_values Number of seed values to read in
*
* @return 0 if insert successful, -1 otherwose
*/
int load_seed_values(std::vector<long> arr, int num_seed_values);
/**
* Number of bits the Bloom Filter is using
*/
int num_bits;
/**
* Number of hash functions the Bloom filter is using
*/
int num_hash_funcs;
/**
* Bits of the Bloom Filter
*/
std::vector<bool> bits;
/**
* Seed values of the hash functions used by the Bloom Filter
*/
std::vector<long> seed_values;
private:
/**
* Bloom Filter configurations
*/
BloomFilterOptions options;
/**
* Insert a single key into the Bloom Filter
*
* @param key The key to insert
*
* @return 0 if insert successful, -1 otherwose
*/
int insert_key(long key);
};
#endif