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
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
package cuckoo
import (
"bytes"
"encoding/gob"
)
const (
DefaultLoadFactor = 0.9
DefaultCapacity = 10000
)
type ScalableCuckooFilter struct {
filters []*Filter
loadFactor float32
//when scale(last filter size * loadFactor >= capacity) get new filter capacity
scaleFactor func(capacity uint) uint
}
type option func(*ScalableCuckooFilter)
type Store struct {
Bytes [][]byte
LoadFactor float32
}
/*
by default option the grow capacity is:
capacity , total
4096 4096
8192 12288
16384 28672
32768 61440
65536 126,976
*/
func NewScalableCuckooFilter(opts ...option) *ScalableCuckooFilter {
sfilter := new(ScalableCuckooFilter)
for _, opt := range opts {
opt(sfilter)
}
configure(sfilter)
return sfilter
}
func (sf *ScalableCuckooFilter) Lookup(data []byte) bool {
for _, filter := range sf.filters {
if filter.Lookup(data) {
return true
}
}
return false
}
func (sf *ScalableCuckooFilter) Reset() {
for _, filter := range sf.filters {
filter.Reset()
}
}
func (sf *ScalableCuckooFilter) Insert(data []byte) bool {
needScale := false
lastFilter := sf.filters[len(sf.filters)-1]
if (float32(lastFilter.count) / float32(len(lastFilter.buckets))) > sf.loadFactor {
needScale = true
} else {
b := lastFilter.Insert(data)
needScale = !b
}
if !needScale {
return true
}
newFilter := NewFilter(sf.scaleFactor(uint(len(lastFilter.buckets))))
sf.filters = append(sf.filters, newFilter)
return newFilter.Insert(data)
}
func (sf *ScalableCuckooFilter) InsertUnique(data []byte) bool {
if sf.Lookup(data) {
return false
}
return sf.Insert(data)
}
func (sf *ScalableCuckooFilter) Delete(data []byte) bool {
for _, filter := range sf.filters {
if filter.Delete(data) {
return true
}
}
return false
}
func (sf *ScalableCuckooFilter) Count() uint {
var sum uint
for _, filter := range sf.filters {
sum += filter.count
}
return sum
}
func (sf *ScalableCuckooFilter) Encode() []byte {
slice := make([][]byte, len(sf.filters))
for i, filter := range sf.filters {
encode := filter.Encode()
slice[i] = encode
}
store := &Store{
Bytes: slice,
LoadFactor: sf.loadFactor,
}
buf := bytes.NewBuffer(nil)
enc := gob.NewEncoder(buf)
err := enc.Encode(store)
if err != nil {
return nil
}
return buf.Bytes()
}
func (sf *ScalableCuckooFilter) DecodeWithParam(fBytes []byte, opts ...option) (*ScalableCuckooFilter, error) {
instance, err := DecodeScalableFilter(fBytes)
if err != nil {
return nil, err
}
for _, opt := range opts {
opt(instance)
}
return instance, nil
}
func DecodeScalableFilter(fBytes []byte) (*ScalableCuckooFilter, error) {
buf := bytes.NewBuffer(fBytes)
dec := gob.NewDecoder(buf)
store := &Store{}
err := dec.Decode(store)
if err != nil {
return nil, err
}
filterSize := len(store.Bytes)
instance := NewScalableCuckooFilter(func(filter *ScalableCuckooFilter) {
filter.filters = make([]*Filter, filterSize)
}, func(filter *ScalableCuckooFilter) {
filter.loadFactor = store.LoadFactor
})
for i, oneBytes := range store.Bytes {
filter, err := Decode(oneBytes)
if err != nil {
return nil, err
}
instance.filters[i] = filter
}
return instance, nil
}
func configure(sfilter *ScalableCuckooFilter) {
if sfilter.loadFactor == 0 {
sfilter.loadFactor = DefaultLoadFactor
}
if sfilter.scaleFactor == nil {
sfilter.scaleFactor = func(currentSize uint) uint {
return currentSize * bucketSize * 2
}
}
if sfilter.filters == nil {
initFilter := NewFilter(DefaultCapacity)
sfilter.filters = []*Filter{initFilter}
}
}
|
