Mercurial > prosody-modules

comparison mod_anti_spam/trie.lib.lua @ 6164:76ae646563ea

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Backed out changeset 94399ad6b5ab Unintentional committed changes
author Matthew Wild <mwild1@gmail.com>
date Thu, 06 Feb 2025 10:23:08 +0000
parents 94399ad6b5ab
children
comparison
equal deleted inserted replaced
6163:94399ad6b5ab 6164:76ae646563ea
118 if #existing == 0 then 118 if #existing == 0 then
119 self:remove(item); 119 self:remove(item);
120 end 120 end
121 end 121 end
122 122
123 local function find_match_in_descendents(node, item, len, i)
124 for child_byte, child_node in pairs(node) do
125 if type(child_byte) == "number" then
126 if child_node.terminal then
127 local bits = child_node.value;
128 for j = #bits, 1, -1 do
129 local b = bits[j]-((i-1)*8);
130 if b ~= 8 then
131 local mask = bit.bnot(2^b-1);
132 if bit.band(bit.bxor(c, child_byte), mask) == 0 then
133 return true;
134 end
135 end
136 end
137 else
138
139 end
140 end
141 end
142 return false;
143 end
144
145 --
146 function trie_methods:contains_ip(item) 123 function trie_methods:contains_ip(item)
147 item = item.packed; 124 item = item.packed;
148 local node = self.root; 125 local node = self.root;
149 local len = #item; 126 local len = #item;
150 for i = 1, len do 127 for i = 1, len do
153 end 130 end
154 131
155 local c = item:byte(i); 132 local c = item:byte(i);
156 local child = node[c]; 133 local child = node[c];
157 if not child then 134 if not child then
158 return find_match_in_descendents(node, item, len, i); 135 for child_byte, child_node in pairs(node) do
136 if type(child_byte) == "number" and child_node.terminal then
137 local bits = child_node.value;
138 for j = #bits, 1, -1 do
139 local b = bits[j]-((i-1)*8);
140 if b ~= 8 then
141 local mask = bit.bnot(2^b-1);
142 if bit.band(bit.bxor(c, child_byte), mask) == 0 then
143 return true;
144 end
145 end
146 end
147 end
148 end
149 return false;
159 end 150 end
160 node = child; 151 node = child;
161 end 152 end
162 end 153 end
163 --]]
164
165 --[[
166 function trie_methods:contains_ip(item)
167 item = item.packed
168 local node = self.root
169 local len = #item
170
171 print(string.byte(item, 1, 4))
172
173 local function search(node, index)
174 if node.terminal then
175 print("S", "TERM")
176 return true
177 end
178
179 if index > len then
180 print("S", "MAX LEN")
181 return false
182 end
183
184 local c = item:byte(index)
185 local child = node[c]
186
187 print("S", (" "):rep(index), ("item[%d] = %d, has_child = %s"):format(index, c, not not child));
188
189 if child then
190 -- Continue searching down the current path
191 return search(child, index + 1)
192 else
193 -- Check all children for a terminal node
194 for child_byte, child_node in pairs(node) do
195 if type(child_byte) == "number" and child_byte then
196 if search(child_node, index + 1) then
197 return true
198 end
199 end
200 end
201 end
202
203 return false
204 end
205
206 return search(node, 1)
207 end
208 --]]
209 154
210 local function new() 155 local function new()
211 return setmetatable({ 156 return setmetatable({
212 root = new_node(); 157 root = new_node();
213 }, trie_mt); 158 }, trie_mt);