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_HPP_INCLUDED__
31#define __ZMQ_GENERIC_MTRIE_HPP_INCLUDED__
32
33#include <stddef.h>
34#include <set>
35
36#include "macros.hpp"
37#include "stdint.hpp"
38
39namespace zmq
40{
41// Multi-trie (prefix tree). Each node in the trie is a set of pointers.
42template <typename T> class generic_mtrie_t
43{
44 public:
45 typedef T value_t;
46 typedef const unsigned char *prefix_t;
47
48 enum rm_result
49 {
50 not_found,
51 last_value_removed,
52 values_remain
53 };
54
55 generic_mtrie_t ();
56 ~generic_mtrie_t ();
57
58 // Add key to the trie. Returns true iff no entry with the same prefix_
59 // and size_ existed before.
60 bool add (prefix_t prefix_, size_t size_, value_t *value_);
61
62 // Remove all entries with a specific value from the trie.
63 // The call_on_uniq_ flag controls if the callback is invoked
64 // when there are no entries left on a prefix only (true)
65 // or on every removal (false). The arg_ argument is passed
66 // through to the callback function.
67 template <typename Arg>
68 void rm (value_t *value_,
69 void (*func_) (const unsigned char *data_, size_t size_, Arg arg_),
70 Arg arg_,
71 bool call_on_uniq_);
72
73 // Removes a specific entry from the trie.
74 // Returns the result of the operation.
75 rm_result rm (prefix_t prefix_, size_t size_, value_t *value_);
76
77 // Calls a callback function for all matching entries, i.e. any node
78 // corresponding to data_ or a prefix of it. The arg_ argument
79 // is passed through to the callback function.
80 template <typename Arg>
81 void match (prefix_t data_,
82 size_t size_,
83 void (*func_) (value_t *value_, Arg arg_),
84 Arg arg_);
85
86 private:
87 bool add_helper (prefix_t prefix_, size_t size_, value_t *value_);
88 template <typename Arg>
89 void rm_helper (value_t *value_,
90 unsigned char **buff_,
91 size_t buffsize_,
92 size_t maxbuffsize_,
93 void (*func_) (prefix_t data_, size_t size_, Arg arg_),
94 Arg arg_,
95 bool call_on_uniq_);
96 template <typename Arg>
97 void rm_helper_multiple_subnodes (unsigned char **buff_,
98 size_t buffsize_,
99 size_t maxbuffsize_,
100 void (*func_) (prefix_t data_,
101 size_t size_,
102 Arg arg_),
103 Arg arg_,
104 bool call_on_uniq_,
105 value_t *pipe_);
106
107 rm_result rm_helper (prefix_t prefix_, size_t size_, value_t *value_);
108 bool is_redundant () const;
109
110 typedef std::set<value_t *> pipes_t;
111 pipes_t *_pipes;
112
113 unsigned char _min;
114 unsigned short _count;
115 unsigned short _live_nodes;
116 union
117 {
118 class generic_mtrie_t<value_t> *node;
119 class generic_mtrie_t<value_t> **table;
120 } _next;
121
122 ZMQ_NON_COPYABLE_NOR_MOVABLE (generic_mtrie_t)
123};
124}
125
126#endif
127