-
Notifications
You must be signed in to change notification settings - Fork 0
/
bloom.lua
58 lines (51 loc) · 1.25 KB
/
bloom.lua
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
local bitset=require 'bitset'
local crc32 = require 'crc32'
local function parse(s)
local bits, hashes, set_s = s:match('^bits=(%d+);hashes=(%d+);set={(.*),}$')
local set = {}
for k, v in set_s:gmatch("%[(%d+)%]=(%d+)") do
set[tonumber(k)] = tonumber(v)
end
return {
bits=bits,
hashes=hashes,
set=set,
}
end
return function (bits, hashes)
local set
if type(bits)=='string' then
-- serialized filter pased as parameter, regenerate
local from = parse(bits)
set = bitset(from.set)
hashes = from.hashes
bits = from.bits
else
set = bitset()
end
local filter = {
add = function(v)
for i = 1, hashes do
local h = crc32(tostring(i)..v)
set[h%bits] = true
end
end,
test = function(v)
for i = 1, hashes do
local h = crc32(tostring(i)..v)
if set[h%bits] == false then return false end
end
return true
end,
serialize = function()
local s=''
s=s..'bits='..tostring(bits)..';hashes='..tostring(hashes)..';set={'
for k, v in pairs(set.set) do
s=s..'['..string.format('%.0f',k)..']='..string.format('%.0f',v)..','--print ('s:',k,v)
end
s=s..'}'
return s
end,
}
return filter
end