author | Matthew Wild <mwild1@gmail.com> |
Tue, 16 Apr 2024 15:01:40 +0100 | |
changeset 5892 | 432efc39572f |
parent 5863 | 259ffdbf8906 |
permissions | -rw-r--r-- |
5863
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
1 |
local bit = require "prosody.util.bitcompat"; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
2 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
3 |
local trie_methods = {}; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
4 |
local trie_mt = { __index = trie_methods }; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
5 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
6 |
local function new_node() |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
7 |
return {}; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
8 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
9 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
10 |
function trie_methods:set(item, value) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
11 |
local node = self.root; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
12 |
for i = 1, #item do |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
13 |
local c = item:byte(i); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
14 |
if not node[c] then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
15 |
node[c] = new_node(); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
16 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
17 |
node = node[c]; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
18 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
19 |
node.terminal = true; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
20 |
node.value = value; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
21 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
22 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
23 |
local function _remove(node, item, i) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
24 |
if i > #item then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
25 |
if node.terminal then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
26 |
node.terminal = nil; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
27 |
node.value = nil; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
28 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
29 |
if next(node) ~= nil then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
30 |
return node; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
31 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
32 |
return nil; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
33 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
34 |
local c = item:byte(i); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
35 |
local child = node[c]; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
36 |
local ret; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
37 |
if child then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
38 |
ret = _remove(child, item, i+1); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
39 |
node[c] = ret; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
40 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
41 |
if ret == nil and next(node) == nil then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
42 |
return nil; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
43 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
44 |
return node; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
45 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
46 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
47 |
function trie_methods:remove(item) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
48 |
return _remove(self.root, item, 1); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
49 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
50 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
51 |
function trie_methods:get(item, partial) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
52 |
local value; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
53 |
local node = self.root; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
54 |
local len = #item; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
55 |
for i = 1, len do |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
56 |
if partial and node.terminal then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
57 |
value = node.value; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
58 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
59 |
local c = item:byte(i); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
60 |
node = node[c]; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
61 |
if not node then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
62 |
return value, i - 1; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
63 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
64 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
65 |
return node.value, len; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
66 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
67 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
68 |
function trie_methods:add(item) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
69 |
return self:set(item, true); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
70 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
71 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
72 |
function trie_methods:contains(item, partial) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
73 |
return self:get(item, partial) ~= nil; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
74 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
75 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
76 |
function trie_methods:longest_prefix(item) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
77 |
return select(2, self:get(item)); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
78 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
79 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
80 |
function trie_methods:add_subnet(item, bits) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
81 |
item = item.packed:sub(1, math.ceil(bits/8)); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
82 |
local existing = self:get(item); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
83 |
if not existing then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
84 |
existing = { bits }; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
85 |
return self:set(item, existing); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
86 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
87 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
88 |
-- Simple insertion sort |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
89 |
for i = 1, #existing do |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
90 |
local v = existing[i]; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
91 |
if v == bits then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
92 |
return; -- Already in there |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
93 |
elseif v > bits then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
94 |
table.insert(existing, v, i); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
95 |
return; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
96 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
97 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
98 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
99 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
100 |
function trie_methods:remove_subnet(item, bits) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
101 |
item = item.packed:sub(1, math.ceil(bits/8)); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
102 |
local existing = self:get(item); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
103 |
if not existing then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
104 |
return; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
105 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
106 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
107 |
-- Simple insertion sort |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
108 |
for i = 1, #existing do |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
109 |
local v = existing[i]; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
110 |
if v == bits then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
111 |
table.remove(existing, i); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
112 |
break; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
113 |
elseif v > bits then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
114 |
return; -- Stop search |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
115 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
116 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
117 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
118 |
if #existing == 0 then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
119 |
self:remove(item); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
120 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
121 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
122 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
123 |
function trie_methods:has_ip(item) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
124 |
item = item.packed; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
125 |
local node = self.root; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
126 |
local len = #item; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
127 |
for i = 1, len do |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
128 |
if node.terminal then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
129 |
return true; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
130 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
131 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
132 |
local c = item:byte(i); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
133 |
local child = node[c]; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
134 |
if not child then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
135 |
for child_byte, child_node in pairs(node) do |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
136 |
if type(child_byte) == "number" and child_node.terminal then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
137 |
local bits = child_node.value; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
138 |
for j = #bits, 1, -1 do |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
139 |
local b = bits[j]-((i-1)*8); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
140 |
if b ~= 8 then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
141 |
local mask = bit.bnot(2^b-1); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
142 |
if bit.band(bit.bxor(c, child_byte), mask) == 0 then |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
143 |
return true; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
144 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
145 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
146 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
147 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
148 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
149 |
return false; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
150 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
151 |
node = child; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
152 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
153 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
154 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
155 |
local function new() |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
156 |
return setmetatable({ |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
157 |
root = new_node(); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
158 |
}, trie_mt); |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
159 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
160 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
161 |
local function is_trie(o) |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
162 |
return getmetatable(o) == trie_mt; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
163 |
end |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
164 |
|
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
165 |
return { |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
166 |
new = new; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
167 |
is_trie = is_trie; |
259ffdbf8906
mod_anti_spam: New module for spam filtering (pre-alpha)
Matthew Wild <mwild1@gmail.com>
parents:
diff
changeset
|
168 |
}; |