1ZTRIE(3) CZMQ Manual ZTRIE(3)
2
6 ztrie - Class for simple trie for tokenizable strings
7
9 // This is a draft class, and may change without notice. It is disabled in
10 // stable builds by default. If you use this in applications, please ask
11 // for it to be pushed to stable state. Use --enable-drafts to enable.
12 #ifdef CZMQ_BUILD_DRAFT_API
13 // Callback function for ztrie_node to destroy node data.
14 typedef void (ztrie_destroy_data_fn) (
15 void **data);
16 // *** Draft method, for development use, may change without warning ***
18 // Creates a new ztrie.
19 CZMQ_EXPORT ztrie_t *
20 ztrie_new (char delimiter);
21 // *** Draft method, for development use, may change without warning ***
23 // Destroy the ztrie.
24 CZMQ_EXPORT void
25 ztrie_destroy (ztrie_t **self_p);
26 // *** Draft method, for development use, may change without warning ***
28 // Inserts a new route into the tree and attaches the data. Returns -1
29 // if the route already exists, otherwise 0. This method takes ownership of
30 // the provided data if a destroy_data_fn is provided.
31 CZMQ_EXPORT int
32 ztrie_insert_route (ztrie_t *self, const char *path, void *data, ztrie_destroy_data_fn destroy_data_fn);
33 // *** Draft method, for development use, may change without warning ***
35 // Removes a route from the trie and destroys its data. Returns -1 if the
36 // route does not exists, otherwise 0.
37 // the start of the list call zlist_first (). Advances the cursor.
38 CZMQ_EXPORT int
39 ztrie_remove_route (ztrie_t *self, const char *path);
40 // *** Draft method, for development use, may change without warning ***
42 // Returns true if the path matches a route in the tree, otherwise false.
43 CZMQ_EXPORT bool
44 ztrie_matches (ztrie_t *self, const char *path);
45 // *** Draft method, for development use, may change without warning ***
47 // Returns the data of a matched route from last ztrie_matches. If the path
48 // did not match, returns NULL. Do not delete the data as it's owned by
49 // ztrie.
50 CZMQ_EXPORT void *
51 ztrie_hit_data (ztrie_t *self);
52 // *** Draft method, for development use, may change without warning ***
54 // Returns the count of parameters that a matched route has.
55 CZMQ_EXPORT size_t
56 ztrie_hit_parameter_count (ztrie_t *self);
57 // *** Draft method, for development use, may change without warning ***
59 // Returns the parameters of a matched route with named regexes from last
60 // ztrie_matches. If the path did not match or the route did not contain any
61 // named regexes, returns NULL.
62 CZMQ_EXPORT zhashx_t *
63 ztrie_hit_parameters (ztrie_t *self);
64 // *** Draft method, for development use, may change without warning ***
66 // Returns the asterisk matched part of a route, if there has been no match
67 // or no asterisk match, returns NULL.
68 CZMQ_EXPORT const char *
69 ztrie_hit_asterisk_match (ztrie_t *self);
70 // *** Draft method, for development use, may change without warning ***
72 // Print the trie
73 CZMQ_EXPORT void
74 ztrie_print (ztrie_t *self);
75 // *** Draft method, for development use, may change without warning ***
77 // Self test of this class.
78 CZMQ_EXPORT void
79 ztrie_test (bool verbose);
80 #endif // CZMQ_BUILD_DRAFT_API
82 Please add '@interface' section in './../src/ztrie.c'.
83
85 This is a variant of a trie or prefix tree where all the descendants of
86 a node have a common prefix of the string associated with that node.
87 This implementation is specialized for strings that can be tokenized by
88 a delimiter like a URL, URI or URN. Routes in the tree can be matched
89 by regular expressions and by using capturing groups parts of a matched
90 route can be easily obtained.
91 Note that the performance for pure string based matching is okay but on
93 short strings zhash and zhashx are 3-4 times faster.
94
96 From ztrie_test method.
97 // Create a new trie for matching strings that can be tokenized by a slash
99 // (e.g. URLs minus the protocol, address and port).
100 ztrie_t *self = ztrie_new ('/');
101 assert (self);
102 int ret = 0;
104 // Let's start by inserting a couple of routes into the trie.
106 // This one is for the route '/foo/bar' the slash at the beginning of the
107 // route is important because everything before the first delimiter will be
108 // discarded. A slash at the end of a route is optional though. The data
109 // associated with this node is passed without destroy function which means
110 // it must be destroyed by the caller.
111 int foo_bar_data = 10;
112 ret = ztrie_insert_route (self, "/foo/bar", &foo_bar_data, NULL);
113 assert (ret == 0);
114 // Now suppose we like to match all routes with two tokens that start with
116 // '/foo/' but aren't '/foo/bar'. This is possible by using regular
117 // expressions which are enclosed in an opening and closing curly bracket.
118 // Tokens that contain regular expressions are always match after string
119 // based tokens.
120 // Note: There is no order in which regular expressions are sorted thus
121 // if you enter multiple expressions for a route you will have to make
122 // sure they don't have overlapping results. For example '/foo/{[^/]+}'
123 // and '/foo/{\d+} having could turn out badly.
124 int foo_other_data = 100;
125 ret = ztrie_insert_route (self, "/foo/{[^/]+}", &foo_other_data, NULL);
126 assert (ret == 0);
127 // Regular expression are only matched against tokens of the same level.
129 // This allows us to append to are route with a regular expression as if
130 // it were a string.
131 ret = ztrie_insert_route (self, "/foo/{[^/]+}/gulp", NULL, NULL);
132 assert (ret == 0);
133 // Routes are identified by their endpoint, which is the last token of the route.
135 // It is possible to insert routes for a node that already exists but isn't an
136 // endpoint yet. The delimiter at the end of a route is optional and has no effect.
137 ret = ztrie_insert_route (self, "/foo/", NULL, NULL);
138 assert (ret == 0);
139 // If you try to insert a route which already exists the method will return -1.
141 ret = ztrie_insert_route (self, "/foo", NULL, NULL);
142 assert (ret == -1);
143 // It is not allowed to insert routes with empty tokens.
145 ret = ztrie_insert_route (self, "//foo", NULL, NULL);
146 assert (ret == -1);
147 // Everything before the first delimiter is ignored so 'foo/bar/baz' is equivalent
149 // to '/bar/baz'.
150 ret = ztrie_insert_route (self, "foo/bar/baz", NULL, NULL);
151 assert (ret == 0);
152 ret = ztrie_insert_route (self, "/bar/baz", NULL, NULL);
153 assert (ret == -1);
154 // Of course you are allowed to remove routes, in case there is data associated with a
156 // route and a destroy data function has been supplied that data will be destroyed.
157 ret = ztrie_remove_route (self, "/foo");
158 assert (ret == 0);
159 // Removing a non existent route will as well return -1.
161 ret = ztrie_remove_route (self, "/foo");
162 assert (ret == -1);
163 // Removing a route with a regular expression must exactly match the entered one.
165 ret = ztrie_remove_route (self, "/foo/{[^/]+}");
166 assert (ret == 0);
167 // Next we like to match a path by regular expressions and also extract matched
169 // parts of a route. This can be done by naming the regular expression. The name of a
170 // regular expression is entered at the beginning of the curly brackets and separated
171 // by a colon from the regular expression. The first one in this examples is named
172 // 'name' and names the expression '[^/]'. If there is no capturing group defined in
173 // the expression the whole matched string will be associated with this parameter. In
174 // case you don't like the get the whole matched string use a capturing group, like
175 // it has been done for the 'id' parameter. This is nice but you can even match as
176 // many parameter for a token as you like. Therefore simply put the parameter names
177 // separated by colons in front of the regular expression and make sure to add a
178 // capturing group for each parameter. The first parameter will be associated with
179 // the first capturing and so on.
180 char *data = (char *) malloc (80);
181 sprintf (data, "%s", "Hello World!");
182 ret = ztrie_insert_route (self, "/baz/{name:[^/]+}/{id:--(\\d+)}/{street:nr:(\\a+)(\\d+)}", data, NULL);
183 assert (ret == 0);
184 // There is a lot you can do with regular expression but matching routes
186 // of arbitrary length won't work. Therefore we make use of the asterisk
187 // operator. Just place it at the end of your route, e.g. '/config/bar/*'.
188 ret = ztrie_insert_route (self, "/config/bar/*", NULL, NULL);
189 assert (ret == 0);
190 // Appending to an asterisk as you would to with a regular expression
192 // isn't valid.
193 ret = ztrie_insert_route (self, "/config/bar/*/bar", NULL, NULL);
194 assert (ret == -1);
195 // The asterisk operator will only work as a leaf in the tree. If you
197 // enter an asterisk in the middle of your route it will simply be
198 // interpreted as a string.
199 ret = ztrie_insert_route (self, "/test/*/bar", NULL, NULL);
200 assert (ret == 0);
201 // If a parent has an asterisk as child it is not allowed to have
203 // other siblings.
204 ret = ztrie_insert_route (self, "/config/bar/foo/glup", NULL, NULL);
205 assert (ret != 0);
206 // Test matches
208 bool hasMatch = false;
209 // The route '/bar/foo' will fail to match as this route has never been inserted.
211 hasMatch = ztrie_matches (self, "/bar/foo");
212 assert (!hasMatch);
213 // The route '/foo/bar' will match and we can obtain the data associated with it.
215 hasMatch = ztrie_matches (self, "/foo/bar");
216 assert (hasMatch);
217 int foo_bar_hit_data = *((int *) ztrie_hit_data (self));
218 assert (foo_bar_data == foo_bar_hit_data);
219 // This route is part of another but is no endpoint itself thus the matches will fail.
221 hasMatch = ztrie_matches (self, "/baz/blub");
222 assert (!hasMatch);
223 // This route will match our named regular expressions route. Thus we can extract data
225 // from the route by their names.
226 hasMatch = ztrie_matches (self, "/baz/blub/--11/abc23");
227 assert (hasMatch);
228 char *match_data = (char *) ztrie_hit_data (self);
229 assert (streq ("Hello World!", match_data));
230 zhashx_t *parameters = ztrie_hit_parameters (self);
231 assert (zhashx_size (parameters) == 4);
232 assert (streq ("blub", (char *) zhashx_lookup (parameters, "name")));
233 assert (streq ("11", (char *) zhashx_lookup (parameters, "id")));
234 assert (streq ("abc", (char *) zhashx_lookup (parameters, "street")));
235 assert (streq ("23", (char *) zhashx_lookup (parameters, "nr")));
236 zhashx_destroy (¶meters);
237 // This will match our asterisk route '/config/bar/*'. As the result we
239 // can obtain the asterisk matched part of the route.
240 hasMatch = ztrie_matches (self, "/config/bar/foo/bar");
241 assert (hasMatch);
242 assert (streq (ztrie_hit_asterisk_match (self), "foo/bar"));
243 zstr_free (&data);
245 ztrie_destroy (&self);
246 #if defined (__WINDOWS__)
248 zsys_shutdown();
249 #endif
250
253 The czmq manual was written by the authors in the AUTHORS file.
254
256 Main web site:
257 Report bugs to the email <zeromq-dev@lists.zeromq.org[1]>
259
261 Copyright (c) the Contributors as noted in the AUTHORS file. This file
262 is part of CZMQ, the high-level C binding for 0MQ:
263 http://czmq.zeromq.org. This Source Code Form is subject to the terms
264 of the Mozilla Public License, v. 2.0. If a copy of the MPL was not
265 distributed with this file, You can obtain one at
266 http://mozilla.org/MPL/2.0/. LICENSE included with the czmq
267 distribution.
268
270 1. zeromq-dev@lists.zeromq.org
271 mailto:zeromq-dev@lists.zeromq.org
272CZMQ 4.2.0 01/28/2020 ZTRIE(3)