Line data Source code
1 : /*
2 : Copyright (c) 2007-2016 Contributors as noted in the AUTHORS file
3 :
4 : This file is part of libzmq, the ZeroMQ core engine in C++.
5 :
6 : libzmq is free software; you can redistribute it and/or modify it under
7 : the terms of the GNU Lesser General Public License (LGPL) as published
8 : by the Free Software Foundation; either version 3 of the License, or
9 : (at your option) any later version.
10 :
11 : As a special exception, the Contributors give you permission to link
12 : this library with independent modules to produce an executable,
13 : regardless of the license terms of these independent modules, and to
14 : copy and distribute the resulting executable under terms of your choice,
15 : provided that you also meet, for each linked independent module, the
16 : terms and conditions of the license of that module. An independent
17 : module is a module which is not derived from or based on this library.
18 : If you modify this library, you must extend this exception to your
19 : version of the library.
20 :
21 : libzmq is distributed in the hope that it will be useful, but WITHOUT
22 : ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
23 : FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
24 : License for more details.
25 :
26 : You should have received a copy of the GNU Lesser General Public License
27 : along with this program. If not, see <http://www.gnu.org/licenses/>.
28 : */
29 :
30 : #include "precompiled.hpp"
31 : #include <stdlib.h>
32 :
33 : #include <new>
34 : #include <algorithm>
35 :
36 : #include "macros.hpp"
37 : #include "platform.hpp"
38 : #if defined ZMQ_HAVE_WINDOWS
39 : #include "windows.hpp"
40 : #endif
41 :
42 : #include "err.hpp"
43 : #include "trie.hpp"
44 :
45 3261 : zmq::trie_t::trie_t () :
46 : refcnt (0),
47 : min (0),
48 : count (0),
49 3351 : live_nodes (0)
50 : {
51 3261 : }
52 :
53 3351 : zmq::trie_t::~trie_t ()
54 : {
55 3351 : if (count == 1) {
56 72 : zmq_assert (next.node);
57 72 : LIBZMQ_DELETE(next.node);
58 : }
59 3279 : else if (count > 1) {
60 12 : for (unsigned short i = 0; i != count; ++i) {
61 12 : LIBZMQ_DELETE(next.table[i]);
62 : }
63 6 : free (next.table);
64 : }
65 3351 : }
66 :
67 216 : bool zmq::trie_t::add (unsigned char *prefix_, size_t size_)
68 : {
69 : // We are at the node corresponding to the prefix. We are done.
70 216 : if (!size_) {
71 120 : ++refcnt;
72 120 : return refcnt == 1;
73 : }
74 :
75 96 : unsigned char c = *prefix_;
76 96 : if (c < min || c >= min + count) {
77 :
78 : // The character is out of range of currently handled
79 : // characters. We have to extend the table.
80 90 : if (!count) {
81 84 : min = c;
82 84 : count = 1;
83 84 : next.node = NULL;
84 : }
85 : else
86 6 : if (count == 1) {
87 6 : unsigned char oldc = min;
88 6 : trie_t *oldp = next.node;
89 6 : count = (min < c ? c - min : min - c) + 1;
90 : next.table = (trie_t**)
91 6 : malloc (sizeof (trie_t*) * count);
92 6 : alloc_assert (next.table);
93 12 : for (unsigned short i = 0; i != count; ++i)
94 12 : next.table [i] = 0;
95 12 : min = std::min (min, c);
96 6 : next.table [oldc - min] = oldp;
97 : }
98 : else
99 0 : if (min < c) {
100 : // The new character is above the current character range.
101 0 : unsigned short old_count = count;
102 0 : count = c - min + 1;
103 : next.table = (trie_t**) realloc ((void*) next.table,
104 0 : sizeof (trie_t*) * count);
105 0 : zmq_assert (next.table);
106 0 : for (unsigned short i = old_count; i != count; i++)
107 0 : next.table [i] = NULL;
108 : }
109 : else {
110 :
111 : // The new character is below the current character range.
112 0 : unsigned short old_count = count;
113 0 : count = (min + old_count) - c;
114 : next.table = (trie_t**) realloc ((void*) next.table,
115 0 : sizeof (trie_t*) * count);
116 0 : zmq_assert (next.table);
117 0 : memmove (next.table + min - c, next.table,
118 0 : old_count * sizeof (trie_t*));
119 0 : for (unsigned short i = 0; i != min - c; i++)
120 0 : next.table [i] = NULL;
121 0 : min = c;
122 : }
123 : }
124 :
125 : // If next node does not exist, create one.
126 96 : if (count == 1) {
127 90 : if (!next.node) {
128 168 : next.node = new (std::nothrow) trie_t;
129 84 : alloc_assert (next.node);
130 84 : ++live_nodes;
131 84 : zmq_assert (live_nodes == 1);
132 : }
133 90 : return next.node->add (prefix_ + 1, size_ - 1);
134 : }
135 : else {
136 6 : if (!next.table [c - min]) {
137 12 : next.table [c - min] = new (std::nothrow) trie_t;
138 6 : alloc_assert (next.table [c - min]);
139 6 : ++live_nodes;
140 6 : zmq_assert (live_nodes > 1);
141 : }
142 6 : return next.table [c - min]->add (prefix_ + 1, size_ - 1);
143 : }
144 : }
145 :
146 24 : bool zmq::trie_t::rm (unsigned char *prefix_, size_t size_)
147 : {
148 : // TODO: Shouldn't an error be reported if the key does not exist?
149 24 : if (!size_) {
150 12 : if (!refcnt)
151 : return false;
152 12 : refcnt--;
153 12 : return refcnt == 0;
154 : }
155 12 : unsigned char c = *prefix_;
156 12 : if (!count || c < min || c >= min + count)
157 : return false;
158 :
159 : trie_t *next_node =
160 12 : count == 1 ? next.node : next.table [c - min];
161 :
162 12 : if (!next_node)
163 : return false;
164 :
165 12 : bool ret = next_node->rm (prefix_ + 1, size_ - 1);
166 :
167 : // Prune redundant nodes
168 12 : if (next_node->is_redundant ()) {
169 6 : LIBZMQ_DELETE(next_node);
170 6 : zmq_assert (count > 0);
171 :
172 6 : if (count == 1) {
173 : // The just pruned node is was the only live node
174 6 : next.node = 0;
175 6 : count = 0;
176 6 : --live_nodes;
177 6 : zmq_assert (live_nodes == 0);
178 : }
179 : else {
180 0 : next.table [c - min] = 0;
181 0 : zmq_assert (live_nodes > 1);
182 0 : --live_nodes;
183 :
184 : // Compact the table if possible
185 0 : if (live_nodes == 1) {
186 : // We can switch to using the more compact single-node
187 : // representation since the table only contains one live node
188 0 : trie_t *node = 0;
189 : // Since we always compact the table the pruned node must
190 : // either be the left-most or right-most ptr in the node
191 : // table
192 0 : if (c == min) {
193 : // The pruned node is the left-most node ptr in the
194 : // node table => keep the right-most node
195 0 : node = next.table [count - 1];
196 0 : min += count - 1;
197 : }
198 : else
199 0 : if (c == min + count - 1) {
200 : // The pruned node is the right-most node ptr in the
201 : // node table => keep the left-most node
202 0 : node = next.table [0];
203 : }
204 0 : zmq_assert (node);
205 0 : free (next.table);
206 0 : next.node = node;
207 0 : count = 1;
208 : }
209 : else
210 0 : if (c == min) {
211 : // We can compact the table "from the left".
212 : // Find the left-most non-null node ptr, which we'll use as
213 : // our new min
214 : unsigned char new_min = min;
215 0 : for (unsigned short i = 1; i < count; ++i) {
216 0 : if (next.table [i]) {
217 0 : new_min = i + min;
218 0 : break;
219 : }
220 : }
221 0 : zmq_assert (new_min != min);
222 :
223 0 : trie_t **old_table = next.table;
224 0 : zmq_assert (new_min > min);
225 0 : zmq_assert (count > new_min - min);
226 :
227 0 : count = count - (new_min - min);
228 0 : next.table = (trie_t**) malloc (sizeof (trie_t*) * count);
229 0 : alloc_assert (next.table);
230 :
231 0 : memmove (next.table, old_table + (new_min - min),
232 0 : sizeof (trie_t*) * count);
233 0 : free (old_table);
234 :
235 0 : min = new_min;
236 : }
237 : else
238 0 : if (c == min + count - 1) {
239 : // We can compact the table "from the right".
240 : // Find the right-most non-null node ptr, which we'll use to
241 : // determine the new table size
242 : unsigned short new_count = count;
243 0 : for (unsigned short i = 1; i < count; ++i) {
244 0 : if (next.table [count - 1 - i]) {
245 0 : new_count = count - i;
246 0 : break;
247 : }
248 : }
249 0 : zmq_assert (new_count != count);
250 0 : count = new_count;
251 :
252 0 : trie_t **old_table = next.table;
253 0 : next.table = (trie_t**) malloc (sizeof (trie_t*) * count);
254 0 : alloc_assert (next.table);
255 :
256 0 : memmove (next.table, old_table, sizeof (trie_t*) * count);
257 0 : free (old_table);
258 : }
259 : }
260 : }
261 12 : return ret;
262 : }
263 :
264 63387 : bool zmq::trie_t::check (unsigned char *data_, size_t size_)
265 : {
266 : // This function is on critical path. It deliberately doesn't use
267 : // recursion to get a bit better performance.
268 63387 : trie_t *current = this;
269 : while (true) {
270 :
271 : // We've found a corresponding subscription!
272 63480 : if (current->refcnt)
273 : return true;
274 :
275 : // We've checked all the data and haven't found matching subscription.
276 99 : if (!size_)
277 : return false;
278 :
279 : // If there's no corresponding slot for the first character
280 : // of the prefix, the message does not match.
281 99 : unsigned char c = *data_;
282 99 : if (c < current->min || c >= current->min + current->count)
283 : return false;
284 :
285 : // Move to the next character.
286 93 : if (current->count == 1)
287 93 : current = current->next.node;
288 : else {
289 0 : current = current->next.table [c - current->min];
290 0 : if (!current)
291 : return false;
292 : }
293 93 : data_++;
294 93 : size_--;
295 93 : }
296 : }
297 :
298 3260 : void zmq::trie_t::apply (void (*func_) (unsigned char *data_, size_t size_,
299 : void *arg_), void *arg_)
300 : {
301 3260 : unsigned char *buff = NULL;
302 3260 : apply_helper (&buff, 0, 0, func_, arg_);
303 3261 : free (buff);
304 3261 : }
305 :
306 3260 : void zmq::trie_t::apply_helper (
307 : unsigned char **buff_, size_t buffsize_, size_t maxbuffsize_,
308 : void (*func_) (unsigned char *data_, size_t size_, void *arg_), void *arg_)
309 : {
310 : // If this node is a subscription, apply the function.
311 3272 : if (refcnt)
312 45 : func_ (*buff_, buffsize_, arg_);
313 :
314 : // Adjust the buffer.
315 3273 : if (buffsize_ >= maxbuffsize_) {
316 3260 : maxbuffsize_ = buffsize_ + 256;
317 3260 : *buff_ = (unsigned char*) realloc (*buff_, maxbuffsize_);
318 3260 : zmq_assert (*buff_);
319 : }
320 :
321 : // If there are no subnodes in the trie, return.
322 3273 : if (count == 0)
323 : return;
324 :
325 : // If there's one subnode (optimisation).
326 12 : if (count == 1) {
327 12 : (*buff_) [buffsize_] = min;
328 12 : buffsize_++;
329 12 : next.node->apply_helper (buff_, buffsize_, maxbuffsize_, func_, arg_);
330 12 : return;
331 : }
332 :
333 : // If there are multiple subnodes.
334 0 : for (unsigned short c = 0; c != count; c++) {
335 0 : (*buff_) [buffsize_] = min + c;
336 0 : if (next.table [c])
337 : next.table [c]->apply_helper (buff_, buffsize_ + 1, maxbuffsize_,
338 0 : func_, arg_);
339 : }
340 : }
341 :
342 0 : bool zmq::trie_t::is_redundant () const
343 : {
344 12 : return refcnt == 0 && live_nodes == 0;
345 : }
|
