A Bloom filter. */
| 22 | |
| 23 | /** A Bloom filter. */ |
| 24 | class BloomFilter |
| 25 | { |
| 26 | public: |
| 27 | |
| 28 | /** Constructor. */ |
| 29 | BloomFilter() : m_size(0), m_hashSeed(0), m_array(NULL) { } |
| 30 | |
| 31 | /** Constructor. */ |
| 32 | BloomFilter(size_t n, size_t hashSeed=0) : m_size(n), |
| 33 | m_hashSeed(hashSeed) |
| 34 | { |
| 35 | m_array = new char[(n + 7)/8](); |
| 36 | } |
| 37 | |
| 38 | ~BloomFilter() |
| 39 | { |
| 40 | delete[] m_array; |
| 41 | } |
| 42 | |
| 43 | /** Return the size of the bit array. */ |
| 44 | size_t size() const { return m_size; } |
| 45 | |
| 46 | /** Return the population count, i.e. the number of set bits. */ |
| 47 | size_t popcount() const |
| 48 | { |
| 49 | size_t count = 0; |
| 50 | size_t bytes = (m_size + 7) / 8; |
| 51 | size_t numInts = bytes / sizeof(uint64_t); |
| 52 | size_t leftOverBytes = bytes % sizeof(uint64_t); |
| 53 | uint64_t* intPtr = reinterpret_cast<uint64_t*>(m_array); |
| 54 | for (size_t i = 0; i < numInts; i++) { |
| 55 | count += ::popcount(intPtr[i]); |
| 56 | } |
| 57 | for (size_t i = (bytes - leftOverBytes)*8; i < m_size; i++) { |
| 58 | if ((*this)[i]) |
| 59 | count++; |
| 60 | } |
| 61 | return count; |
| 62 | } |
| 63 | |
| 64 | /** Return the estimated false positive rate */ |
| 65 | double FPR() const |
| 66 | { |
| 67 | return (double)popcount() / size(); |
| 68 | } |
| 69 | |
| 70 | /** Return whether the specified bit is set. */ |
| 71 | bool operator[](size_t i) const |
| 72 | { |
| 73 | assert(i < m_size); |
| 74 | return m_array[i / 8] & 1 << (7 - i % 8); |
| 75 | } |
| 76 | |
| 77 | /** Return whether the object is present in this set. */ |
| 78 | bool operator[](const Bloom::key_type& key) const |
| 79 | { |
| 80 | return (*this)[Bloom::hash(key, m_hashSeed) % m_size]; |
| 81 | } |