Software /
code /
prosody-modules
Annotate
mod_anti_spam/trie.lib.lua @ 5884:fdff8cb54302
mod_report_forward: fix address detection when there are multiple field values
author | Stephen Paul Weber <singpolyma@singpolyma.net> |
---|---|
date | Mon, 11 Mar 2024 19:28:19 -0500 |
parent | 5883:259ffdbf8906 |
rev | line source |
---|---|
5883
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 }; |