generic_mtrie_impl.hpp 16 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
/*
Copyright (c) 2018 Contributors as noted in the AUTHORS file

This file is part of libzmq, the ZeroMQ core engine in C++.

libzmq is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License (LGPL) as published
by the Free Software Foundation; either version 3 of the License, or
(at your option) any later version.

As a special exception, the Contributors give you permission to link
this library with independent modules to produce an executable,
regardless of the license terms of these independent modules, and to
copy and distribute the resulting executable under terms of your choice,
provided that you also meet, for each linked independent module, the
terms and conditions of the license of that module. An independent
module is a module which is not derived from or based on this library.
If you modify this library, you must extend this exception to your
version of the library.

libzmq is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
License for more details.

You should have received a copy of the GNU Lesser General Public License
along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef __ZMQ_GENERIC_MTRIE_IMPL_HPP_INCLUDED__
#define __ZMQ_GENERIC_MTRIE_IMPL_HPP_INCLUDED__


#include <stdlib.h>

#include <new>
#include <algorithm>

#include "err.hpp"
#include "macros.hpp"
#include "generic_mtrie.hpp"

template <typename T>
zmq::generic_mtrie_t<T>::generic_mtrie_t () :
45 46 47 48
    _pipes (0),
    _min (0),
    _count (0),
    _live_nodes (0)
49 50 51 52 53
{
}

template <typename T> zmq::generic_mtrie_t<T>::~generic_mtrie_t ()
{
54 55 56 57 58 59 60 61
    LIBZMQ_DELETE (_pipes);

    if (_count == 1) {
        zmq_assert (_next.node);
        LIBZMQ_DELETE (_next.node);
    } else if (_count > 1) {
        for (unsigned short i = 0; i != _count; ++i) {
            LIBZMQ_DELETE (_next.table[i]);
62
        }
63
        free (_next.table);
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
    }
}

template <typename T>
bool zmq::generic_mtrie_t<T>::add (prefix_t prefix_,
                                   size_t size_,
                                   value_t *pipe_)
{
    return add_helper (prefix_, size_, pipe_);
}

template <typename T>
bool zmq::generic_mtrie_t<T>::add_helper (prefix_t prefix_,
                                          size_t size_,
                                          value_t *pipe_)
{
    //  We are at the node corresponding to the prefix. We are done.
    if (!size_) {
82
        const bool result = !_pipes;
83 84 85
        if (!_pipes) {
            _pipes = new (std::nothrow) pipes_t;
            alloc_assert (_pipes);
86
        }
87
        _pipes->insert (pipe_);
88 89 90
        return result;
    }

91
    const unsigned char c = *prefix_;
92
    if (c < _min || c >= _min + _count) {
93 94
        //  The character is out of range of currently handled
        //  characters. We have to extend the table.
95 96 97 98 99
        if (!_count) {
            _min = c;
            _count = 1;
            _next.node = NULL;
        } else if (_count == 1) {
100
            const unsigned char oldc = _min;
101 102
            generic_mtrie_t *oldp = _next.node;
            _count = (_min < c ? c - _min : _min - c) + 1;
103 104
            _next.table = static_cast<generic_mtrie_t **> (
              malloc (sizeof (generic_mtrie_t *) * _count));
105 106 107 108 109 110
            alloc_assert (_next.table);
            for (unsigned short i = 0; i != _count; ++i)
                _next.table[i] = 0;
            _min = std::min (_min, c);
            _next.table[oldc - _min] = oldp;
        } 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 115
            _next.table = static_cast<generic_mtrie_t **> (
              realloc (_next.table, sizeof (generic_mtrie_t *) * _count));
116 117 118
            alloc_assert (_next.table);
            for (unsigned short i = old_count; i != _count; i++)
                _next.table[i] = NULL;
119 120
        } else {
            //  The new character is below the current character range.
121
            const unsigned short old_count = _count;
122
            _count = (_min + old_count) - c;
123 124
            _next.table = static_cast<generic_mtrie_t **> (
              realloc (_next.table, sizeof (generic_mtrie_t *) * _count));
125 126
            alloc_assert (_next.table);
            memmove (_next.table + _min - c, _next.table,
127
                     old_count * sizeof (generic_mtrie_t *));
128 129 130
            for (unsigned short i = 0; i != _min - c; i++)
                _next.table[i] = NULL;
            _min = c;
131 132 133 134
        }
    }

    //  If next node does not exist, create one.
135 136 137 138 139
    if (_count == 1) {
        if (!_next.node) {
            _next.node = new (std::nothrow) generic_mtrie_t;
            alloc_assert (_next.node);
            ++_live_nodes;
140
        }
141
        return _next.node->add_helper (prefix_ + 1, size_ - 1, pipe_);
142
    }
143 144 145 146
    if (!_next.table[c - _min]) {
        _next.table[c - _min] = new (std::nothrow) generic_mtrie_t;
        alloc_assert (_next.table[c - _min]);
        ++_live_nodes;
147
    }
148
    return _next.table[c - _min]->add_helper (prefix_ + 1, size_ - 1, pipe_);
149 150 151 152
}


template <typename T>
153
template <typename Arg>
154 155 156
void zmq::generic_mtrie_t<T>::rm (value_t *pipe_,
                                  void (*func_) (prefix_t data_,
                                                 size_t size_,
157 158
                                                 Arg arg_),
                                  Arg arg_,
159 160 161 162 163 164 165 166
                                  bool call_on_uniq_)
{
    unsigned char *buff = NULL;
    rm_helper (pipe_, &buff, 0, 0, func_, arg_, call_on_uniq_);
    free (buff);
}

template <typename T>
167
template <typename Arg>
168
void zmq::generic_mtrie_t<T>::rm_helper (value_t *pipe_,
169 170 171 172 173
                                         unsigned char **buff_,
                                         size_t buffsize_,
                                         size_t maxbuffsize_,
                                         void (*func_) (prefix_t data_,
                                                        size_t size_,
174 175
                                                        Arg arg_),
                                         Arg arg_,
176 177 178
                                         bool call_on_uniq_)
{
    //  Remove the subscription from this node.
179 180
    if (_pipes && _pipes->erase (pipe_)) {
        if (!call_on_uniq_ || _pipes->empty ()) {
181 182 183
            func_ (*buff_, buffsize_, arg_);
        }

184 185
        if (_pipes->empty ()) {
            LIBZMQ_DELETE (_pipes);
186 187 188 189 190 191
        }
    }

    //  Adjust the buffer.
    if (buffsize_ >= maxbuffsize_) {
        maxbuffsize_ = buffsize_ + 256;
192
        *buff_ = static_cast<unsigned char *> (realloc (*buff_, maxbuffsize_));
193 194 195
        alloc_assert (*buff_);
    }

196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
    switch (_count) {
        case 0:
            //  If there are no subnodes in the trie, return.
            break;
        case 1:
            //  If there's one subnode (optimisation).

            (*buff_)[buffsize_] = _min;
            buffsize_++;
            _next.node->rm_helper (pipe_, buff_, buffsize_, maxbuffsize_, func_,
                                   arg_, call_on_uniq_);

            //  Prune the node if it was made redundant by the removal
            if (_next.node->is_redundant ()) {
                LIBZMQ_DELETE (_next.node);
                _count = 0;
                --_live_nodes;
                zmq_assert (_live_nodes == 0);
            }
            break;
        default:
            //  If there are multiple subnodes.
            rm_helper_multiple_subnodes (buff_, buffsize_, maxbuffsize_, func_,
                                         arg_, call_on_uniq_, pipe_);
            break;
221
    }
222
}
223

224 225 226 227 228 229 230 231 232 233 234
template <typename T>
template <typename Arg>
void zmq::generic_mtrie_t<T>::rm_helper_multiple_subnodes (
  unsigned char **buff_,
  size_t buffsize_,
  size_t maxbuffsize_,
  void (*func_) (prefix_t data_, size_t size_, Arg arg_),
  Arg arg_,
  bool call_on_uniq_,
  value_t *pipe_)
{
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 239 240 241 242 243 244
    unsigned char new_max = _min;
    for (unsigned short c = 0; c != _count; c++) {
        (*buff_)[buffsize_] = _min + c;
        if (_next.table[c]) {
            _next.table[c]->rm_helper (pipe_, buff_, buffsize_ + 1,
                                       maxbuffsize_, func_, arg_,
                                       call_on_uniq_);
245 246

            //  Prune redundant nodes from the mtrie
247 248
            if (_next.table[c]->is_redundant ()) {
                LIBZMQ_DELETE (_next.table[c]);
249

250 251
                zmq_assert (_live_nodes > 0);
                --_live_nodes;
252 253 254 255 256 257 258 259
            } else {
                //  The node is not redundant, so it's a candidate for being
                //  the new min/max node.
                //
                //  We loop through the node array from left to right, so the
                //  first non-null, non-redundant node encountered is the new
                //  minimum index. Conversely, the last non-redundant, non-null
                //  node encountered is the new maximum index.
260 261 262 263
                if (c + _min < new_min)
                    new_min = c + _min;
                if (c + _min > new_max)
                    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 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314
    switch (_live_nodes) {
        case 0:
            free (_next.table);
            _next.table = NULL;
            _count = 0;
            break;
        case 1:
            //  Compact the node table if possible

            //  If there's only one live node in the table we can
            //  switch to using the more compact single-node
            //  representation
            zmq_assert (new_min == new_max);
            zmq_assert (new_min >= _min && new_min < _min + _count);
            {
                generic_mtrie_t *node = _next.table[new_min - _min];
                zmq_assert (node);
                free (_next.table);
                _next.node = node;
            }
            _count = 1;
            _min = new_min;
            break;
        default:
            if (new_min > _min || new_max < _min + _count - 1) {
                zmq_assert (new_max - new_min + 1 > 1);

                generic_mtrie_t **old_table = _next.table;
                zmq_assert (new_min > _min || new_max < _min + _count - 1);
                zmq_assert (new_min >= _min);
                zmq_assert (new_max <= _min + _count - 1);
                zmq_assert (new_max - new_min + 1 < _count);

                _count = new_max - new_min + 1;
                _next.table = static_cast<generic_mtrie_t **> (
                  malloc (sizeof (generic_mtrie_t *) * _count));
                alloc_assert (_next.table);

                memmove (_next.table, old_table + (new_min - _min),
                         sizeof (generic_mtrie_t *) * _count);
                free (old_table);

                _min = new_min;
            }
315 316 317
    }
}
template <typename T>
318 319
typename zmq::generic_mtrie_t<T>::rm_result
zmq::generic_mtrie_t<T>::rm (prefix_t prefix_, size_t size_, value_t *pipe_)
320 321 322 323 324
{
    return rm_helper (prefix_, size_, pipe_);
}

template <typename T>
325 326
typename zmq::generic_mtrie_t<T>::rm_result zmq::generic_mtrie_t<T>::rm_helper (
  prefix_t prefix_, size_t size_, value_t *pipe_)
327 328
{
    if (!size_) {
329
        if (!_pipes)
330 331
            return not_found;

332 333
        typename pipes_t::size_type erased = _pipes->erase (pipe_);
        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 346
    generic_mtrie_t *next_node =
      _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 354

    if (next_node->is_redundant ()) {
        LIBZMQ_DELETE (next_node);
355
        zmq_assert (_count > 0);
356

357 358 359 360 361
        if (_count == 1) {
            _next.node = 0;
            _count = 0;
            --_live_nodes;
            zmq_assert (_live_nodes == 0);
362
        } else {
363 364 365
            _next.table[c - _min] = 0;
            zmq_assert (_live_nodes > 1);
            --_live_nodes;
366 367

            //  Compact the table if possible
368
            if (_live_nodes == 1) {
369 370 371 372
                //  If there's only one live node in the table we can
                //  switch to using the more compact single-node
                //  representation
                unsigned short i;
373 374
                for (i = 0; i < _count; ++i)
                    if (_next.table[i])
375 376
                        break;

377 378 379 380 381 382 383
                zmq_assert (i < _count);
                _min += i;
                _count = 1;
                generic_mtrie_t *oldp = _next.table[i];
                free (_next.table);
                _next.node = oldp;
            } else if (c == _min) {
384 385
                //  We can compact the table "from the left"
                unsigned short i;
386 387
                for (i = 1; i < _count; ++i)
                    if (_next.table[i])
388 389
                        break;

390 391 392 393
                zmq_assert (i < _count);
                _min += i;
                _count -= i;
                generic_mtrie_t **old_table = _next.table;
394 395
                _next.table = static_cast<generic_mtrie_t **> (
                  malloc (sizeof (generic_mtrie_t *) * _count));
396 397 398
                alloc_assert (_next.table);
                memmove (_next.table, old_table + i,
                         sizeof (generic_mtrie_t *) * _count);
399
                free (old_table);
400
            } else if (c == _min + _count - 1) {
401 402
                //  We can compact the table "from the right"
                unsigned short i;
403 404
                for (i = 1; i < _count; ++i)
                    if (_next.table[_count - 1 - i])
405 406
                        break;

407 408 409
                zmq_assert (i < _count);
                _count -= i;
                generic_mtrie_t **old_table = _next.table;
410 411
                _next.table = static_cast<generic_mtrie_t **> (
                  malloc (sizeof (generic_mtrie_t *) * _count));
412 413 414
                alloc_assert (_next.table);
                memmove (_next.table, old_table,
                         sizeof (generic_mtrie_t *) * _count);
415 416 417 418 419 420 421 422 423
                free (old_table);
            }
        }
    }

    return ret;
}

template <typename T>
424
template <typename Arg>
425 426
void zmq::generic_mtrie_t<T>::match (prefix_t data_,
                                     size_t size_,
427 428
                                     void (*func_) (value_t *pipe_, Arg arg_),
                                     Arg arg_)
429 430 431 432
{
    generic_mtrie_t *current = this;
    while (true) {
        //  Signal the pipes attached to this node.
433 434 435
        if (current->_pipes) {
            for (typename pipes_t::iterator it = current->_pipes->begin ();
                 it != current->_pipes->end (); ++it)
436 437 438 439 440 441 442 443
                func_ (*it, arg_);
        }

        //  If we are at the end of the message, there's nothing more to match.
        if (!size_)
            break;

        //  If there are no subnodes in the trie, return.
444
        if (current->_count == 0)
445 446 447
            break;

        //  If there's one subnode (optimisation).
448 449
        if (current->_count == 1) {
            if (data_[0] != current->_min)
450
                break;
451
            current = current->_next.node;
452 453 454 455 456 457
            data_++;
            size_--;
            continue;
        }

        //  If there are multiple subnodes.
458 459
        if (data_[0] < current->_min
            || 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 465 466 467 468 469 470
        data_++;
        size_--;
    }
}

template <typename T> bool zmq::generic_mtrie_t<T>::is_redundant () const
{
471
    return !_pipes && _live_nodes == 0;
472 473 474 475
}


#endif