1 /*
2     Copyright (c) 2018 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 #ifndef RADIX_TREE_HPP
31 #define RADIX_TREE_HPP
32 
33 #include <stddef.h>
34 
35 #include "stdint.hpp"
36 
37 // Wrapper type for a node's data layout.
38 //
39 // There are 3 32-bit unsigned integers that act as a header. These
40 // integers represent the following values in this order:
41 //
42 // (1) The reference count of the key held by the node. This is 0 if
43 // the node doesn't hold a key.
44 //
45 // (2) The number of characters in the node's prefix. The prefix is a
46 // part of one or more keys in the tree, e.g. the prefix of each node
47 // in a trie consists of a single character.
48 //
49 // (3) The number of outgoing edges from this node.
50 //
51 // The rest of the layout consists of 3 chunks in this order:
52 //
53 // (1) The node's prefix as a sequence of one or more bytes. The root
54 // node always has an empty prefix, unlike other nodes in the tree.
55 //
56 // (2) The first byte of the prefix of each of this node's children.
57 //
58 // (3) The pointer to each child node.
59 //
60 // The link to each child is looked up using its index, e.g. the child
61 // with index 0 will have its first byte and node pointer at the start
62 // of the chunk of first bytes and node pointers respectively.
63 struct node_t
64 {
65     explicit node_t (unsigned char *data_);
66 
67     bool operator== (node_t other_) const;
68     bool operator!= (node_t other_) const;
69 
70     uint32_t refcount ();
71     uint32_t prefix_length ();
72     uint32_t edgecount ();
73     unsigned char *prefix ();
74     unsigned char *first_bytes ();
75     unsigned char first_byte_at (size_t index_);
76     unsigned char *node_pointers ();
77     node_t node_at (size_t index_);
78     void set_refcount (uint32_t value_);
79     void set_prefix_length (uint32_t value_);
80     void set_edgecount (uint32_t value_);
81     void set_prefix (const unsigned char *bytes_);
82     void set_first_bytes (const unsigned char *bytes_);
83     void set_first_byte_at (size_t index_, unsigned char byte_);
84     void set_node_pointers (const unsigned char *pointers_);
85     void set_node_at (size_t index_, node_t node_);
86     void set_edge_at (size_t index_, unsigned char first_byte_, node_t node_);
87     void resize (size_t prefix_length_, size_t edgecount_);
88 
89     unsigned char *_data;
90 };
91 
92 node_t make_node (size_t refcount_, size_t prefix_length_, size_t edgecount_);
93 
94 struct match_result_t
95 {
96     match_result_t (size_t key_bytes_matched_,
97                     size_t prefix_bytes_matched_,
98                     size_t edge_index_,
99                     size_t parent_edge_index_,
100                     node_t current_,
101                     node_t parent_,
102                     node_t grandparent);
103 
104     size_t _key_bytes_matched;
105     size_t _prefix_bytes_matched;
106     size_t _edge_index;
107     size_t _parent_edge_index;
108     node_t _current_node;
109     node_t _parent_node;
110     node_t _grandparent_node;
111 };
112 
113 namespace zmq
114 {
115 class radix_tree_t
116 {
117   public:
118     radix_tree_t ();
119     ~radix_tree_t ();
120 
121     //  Add key to the tree. Returns true if this was a new key rather
122     //  than a duplicate.
123     bool add (const unsigned char *key_, size_t key_size_);
124 
125     //  Remove key from the tree. Returns true if the item is actually
126     //  removed from the tree.
127     bool rm (const unsigned char *key_, size_t key_size_);
128 
129     //  Check whether particular key is in the tree.
130     bool check (const unsigned char *key_, size_t key_size_);
131 
132     //  Apply the function supplied to each key in the tree.
133     void apply (void (*func_) (unsigned char *data, size_t size, void *arg),
134                 void *arg_);
135 
136     size_t size () const;
137 
138   private:
139     match_result_t
140     match (const unsigned char *key_, size_t key_size_, bool is_lookup_) const;
141 
142     node_t _root;
143     size_t _size;
144 };
145 }
146 
147 #endif
148