Mercurial > prosody-modules

annotate mod_anti_spam/trie.lib.lua @ 5899:694b62d8a82f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
various/README: Fix 'labels' metadata, should be a list
author Kim Alvefur <zash@zash.se>
date Sun, 05 May 2024 17:37:38 +0200
parents 259ffdbf8906
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
5859
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 };