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 "macros.hpp"
32#include "err.hpp"
33#include "trie.hpp"
34
35#include <stdlib.h>
36
37#include <new>
38#include <algorithm>
39
40zmq::trie_t::trie_t () : _refcnt (0), _min (0), _count (0), _live_nodes (0)
41{
42}
43
44zmq::trie_t::~trie_t ()
45{
46 if (_count == 1) {
47 zmq_assert (_next.node);
48 LIBZMQ_DELETE (_next.node);
49 } else if (_count > 1) {
50 for (unsigned short i = 0; i != _count; ++i) {
51 LIBZMQ_DELETE (_next.table[i]);
52 }
53 free (_next.table);
54 }
55}
56
57bool zmq::trie_t::add (unsigned char *prefix_, size_t size_)
58{
59 // We are at the node corresponding to the prefix. We are done.
60 if (!size_) {
61 ++_refcnt;
62 return _refcnt == 1;
63 }
64
65 const unsigned char c = *prefix_;
66 if (c < _min || c >= _min + _count) {
67 // The character is out of range of currently handled
68 // characters. We have to extend the table.
69 if (!_count) {
70 _min = c;
71 _count = 1;
72 _next.node = NULL;
73 } else if (_count == 1) {
74 const unsigned char oldc = _min;
75 trie_t *oldp = _next.node;
76 _count = (_min < c ? c - _min : _min - c) + 1;
77 _next.table =
78 static_cast<trie_t **> (malloc (sizeof (trie_t *) * _count));
79 alloc_assert (_next.table);
80 for (unsigned short i = 0; i != _count; ++i)
81 _next.table[i] = 0;
82 _min = std::min (_min, c);
83 _next.table[oldc - _min] = oldp;
84 } else if (_min < c) {
85 // The new character is above the current character range.
86 const unsigned short old_count = _count;
87 _count = c - _min + 1;
88 _next.table = static_cast<trie_t **> (
89 realloc (_next.table, sizeof (trie_t *) * _count));
90 zmq_assert (_next.table);
91 for (unsigned short i = old_count; i != _count; i++)
92 _next.table[i] = NULL;
93 } else {
94 // The new character is below the current character range.
95 const unsigned short old_count = _count;
96 _count = (_min + old_count) - c;
97 _next.table = static_cast<trie_t **> (
98 realloc (_next.table, sizeof (trie_t *) * _count));
99 zmq_assert (_next.table);
100 memmove (_next.table + _min - c, _next.table,
101 old_count * sizeof (trie_t *));
102 for (unsigned short i = 0; i != _min - c; i++)
103 _next.table[i] = NULL;
104 _min = c;
105 }
106 }
107
108 // If next node does not exist, create one.
109 if (_count == 1) {
110 if (!_next.node) {
111 _next.node = new (std::nothrow) trie_t;
112 alloc_assert (_next.node);
113 ++_live_nodes;
114 zmq_assert (_live_nodes == 1);
115 }
116 return _next.node->add (prefix_ + 1, size_ - 1);
117 }
118 if (!_next.table[c - _min]) {
119 _next.table[c - _min] = new (std::nothrow) trie_t;
120 alloc_assert (_next.table[c - _min]);
121 ++_live_nodes;
122 zmq_assert (_live_nodes > 1);
123 }
124 return _next.table[c - _min]->add (prefix_ + 1, size_ - 1);
125}
126
127bool zmq::trie_t::rm (unsigned char *prefix_, size_t size_)
128{
129 // TODO: Shouldn't an error be reported if the key does not exist?
130 if (!size_) {
131 if (!_refcnt)
132 return false;
133 _refcnt--;
134 return _refcnt == 0;
135 }
136 const unsigned char c = *prefix_;
137 if (!_count || c < _min || c >= _min + _count)
138 return false;
139
140 trie_t *next_node = _count == 1 ? _next.node : _next.table[c - _min];
141
142 if (!next_node)
143 return false;
144
145 const bool ret = next_node->rm (prefix_ + 1, size_ - 1);
146
147 // Prune redundant nodes
148 if (next_node->is_redundant ()) {
149 LIBZMQ_DELETE (next_node);
150 zmq_assert (_count > 0);
151
152 if (_count == 1) {
153 // The just pruned node is was the only live node
154 _next.node = 0;
155 _count = 0;
156 --_live_nodes;
157 zmq_assert (_live_nodes == 0);
158 } else {
159 _next.table[c - _min] = 0;
160 zmq_assert (_live_nodes > 1);
161 --_live_nodes;
162
163 // Compact the table if possible
164 if (_live_nodes == 1) {
165 // We can switch to using the more compact single-node
166 // representation since the table only contains one live node
167 trie_t *node = 0;
168 // Since we always compact the table the pruned node must
169 // either be the left-most or right-most ptr in the node
170 // table
171 if (c == _min) {
172 // The pruned node is the left-most node ptr in the
173 // node table => keep the right-most node
174 node = _next.table[_count - 1];
175 _min += _count - 1;
176 } else if (c == _min + _count - 1) {
177 // The pruned node is the right-most node ptr in the
178 // node table => keep the left-most node
179 node = _next.table[0];
180 }
181 zmq_assert (node);
182 free (_next.table);
183 _next.node = node;
184 _count = 1;
185 } else if (c == _min) {
186 // We can compact the table "from the left".
187 // Find the left-most non-null node ptr, which we'll use as
188 // our new min
189 unsigned char new_min = _min;
190 for (unsigned short i = 1; i < _count; ++i) {
191 if (_next.table[i]) {
192 new_min = i + _min;
193 break;
194 }
195 }
196 zmq_assert (new_min != _min);
197
198 trie_t **old_table = _next.table;
199 zmq_assert (new_min > _min);
200 zmq_assert (_count > new_min - _min);
201
202 _count = _count - (new_min - _min);
203 _next.table =
204 static_cast<trie_t **> (malloc (sizeof (trie_t *) * _count));
205 alloc_assert (_next.table);
206
207 memmove (_next.table, old_table + (new_min - _min),
208 sizeof (trie_t *) * _count);
209 free (old_table);
210
211 _min = new_min;
212 } else if (c == _min + _count - 1) {
213 // We can compact the table "from the right".
214 // Find the right-most non-null node ptr, which we'll use to
215 // determine the new table size
216 unsigned short new_count = _count;
217 for (unsigned short i = 1; i < _count; ++i) {
218 if (_next.table[_count - 1 - i]) {
219 new_count = _count - i;
220 break;
221 }
222 }
223 zmq_assert (new_count != _count);
224 _count = new_count;
225
226 trie_t **old_table = _next.table;
227 _next.table =
228 static_cast<trie_t **> (malloc (sizeof (trie_t *) * _count));
229 alloc_assert (_next.table);
230
231 memmove (_next.table, old_table, sizeof (trie_t *) * _count);
232 free (old_table);
233 }
234 }
235 }
236 return ret;
237}
238
239bool zmq::trie_t::check (unsigned char *data_, size_t size_)
240{
241 // This function is on critical path. It deliberately doesn't use
242 // recursion to get a bit better performance.
243 trie_t *current = this;
244 while (true) {
245 // We've found a corresponding subscription!
246 if (current->_refcnt)
247 return true;
248
249 // We've checked all the data and haven't found matching subscription.
250 if (!size_)
251 return false;
252
253 // If there's no corresponding slot for the first character
254 // of the prefix, the message does not match.
255 const unsigned char c = *data_;
256 if (c < current->_min || c >= current->_min + current->_count)
257 return false;
258
259 // Move to the next character.
260 if (current->_count == 1)
261 current = current->_next.node;
262 else {
263 current = current->_next.table[c - current->_min];
264 if (!current)
265 return false;
266 }
267 data_++;
268 size_--;
269 }
270}
271
272void zmq::trie_t::apply (
273 void (*func_) (unsigned char *data_, size_t size_, void *arg_), void *arg_)
274{
275 unsigned char *buff = NULL;
276 apply_helper (&buff, 0, 0, func_, arg_);
277 free (buff);
278}
279
280void zmq::trie_t::apply_helper (unsigned char **buff_,
281 size_t buffsize_,
282 size_t maxbuffsize_,
283 void (*func_) (unsigned char *data_,
284 size_t size_,
285 void *arg_),
286 void *arg_) const
287{
288 // If this node is a subscription, apply the function.
289 if (_refcnt)
290 func_ (*buff_, buffsize_, arg_);
291
292 // Adjust the buffer.
293 if (buffsize_ >= maxbuffsize_) {
294 maxbuffsize_ = buffsize_ + 256;
295 *buff_ = static_cast<unsigned char *> (realloc (*buff_, maxbuffsize_));
296 zmq_assert (*buff_);
297 }
298
299 // If there are no subnodes in the trie, return.
300 if (_count == 0)
301 return;
302
303 // If there's one subnode (optimisation).
304 if (_count == 1) {
305 (*buff_)[buffsize_] = _min;
306 buffsize_++;
307 _next.node->apply_helper (buff_, buffsize_, maxbuffsize_, func_, arg_);
308 return;
309 }
310
311 // If there are multiple subnodes.
312 for (unsigned short c = 0; c != _count; c++) {
313 (*buff_)[buffsize_] = _min + c;
314 if (_next.table[c])
315 _next.table[c]->apply_helper (buff_, buffsize_ + 1, maxbuffsize_,
316 func_, arg_);
317 }
318}
319
320bool zmq::trie_t::is_redundant () const
321{
322 return _refcnt == 0 && _live_nodes == 0;
323}
324