-
Notifications
You must be signed in to change notification settings - Fork 0
/
deletable_bf.go
66 lines (57 loc) · 1.91 KB
/
deletable_bf.go
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
package abloom
type DeletableBloom struct {
bloom *bloom
perRegionLen int
pallete []byte
}
// NewDeletableBF creates a deletable bloom filter of length `size` bytes
// and `hashSeeds` are the seed values for the murmur hash functions
// bloom will be initialized with len(hashSeeds) hash functions
// with provided seeds.
// if no hashSeeds are provided then 2 hash functions will be used
// with random seeds.
// numRegions are the number of regions in which the bloom filter needs to be split
// so as to make it deletable. For each region, one extra bit of memory will be allocated.
func NewDeletableBF(size int, hashSeeds []int, numRegions int) *DeletableBloom {
bf := &DeletableBloom{
perRegionLen: divCeil(size*8, numRegions),
pallete: make([]byte, divCeil(numRegions, 8)),
bloom: newBloom(size, hashSeeds),
}
return bf
}
// Put puts the element `x` in the deletable bloom filter
func (b *DeletableBloom) Put(x []byte) error {
_, unsetBits, err := b.bloom.put(x)
if err != nil {
return err
}
// updating the pallete, get the region number
for i := range unsetBits {
posReg := unsetBits[i] / b.perRegionLen
setBit(b.pallete, posReg)
}
return nil
}
// Check checks the existence of the element `x` in the bloom filter
func (b *DeletableBloom) Check(x []byte) (bool, error) {
return b.bloom.check(x)
}
// Delete possibly deletes the element `x` from the bloom filter the element `x`
// returns error if any and if the element `x` was deleted or not
func (b *DeletableBloom) Delete(x []byte) (bool, error) {
positions, err := b.bloom.positions(x)
if err != nil {
return false, err
}
// updating the pallete, get the region number
for i := range positions {
posReg := positions[i] / b.perRegionLen
bit := getBit(b.pallete, posReg)
// if pallet bit is 0 then clear the position from the filter
if bit == 0 {
resetBit(b.bloom.filter, positions[i])
}
}
return false, nil
}