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
|
#ifndef CONCURRENTBLOOMFILTER_H
#define CONCURRENTBLOOMFILTER_H
#ifndef _OPENMP
# error ConcurrentBloomFilter class requires a compiler that supports OpenMP
#endif
#include "config.h"
#include <vector>
#include <omp.h>
/**
* A wrapper class that makes a Bloom filter
* thread-safe.
*/
template <class BloomFilterType>
class ConcurrentBloomFilter
{
public:
/** Constructor */
ConcurrentBloomFilter(BloomFilterType& bloom, size_t numLocks,
size_t hashSeed=0) : m_bloom(bloom), m_locks(numLocks),
m_hashSeed(hashSeed)
{
m_windowSize = bloom.size() / numLocks;
// round down to the nearest byte boundary,
// because bytes that span locks will
// cause concurrency issues
m_windowSize -= m_windowSize % 8;
assert(numLocks < bloom.size());
for (size_t i = 0; i < m_locks.size(); i++)
omp_init_lock(&(m_locks.at(i)));
}
/** Destructor */
~ConcurrentBloomFilter()
{
for (size_t i = 0; i < m_locks.size(); i++)
omp_destroy_lock(&(m_locks.at(i)));
}
/** Return whether the specified bit is set. */
bool operator[](size_t i) const
{
assert(i < m_bloom.size());
bool bit;
getLock(i);
bit = m_bloom[i];
releaseLock(i);
return bit;
}
/** Return whether the object is present in this set. */
bool operator[](const Bloom::key_type& key) const
{
return *this[Bloom::hash(key, m_hashSeed) % m_bloom.size()];
}
/** Add the object with the specified index to this set. */
void insert(size_t index)
{
assert(index < m_bloom.size());
getLock(index);
m_bloom.insert(index);
releaseLock(index);
}
/** Add the object to this set. */
void insert(const Bloom::key_type& key)
{
insert(Bloom::hash(key, m_hashSeed) % m_bloom.size());
}
private:
void getLock(size_t bitIndex)
{
assert(bitIndex < m_bloom.size());
size_t lockIndex = std::min(bitIndex / m_windowSize, m_locks.size() - 1);
omp_set_lock(&(m_locks.at(lockIndex)));
}
void releaseLock(size_t bitIndex)
{
assert(bitIndex < m_bloom.size());
size_t lockIndex = std::min(bitIndex / m_windowSize, m_locks.size() - 1);
omp_unset_lock(&(m_locks.at(lockIndex)));
}
BloomFilterType& m_bloom;
std::vector<omp_lock_t> m_locks;
size_t m_hashSeed;
size_t m_windowSize;
};
#endif
|
