annotate mod_anti_spam/trie.lib.lua @ 6319:04c3273cb81f

mod_auth_cyrus: Add empty 'profile' table to SASL handler objects This is for compatibility with Prosody's built-in util.sasl objects. A SASL profile table usually includes methods supported by the backend, which can be used by SASL mechanism handlers to perform operations (such as testing the password). It also optionally contains a 'cb' field with channel binding method handlers. The Cyrus backend doesn't support channel binding, and doesn't have the same concept of auth backend methods (it handles all that internally, and Prosody has no insight or control over it). Thus, we create an empty profile which informs Prosody that the SASL handler does not support any of the auth or channel binding methods. Some features will not work, but they didn't work anyway. This just makes it explicit. This fixes a traceback in mod_sasl2_fast, which expected SASL handlers to always contain a 'profile' field.
author Matthew Wild <mwild1@gmail.com>
date Thu, 04 Sep 2025 10:14:46 +0100
parents 76ae646563ea
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6131
82a10e21b7f9 mod_anti_spam: prosody 0.12 compat
Menel <menel@snikket.de>
parents: 6090
diff changeset
1 local bit = require "util.bitcompat";
5859
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
6090
8338f42d2bc5 mod_anti_spam: Tweak trie method name (fixes traceback)
Matthew Wild <mwild1@gmail.com>
parents: 5859
diff changeset
123 function trie_methods:contains_ip(item)
5859
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
6164
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
135 for child_byte, child_node in pairs(node) do
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
136 if type(child_byte) == "number" and child_node.terminal then
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
137 local bits = child_node.value;
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
138 for j = #bits, 1, -1 do
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
139 local b = bits[j]-((i-1)*8);
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
140 if b ~= 8 then
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
141 local mask = bit.bnot(2^b-1);
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
142 if bit.band(bit.bxor(c, child_byte), mask) == 0 then
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
143 return true;
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
144 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
145 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
146 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
147 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
148 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6163
diff changeset
149 return false;
5859
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 };