prosody-modules
06fbbd45ba75
mod_anti_spam/trie.lib.lua

Find changesets by keywords by author, files, the commit message, revision number or hash, or revset expression.

Software / code / prosody-modules

Annotate

mod_anti_spam/trie.lib.lua @ 6302:06fbbd45ba75

mod_cloud_notify: Readme: fix links and labels that were removed in the last commit diff --git a/mod_cloud_notify/README.md b/mod_cloud_notify/README.md --- a/mod_cloud_notify/README.md +++ b/mod_cloud_notify/README.md @@ -1,3 +1,9 @@ +---- +-labels: +-- 'Stage-Beta' +-summary: 'XEP-0357: Cloud push notifications' +---- + # Introduction This module enables support for sending "push notifications" to clients @@ -32,15 +38,15 @@ notification to your device. When your d it will display it or wake up the app so it can connect to XMPP and receive any pending messages. -This protocol is described for developers in \[XEP-0357: Push -Notifications\]. +This protocol is described for developers in [XEP-0357: Push +Notifications]. -For this module to work reliably, you must have \[mod_smacks\], -\[mod_mam\] and \[mod_carbons\] also enabled on your server. +For this module to work reliably, you must have [mod_smacks], +[mod_mam] and [mod_carbons] also enabled on your server. Some clients, notably Siskin and Snikket iOS need some additional extensions that are not currently defined in a standard XEP. To support -these clients, see \[mod_cloud_notify_extensions\]. +these clients, see [mod_cloud_notify_extensions]. # Configuration @@ -58,18 +64,18 @@ these clients, see \[mod_cloud_notify_ex # Internal design notes App servers are notified about offline messages, messages stored by -\[mod_mam\] or messages waiting in the smacks queue. The business rules +[mod_mam] or messages waiting in the smacks queue. The business rules outlined [here](//mail.jabber.org/pipermail/standards/2016-February/030925.html) are all honored[^2]. -To cooperate with \[mod_smacks\] this module consumes some events: +To cooperate with [mod_smacks] this module consumes some events: `smacks-ack-delayed`, `smacks-hibernation-start` and `smacks-hibernation-end`. These events allow this module to send out notifications for messages received while the session is hibernated by -\[mod_smacks\] or even when smacks acknowledgements for messages are +[mod_smacks] or even when smacks acknowledgements for messages are delayed by a certain amount of seconds configurable with the -\[mod_smacks\] setting `smacks_max_ack_delay`. +[mod_smacks] setting `smacks_max_ack_delay`. The `smacks_max_ack_delay` setting allows to send out notifications to clients which aren't already in smacks hibernation state (because the
author Menel <menel@snikket.de>
date Fri, 13 Jun 2025 10:44:37 +0200
parent 6192:76ae646563ea
child 6211:750d64c47ec6
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
6159
82a10e21b7f9 mod_anti_spam: prosody 0.12 compat
Menel <menel@snikket.de>
parents: 6118
diff changeset
1 local bit = require "util.bitcompat";
5883
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
6118
8338f42d2bc5 mod_anti_spam: Tweak trie method name (fixes traceback)
Matthew Wild <mwild1@gmail.com>
parents: 5883
diff changeset
123 function trie_methods:contains_ip(item)
5883
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
6192
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
135 for child_byte, child_node in pairs(node) do
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
136 if type(child_byte) == "number" and child_node.terminal then
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
137 local bits = child_node.value;
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
138 for j = #bits, 1, -1 do
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
139 local b = bits[j]-((i-1)*8);
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
140 if b ~= 8 then
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
141 local mask = bit.bnot(2^b-1);
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
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: 6191
diff changeset
143 return true;
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
144 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
145 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
146 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
147 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
148 end
76ae646563ea Backed out changeset 94399ad6b5ab
Matthew Wild <mwild1@gmail.com>
parents: 6191
diff changeset
149 return false;
5883
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 };