1/*
2Copyright (c) 2018 Contributors as noted in the AUTHORS file
3
4This file is part of libzmq, the ZeroMQ core engine in C++.
5
6libzmq is free software; you can redistribute it and/or modify it under
7the terms of the GNU Lesser General Public License (LGPL) as published
8by the Free Software Foundation; either version 3 of the License, or
9(at your option) any later version.
10
11As a special exception, the Contributors give you permission to link
12this library with independent modules to produce an executable,
13regardless of the license terms of these independent modules, and to
14copy and distribute the resulting executable under terms of your choice,
15provided that you also meet, for each linked independent module, the
16terms and conditions of the license of that module. An independent
17module is a module which is not derived from or based on this library.
18If you modify this library, you must extend this exception to your
19version of the library.
20
21libzmq is distributed in the hope that it will be useful, but WITHOUT
22ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
23FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
24License for more details.
25
26You should have received a copy of the GNU Lesser General Public License
27along with this program. If not, see <http://www.gnu.org/licenses/>.
28*/
29
30#ifndef __ZMQ_GENERIC_MTRIE_IMPL_HPP_INCLUDED__
31#define __ZMQ_GENERIC_MTRIE_IMPL_HPP_INCLUDED__
32
33
34#include <stdlib.h>
35
36#include <new>
37#include <algorithm>
38
39#include "err.hpp"
40#include "macros.hpp"
41#include "generic_mtrie.hpp"
42
43template <typename T>
44zmq::generic_mtrie_t<T>::generic_mtrie_t () :
45 _pipes (0),
46 _min (0),
47 _count (0),
48 _live_nodes (0)
49{
50}
51
52template <typename T> zmq::generic_mtrie_t<T>::~generic_mtrie_t ()
53{
54 LIBZMQ_DELETE (_pipes);
55
56 if (_count == 1) {
57 zmq_assert (_next.node);
58 LIBZMQ_DELETE (_next.node);
59 } else if (_count > 1) {
60 for (unsigned short i = 0; i != _count; ++i) {
61 LIBZMQ_DELETE (_next.table[i]);
62 }
63 free (_next.table);
64 }
65}
66
67template <typename T>
68bool zmq::generic_mtrie_t<T>::add (prefix_t prefix_,
69 size_t size_,
70 value_t *pipe_)
71{
72 return add_helper (prefix_, size_, pipe_);
73}
74
75template <typename T>
76bool zmq::generic_mtrie_t<T>::add_helper (prefix_t prefix_,
77 size_t size_,
78 value_t *pipe_)
79{
80 // We are at the node corresponding to the prefix. We are done.
81 if (!size_) {
82 const bool result = !_pipes;
83 if (!_pipes) {
84 _pipes = new (std::nothrow) pipes_t;
85 alloc_assert (_pipes);
86 }
87 _pipes->insert (pipe_);
88 return result;
89 }
90
91 const unsigned char c = *prefix_;
92 if (c < _min || c >= _min + _count) {
93 // The character is out of range of currently handled
94 // characters. We have to extend the table.
95 if (!_count) {
96 _min = c;
97 _count = 1;
98 _next.node = NULL;
99 } else if (_count == 1) {
100 const unsigned char oldc = _min;
101 generic_mtrie_t *oldp = _next.node;
102 _count = (_min < c ? c - _min : _min - c) + 1;
103 _next.table = static_cast<generic_mtrie_t **> (
104 malloc (sizeof (generic_mtrie_t *) * _count));
105 alloc_assert (_next.table);
106 for (unsigned short i = 0; i != _count; ++i)
107 _next.table[i] = 0;
108 _min = std::min (_min, c);
109 _next.table[oldc - _min] = oldp;
110 } else if (_min < c) {
111 // The new character is above the current character range.
112 const unsigned short old_count = _count;
113 _count = c - _min + 1;
114 _next.table = static_cast<generic_mtrie_t **> (
115 realloc (_next.table, sizeof (generic_mtrie_t *) * _count));
116 alloc_assert (_next.table);
117 for (unsigned short i = old_count; i != _count; i++)
118 _next.table[i] = NULL;
119 } else {
120 // The new character is below the current character range.
121 const unsigned short old_count = _count;
122 _count = (_min + old_count) - c;
123 _next.table = static_cast<generic_mtrie_t **> (
124 realloc (_next.table, sizeof (generic_mtrie_t *) * _count));
125 alloc_assert (_next.table);
126 memmove (_next.table + _min - c, _next.table,
127 old_count * sizeof (generic_mtrie_t *));
128 for (unsigned short i = 0; i != _min - c; i++)
129 _next.table[i] = NULL;
130 _min = c;
131 }
132 }
133
134 // If next node does not exist, create one.
135 if (_count == 1) {
136 if (!_next.node) {
137 _next.node = new (std::nothrow) generic_mtrie_t;
138 alloc_assert (_next.node);
139 ++_live_nodes;
140 }
141 return _next.node->add_helper (prefix_ + 1, size_ - 1, pipe_);
142 }
143 if (!_next.table[c - _min]) {
144 _next.table[c - _min] = new (std::nothrow) generic_mtrie_t;
145 alloc_assert (_next.table[c - _min]);
146 ++_live_nodes;
147 }
148 return _next.table[c - _min]->add_helper (prefix_ + 1, size_ - 1, pipe_);
149}
150
151
152template <typename T>
153template <typename Arg>
154void zmq::generic_mtrie_t<T>::rm (value_t *pipe_,
155 void (*func_) (prefix_t data_,
156 size_t size_,
157 Arg arg_),
158 Arg arg_,
159 bool call_on_uniq_)
160{
161 unsigned char *buff = NULL;
162 rm_helper (pipe_, &buff, 0, 0, func_, arg_, call_on_uniq_);
163 free (buff);
164}
165
166template <typename T>
167template <typename Arg>
168void zmq::generic_mtrie_t<T>::rm_helper (value_t *pipe_,
169 unsigned char **buff_,
170 size_t buffsize_,
171 size_t maxbuffsize_,
172 void (*func_) (prefix_t data_,
173 size_t size_,
174 Arg arg_),
175 Arg arg_,
176 bool call_on_uniq_)
177{
178 // Remove the subscription from this node.
179 if (_pipes && _pipes->erase (pipe_)) {
180 if (!call_on_uniq_ || _pipes->empty ()) {
181 func_ (*buff_, buffsize_, arg_);
182 }
183
184 if (_pipes->empty ()) {
185 LIBZMQ_DELETE (_pipes);
186 }
187 }
188
189 // Adjust the buffer.
190 if (buffsize_ >= maxbuffsize_) {
191 maxbuffsize_ = buffsize_ + 256;
192 *buff_ = static_cast<unsigned char *> (realloc (*buff_, maxbuffsize_));
193 alloc_assert (*buff_);
194 }
195
196 switch (_count) {
197 case 0:
198 // If there are no subnodes in the trie, return.
199 break;
200 case 1:
201 // If there's one subnode (optimisation).
202
203 (*buff_)[buffsize_] = _min;
204 buffsize_++;
205 _next.node->rm_helper (pipe_, buff_, buffsize_, maxbuffsize_, func_,
206 arg_, call_on_uniq_);
207
208 // Prune the node if it was made redundant by the removal
209 if (_next.node->is_redundant ()) {
210 LIBZMQ_DELETE (_next.node);
211 _count = 0;
212 --_live_nodes;
213 zmq_assert (_live_nodes == 0);
214 }
215 break;
216 default:
217 // If there are multiple subnodes.
218 rm_helper_multiple_subnodes (buff_, buffsize_, maxbuffsize_, func_,
219 arg_, call_on_uniq_, pipe_);
220 break;
221 }
222}
223
224template <typename T>
225template <typename Arg>
226void zmq::generic_mtrie_t<T>::rm_helper_multiple_subnodes (
227 unsigned char **buff_,
228 size_t buffsize_,
229 size_t maxbuffsize_,
230 void (*func_) (prefix_t data_, size_t size_, Arg arg_),
231 Arg arg_,
232 bool call_on_uniq_,
233 value_t *pipe_)
234{
235 // New min non-null character in the node table after the removal
236 unsigned char new_min = _min + _count - 1;
237 // New max non-null character in the node table after the removal
238 unsigned char new_max = _min;
239 for (unsigned short c = 0; c != _count; c++) {
240 (*buff_)[buffsize_] = _min + c;
241 if (_next.table[c]) {
242 _next.table[c]->rm_helper (pipe_, buff_, buffsize_ + 1,
243 maxbuffsize_, func_, arg_,
244 call_on_uniq_);
245
246 // Prune redundant nodes from the mtrie
247 if (_next.table[c]->is_redundant ()) {
248 LIBZMQ_DELETE (_next.table[c]);
249
250 zmq_assert (_live_nodes > 0);
251 --_live_nodes;
252 } else {
253 // The node is not redundant, so it's a candidate for being
254 // the new min/max node.
255 //
256 // We loop through the node array from left to right, so the
257 // first non-null, non-redundant node encountered is the new
258 // minimum index. Conversely, the last non-redundant, non-null
259 // node encountered is the new maximum index.
260 if (c + _min < new_min)
261 new_min = c + _min;
262 if (c + _min > new_max)
263 new_max = c + _min;
264 }
265 }
266 }
267
268 zmq_assert (_count > 1);
269
270 // Free the node table if it's no longer used.
271 switch (_live_nodes) {
272 case 0:
273 free (_next.table);
274 _next.table = NULL;
275 _count = 0;
276 break;
277 case 1:
278 // Compact the node table if possible
279
280 // If there's only one live node in the table we can
281 // switch to using the more compact single-node
282 // representation
283 zmq_assert (new_min == new_max);
284 zmq_assert (new_min >= _min && new_min < _min + _count);
285 {
286 generic_mtrie_t *node = _next.table[new_min - _min];
287 zmq_assert (node);
288 free (_next.table);
289 _next.node = node;
290 }
291 _count = 1;
292 _min = new_min;
293 break;
294 default:
295 if (new_min > _min || new_max < _min + _count - 1) {
296 zmq_assert (new_max - new_min + 1 > 1);
297
298 generic_mtrie_t **old_table = _next.table;
299 zmq_assert (new_min > _min || new_max < _min + _count - 1);
300 zmq_assert (new_min >= _min);
301 zmq_assert (new_max <= _min + _count - 1);
302 zmq_assert (new_max - new_min + 1 < _count);
303
304 _count = new_max - new_min + 1;
305 _next.table = static_cast<generic_mtrie_t **> (
306 malloc (sizeof (generic_mtrie_t *) * _count));
307 alloc_assert (_next.table);
308
309 memmove (_next.table, old_table + (new_min - _min),
310 sizeof (generic_mtrie_t *) * _count);
311 free (old_table);
312
313 _min = new_min;
314 }
315 }
316}
317template <typename T>
318typename zmq::generic_mtrie_t<T>::rm_result
319zmq::generic_mtrie_t<T>::rm (prefix_t prefix_, size_t size_, value_t *pipe_)
320{
321 return rm_helper (prefix_, size_, pipe_);
322}
323
324template <typename T>
325typename zmq::generic_mtrie_t<T>::rm_result zmq::generic_mtrie_t<T>::rm_helper (
326 prefix_t prefix_, size_t size_, value_t *pipe_)
327{
328 if (!size_) {
329 if (!_pipes)
330 return not_found;
331
332 typename pipes_t::size_type erased = _pipes->erase (pipe_);
333 if (_pipes->empty ()) {
334 zmq_assert (erased == 1);
335 LIBZMQ_DELETE (_pipes);
336 return last_value_removed;
337 }
338 return (erased == 1) ? values_remain : not_found;
339 }
340
341 const unsigned char c = *prefix_;
342 if (!_count || c < _min || c >= _min + _count)
343 return not_found;
344
345 generic_mtrie_t *next_node =
346 _count == 1 ? _next.node : _next.table[c - _min];
347
348 if (!next_node)
349 return not_found;
350
351 const rm_result ret = next_node->rm_helper (prefix_ + 1, size_ - 1, pipe_);
352
353 if (next_node->is_redundant ()) {
354 LIBZMQ_DELETE (next_node);
355 zmq_assert (_count > 0);
356
357 if (_count == 1) {
358 _next.node = 0;
359 _count = 0;
360 --_live_nodes;
361 zmq_assert (_live_nodes == 0);
362 } else {
363 _next.table[c - _min] = 0;
364 zmq_assert (_live_nodes > 1);
365 --_live_nodes;
366
367 // Compact the table if possible
368 if (_live_nodes == 1) {
369 // If there's only one live node in the table we can
370 // switch to using the more compact single-node
371 // representation
372 unsigned short i;
373 for (i = 0; i < _count; ++i)
374 if (_next.table[i])
375 break;
376
377 zmq_assert (i < _count);
378 _min += i;
379 _count = 1;
380 generic_mtrie_t *oldp = _next.table[i];
381 free (_next.table);
382 _next.node = oldp;
383 } else if (c == _min) {
384 // We can compact the table "from the left"
385 unsigned short i;
386 for (i = 1; i < _count; ++i)
387 if (_next.table[i])
388 break;
389
390 zmq_assert (i < _count);
391 _min += i;
392 _count -= i;
393 generic_mtrie_t **old_table = _next.table;
394 _next.table = static_cast<generic_mtrie_t **> (
395 malloc (sizeof (generic_mtrie_t *) * _count));
396 alloc_assert (_next.table);
397 memmove (_next.table, old_table + i,
398 sizeof (generic_mtrie_t *) * _count);
399 free (old_table);
400 } else if (c == _min + _count - 1) {
401 // We can compact the table "from the right"
402 unsigned short i;
403 for (i = 1; i < _count; ++i)
404 if (_next.table[_count - 1 - i])
405 break;
406
407 zmq_assert (i < _count);
408 _count -= i;
409 generic_mtrie_t **old_table = _next.table;
410 _next.table = static_cast<generic_mtrie_t **> (
411 malloc (sizeof (generic_mtrie_t *) * _count));
412 alloc_assert (_next.table);
413 memmove (_next.table, old_table,
414 sizeof (generic_mtrie_t *) * _count);
415 free (old_table);
416 }
417 }
418 }
419
420 return ret;
421}
422
423template <typename T>
424template <typename Arg>
425void zmq::generic_mtrie_t<T>::match (prefix_t data_,
426 size_t size_,
427 void (*func_) (value_t *pipe_, Arg arg_),
428 Arg arg_)
429{
430 generic_mtrie_t *current = this;
431 while (true) {
432 // Signal the pipes attached to this node.
433 if (current->_pipes) {
434 for (typename pipes_t::iterator it = current->_pipes->begin ();
435 it != current->_pipes->end (); ++it)
436 func_ (*it, arg_);
437 }
438
439 // If we are at the end of the message, there's nothing more to match.
440 if (!size_)
441 break;
442
443 // If there are no subnodes in the trie, return.
444 if (current->_count == 0)
445 break;
446
447 // If there's one subnode (optimisation).
448 if (current->_count == 1) {
449 if (data_[0] != current->_min)
450 break;
451 current = current->_next.node;
452 data_++;
453 size_--;
454 continue;
455 }
456
457 // If there are multiple subnodes.
458 if (data_[0] < current->_min
459 || data_[0] >= current->_min + current->_count)
460 break;
461 if (!current->_next.table[data_[0] - current->_min])
462 break;
463 current = current->_next.table[data_[0] - current->_min];
464 data_++;
465 size_--;
466 }
467}
468
469template <typename T> bool zmq::generic_mtrie_t<T>::is_redundant () const
470{
471 return !_pipes && _live_nodes == 0;
472}
473
474
475#endif
476