/* ========================================================================= ztrie - simple trie for tokenizable strings Copyright (c) the Contributors as noted in the AUTHORS file. This file is part of CZMQ, the high-level C binding for 0MQ: http://czmq.zeromq.org. This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/. ========================================================================= */ /* @header This is a variant of a trie or prefix tree where all the descendants of a node have a common prefix of the string associated with that node. This implementation is specialized for strings that can be tokenized by a delimiter like a URL, URI or URN. Routes in the tree can be matched by regular expressions and by using capturing groups parts of a matched route can be easily obtained. @discuss Note that the performance for pure string based matching is okay but on short strings zhash and zhashx are 3-4 times faster. @end */ #include "czmq_classes.h" #define MODE_INSERT 0 #define MODE_LOOKUP 1 #define MODE_MATCH 2 #define NODE_TYPE_STRING 0 // Node with string token #define NODE_TYPE_REGEX 1 // Node with regex token #define NODE_TYPE_PARAM 2 // Node with named regex token and capturing group(s) #define NODE_TYPE_ASTERISK 3 // Node with an asterisk, to match routes of variable length #define MIN_LEN(x,y) \ y + ((x - y) & ((x - y) >>(sizeof(int) * CHAR_BIT - 1))) // TODO: Move to a more appropriate location: static char * s_strndup (const char *s, size_t size) { char *dup; char *end = (char *) memchr (s, '\0', size); if (end) size = end - 1 - s; // -1 to get the last char before '\0' dup = (char *) zmalloc (sizeof (char) * size + 1); // +1 for trailing '\0' if (size) { memcpy (dup, s, size); dup [size] = '\0'; } return dup; } // Trie node, used internally only typedef struct _ztrie_node_t { char *token; // Part of a path between to delemiters e.g. '/{token}/' int token_type; // Type of the token, string, regex, asterisk int token_len; // Number of characters of the token size_t path_len; // Length of the path/route including this token bool endpoint; // Has a path been added that routes to this node? size_t parameter_count; // How many regex parameters does this token contain? char **parameter_names; // Names of the regex parameters for easy access at matching time char **parameter_values; // Values of the parameters char *asterisk_match; // Matched asterisk route zrex_t *regex; // Compiled regex void *data; // Custom arbitrary data assoziated with a route ztrie_destroy_data_fn *destroy_data_fn; // Callback to destroy custom data zlistx_t *children; // List of all children to this route struct _ztrie_node_t *parent; // Parent of this node } ztrie_node_t; // -------------------------------------------------------------------------- // Structure of our class struct _ztrie_t { char delimiter; // Character that seperates the tokens of a route ztrie_node_t *root; // Root node of this tree ztrie_node_t *match; // Last match made by ztrie_matches zlistx_t *params; // List of regex parameters found during parsing // The list is kept globally to optimize performance. }; // Internal helper functions static int s_ztrie_node_compare (const void *item1, const void *item2) { assert (item1); assert (item2); ztrie_node_t *node1 = (ztrie_node_t *) item1; ztrie_node_t *node2 = (ztrie_node_t *) item2; int same = node1->token_type - node2->token_type; if (same == 0) { if (*node1->token == *node2->token // This achieves a small performance boost && node1->token_len == node2->token_len && strncmp (node1->token, node2->token, MIN_LEN (node1->token_len, node2->token_len)) == 0) return 0; else return -1; } else return same; } // Create a new ztrie_node. If parent is not NULL the child will add itself // to the parents children. static ztrie_node_t * s_ztrie_node_new (ztrie_node_t *parent, char *token, int token_len, zlistx_t *param_keys, int token_type) { ztrie_node_t *self = (ztrie_node_t *) zmalloc (sizeof (ztrie_node_t)); assert (self); // Initialize properties self->token = s_strndup (token, token_len); self->token_type = token_type; self->token_len = token_len; self->endpoint = false; self->parameter_count = 0; self->parameter_names = NULL; self->parameter_values = NULL; if (param_keys && zlistx_size (param_keys) > 0) { self->parameter_count = zlistx_size (param_keys); self->parameter_names = (char **) malloc (sizeof (char *) * self->parameter_count); self->parameter_values = (char **) malloc (sizeof (char *) * self->parameter_count); char *key = (char *) zlistx_first (param_keys); size_t index; for (index = 0; index < zlistx_size (param_keys); index++) { self->parameter_names [index] = key; self->parameter_values [index] = NULL; key = (char *) zlistx_next (param_keys); } } if (self->token_type == NODE_TYPE_REGEX || self->token_type == NODE_TYPE_PARAM) self->regex = zrex_new (self->token); self->data = NULL; // Initialize relationships self->parent = parent; if (self->parent) { zlistx_add_end (self->parent->children, self); // Sort regexes to the end to avoid conlficts zlistx_sort (self->parent->children); } size_t parent_path_len = self->parent? self->parent->path_len: 0; self->path_len = parent_path_len + strlen (self->token) + 1; // +1 path delimiter self->children = zlistx_new (); zlistx_set_comparator (self->children, s_ztrie_node_compare); return self; } // Destroy the ztrie_node. static void s_ztrie_node_destroy (ztrie_node_t **self_p) { assert (self_p); if (*self_p) { ztrie_node_t *self = *self_p; // Free class properties zstr_free (&self->token); zstr_free (&self->asterisk_match); if (self->parameter_count > 0) { size_t index; for (index = 0; index < self->parameter_count; index++) { freen (self->parameter_names [index]); if (self->parameter_values [index]) freen (self->parameter_values [index]); } freen (self->parameter_names); freen (self->parameter_values); } if (self->token_type == NODE_TYPE_REGEX || self->token_type == NODE_TYPE_PARAM) zrex_destroy (&self->regex); zlistx_destroy (&self->children); if (self->data && self->destroy_data_fn) (self->destroy_data_fn) (&self->data); // Free object itself freen (self); *self_p = NULL; } } // Update the value of a regex parameter at position. static void s_ztrie_node_update_param (ztrie_node_t *self, int pos, const char *value) { assert (self); zstr_free (&self->parameter_values [pos - 1]); self->parameter_values [pos - 1] = strdup (value); } // -------------------------------------------------------------------------- // Creates a new ztrie. ztrie_t * ztrie_new (char delimiter) { ztrie_t *self = (ztrie_t *) zmalloc (sizeof (ztrie_t)); assert (self); // Initialize properties if (delimiter) self->delimiter = delimiter; else self->delimiter = '/'; self->root = s_ztrie_node_new (NULL, "", 0, NULL, NODE_TYPE_STRING); self->match = NULL; self->params = zlistx_new (); return self; } // Destroy all children of a node static void s_ztrie_destroy_children (ztrie_node_t *node) { ztrie_node_t *child = (ztrie_node_t *) zlistx_first (node->children); while (child) { s_ztrie_destroy_children (child); s_ztrie_node_destroy (&child); child = (ztrie_node_t *) zlistx_next (node->children); } } // -------------------------------------------------------------------------- // Destroy the ztrie. void ztrie_destroy (ztrie_t **self_p) { assert (self_p); if (*self_p) { ztrie_t *self = *self_p; // Free class properties s_ztrie_destroy_children (self->root); s_ztrie_node_destroy (&self->root); zlistx_destroy (&self->params); // Free object itself freen (self); *self_p = NULL; } } // String compare token static ztrie_node_t * s_ztrie_compare_token (ztrie_node_t *parent, char *token, int len) { ztrie_node_t *child = (ztrie_node_t *) zlistx_first (parent->children); while (child) { if (child->token_len == len && strncmp (child->token, token, MIN_LEN (child->token_len, len)) == 0) return child; child = (ztrie_node_t *) zlistx_next (parent->children); } return NULL; } // String compare token or evaluate regexes static ztrie_node_t * s_ztrie_matches_token (ztrie_node_t *parent, char *token, int len) { char firstbyte = *token; ztrie_node_t *child = (ztrie_node_t *) zlistx_first (parent->children); while (child) { if (child->token_type == NODE_TYPE_STRING) { if (firstbyte == *child->token // This achieves a small performance boost && child->token_len == len && strncmp (child->token, token, MIN_LEN (child->token_len, len)) == 0) return child; } else if (child->token_type == NODE_TYPE_ASTERISK) { child->asterisk_match = strdup (token); return child; } else { // Need to copy token as zrex_matches expects '\0' terminated string char *token_term = s_strndup (token, len); if (zrex_matches (child->regex, token_term)) { if (child->token_type == NODE_TYPE_PARAM) { // One hit means no capturing group was defined // More than one hit indicates that at least on capturing group. // In this case only the values of the capturing groups are considered. if (zrex_hits (child->regex) == 1) s_ztrie_node_update_param (child, 1, zrex_hit (child->regex, 0)); else if (zrex_hits (child->regex) > 1) { int index; for (index = 1; index < zrex_hits (child->regex); index++) s_ztrie_node_update_param (child, index, zrex_hit (child->regex, index)); } } freen (token_term); return child; } freen (token_term); } child = (ztrie_node_t *) zlistx_next (parent->children); } return NULL; } // -------------------------------------------------------------------------- // Parses a path bytewise trying to find matches for path tokens. Depending // on the mode there are different behaviors on, // how the tokens are compared: // MODE_INSERT: All tokens are compared as strings. // MODE_LOOKUP: All tokens are compared as strings. // MODE_MATCH: Node tokens of NODE_TYPE_STRING tokens are compared as strings, // otherwise the tokens are matched against the nodes regex. // how a mismatch is handled: // MODE_INSERT: creates a new node and attaches it to the common prefix for // the given path, repeat for the remaining path tokens. // returns the node that has been attached last. // MODE_LOOKUP: returns NULL if the comparison failed. // MODE_MATCH: returns NULL if the comparison failed. static ztrie_node_t * s_ztrie_parse_path (ztrie_t *self, const char *path, int mode) { int state = 0; char *needle, *beginToken = NULL, *beginRegex = NULL; ztrie_node_t *parent = self->root; if (zlistx_size (self->params) > 0) zlistx_purge (self->params); size_t len = strlen (path); needle = (char *) path; char *needle_stop = needle + len; // Ignore trailing delimiter if (needle [len-1] == self->delimiter) needle_stop -= 1; while (needle < needle_stop + 1) { // It is valid not to have an delimiter at the end of the path if (*needle == self->delimiter || needle == needle_stop) { // Token starts with delimiter ignore everything that comes before if (state == 0) { beginToken = needle + 1; state++; if (mode == MODE_INSERT || mode == MODE_LOOKUP) // Increment so regexes are parsed which is only relevant // during INSERT or LOOKUP. Using different states gives a small // performance boost for matching. state++; } // Token ends with delimiter. else if (state < 3) { int matchType = zlistx_size (self->params) > 0? NODE_TYPE_PARAM: beginRegex? NODE_TYPE_REGEX: NODE_TYPE_STRING; char *matchToken = beginRegex? beginRegex: beginToken; int matchTokenLen = (int) (needle - matchToken) - (beginRegex? 1: 0); // Illegal token if (matchTokenLen == 0) return NULL; ztrie_node_t *match = NULL; // Asterisk nodes are only allowed at the end of a route if (needle == needle_stop && *matchToken == '*') { if (zlistx_size (parent->children) == 0) { matchType = NODE_TYPE_ASTERISK; matchToken = needle - 1; matchTokenLen = 1; } // Asterisk must be a leaf in the tree else return NULL; } else { matchType = zlistx_size (self->params) > 0? NODE_TYPE_PARAM: beginRegex? NODE_TYPE_REGEX: NODE_TYPE_STRING; matchToken = beginRegex? beginRegex: beginToken; matchTokenLen = (int) (needle - matchToken) - (beginRegex? 1: 0); } // In insert and lookup mode only do a string comparison if (mode == MODE_INSERT || mode == MODE_LOOKUP) match = s_ztrie_compare_token (parent, matchToken, matchTokenLen); else // Otherwise evaluate regexes if (mode == MODE_MATCH) match = s_ztrie_matches_token (parent, matchToken, matchTokenLen); // Mismatch behavior depends on mode if (!match) { // Append to common prefix if (mode == MODE_INSERT) { // It's not allowed to append on asterisk if (parent->token_type == NODE_TYPE_ASTERISK || (zlistx_size (parent->children) == 1 && ((ztrie_node_t *) (zlistx_first (parent->children)))->token_type == NODE_TYPE_ASTERISK)) return NULL; parent = s_ztrie_node_new (parent, matchToken, matchTokenLen, self->params, matchType); } else // No match for path found if (mode == MODE_MATCH || mode == MODE_LOOKUP) return NULL; } // If a match has been found it becomes the parent for next path token else { parent = match; // In case a asterisk match has been made skip the rest of the route if (parent->token_type == NODE_TYPE_ASTERISK) break; } // Cleanup for next token beginRegex = NULL; if (zlistx_size (self->params) > 0) zlistx_purge (self->params); // Token end equals token begin beginToken = needle + 1; } } else // regex starts with '{' if (state == 2 && *needle == '{') { beginRegex = needle + 1; state++; } else // in the middle of the regex. Found a named regex. if (state == 3 && (*needle == ':')) { zlistx_add_end (self->params, s_strndup (beginRegex, needle - beginRegex)); beginRegex = needle + 1; } else // regex ends with { if (state == 3 && *needle == '}') { state--; } needle++; } // In matching mode the discovered node must be an endpoint if (parent && mode == MODE_MATCH && !parent->endpoint) return NULL; return parent; } // -------------------------------------------------------------------------- // Inserts a new route into the trie and attaches the data. Returns -1 // if the route already exists, otherwise 0. This method takes ownership of // the provided data. int ztrie_insert_route (ztrie_t *self, const char *path, void *data, ztrie_destroy_data_fn destroy_data_fn) { assert (self); ztrie_node_t *node = s_ztrie_parse_path (self, path, MODE_INSERT); // If the returned node has no endpoint, a new route can be assigned to it. if (node && !node->endpoint) { node->endpoint = true; node->data = data; node->destroy_data_fn = destroy_data_fn; return 0; } // If the returned node has an endpoint, a route has already assigned to it. else return -1; } // -------------------------------------------------------------------------- // Removes a route from the trie and destroys its data. Returns -1 if the // route does not exists, otherwise 0. int ztrie_remove_route (ztrie_t *self, const char *path) { assert (self); ztrie_node_t *match = s_ztrie_parse_path (self, path, MODE_LOOKUP); // The path did match a node which is endpoint to a route if (match && match->endpoint) { // This node is part of other routes, thus it cannot destroy it if (zlistx_size (match->children) > 0) { match->endpoint = false; if (match->data && match->destroy_data_fn) (match->destroy_data_fn) (&match->data); } // If this node is not part of other routes, destroy it else { // Delete match from parent's children before destroying void *handle = zlistx_find (match->parent->children, match); assert (handle); zlistx_delete (match->parent->children, handle); s_ztrie_node_destroy (&match); } return 0; } // If there is no match or the match is not endpoint to a route, fail else return -1; } // -------------------------------------------------------------------------- // Returns true if the path matches a route in the tree, otherwise false. bool ztrie_matches (ztrie_t *self, const char *path) { assert (self); self->match = s_ztrie_parse_path (self, path, MODE_MATCH); return self->match? true: false; } // -------------------------------------------------------------------------- // Returns the data of a matched route from last ztrie_matches. If the path // did not match, returns NULL. Do not delete the data as it's owned by // ztrie. void * ztrie_hit_data (ztrie_t *self) { assert (self); if (self->match) return self->match->data; return NULL; } // -------------------------------------------------------------------------- // Returns the count of parameters that a matched route has. size_t ztrie_hit_parameter_count (ztrie_t *self) { size_t count = 0; ztrie_node_t *node = self->match; while (node) { count += node->parameter_count; node = node->parent; } return count; } // -------------------------------------------------------------------------- // Returns the parameters of a matched route with named regexes from last // ztrie_matches. If the path did not match or the route did not contain any // named regexes, returns NULL. The caller is responseable for destroy the map. zhashx_t * ztrie_hit_parameters (ztrie_t *self) { assert (self); if (self->match) { zhashx_t *route_parameters = zhashx_new (); ztrie_node_t *node = self->match; while (node) { size_t index; for (index = 0; index < node->parameter_count; index++) zhashx_insert (route_parameters, node->parameter_names [index], (void *) node->parameter_values [index]); node = node->parent; } return route_parameters; } return NULL; } // -------------------------------------------------------------------------- // Returns the asterisk matched part of a route, if there has been no match // or no asterisk match, returns NULL. const char * ztrie_hit_asterisk_match (ztrie_t *self) { assert (self); if (self->match) return self->match->asterisk_match; return NULL; } // -------------------------------------------------------------------------- // Print properties of the ztrie object. // static void s_ztrie_print_tree_line (ztrie_node_t *self, bool end_line) { if (self->parent) { s_ztrie_print_tree_line (self->parent, false); if (zlistx_tail (self->parent->children) == self) { if (end_line) printf ("`-- "); else printf (" "); } else { if (end_line) printf ("+-- "); else printf ("| "); } if (end_line) { char *is_endpoint = self->endpoint? "true": "false"; printf ("%s (params: %zu, endpoint: %s, type: %d)\n", self->token, self->parameter_count, is_endpoint, self->token_type); } } } static void s_ztrie_print_tree (ztrie_node_t *self) { // Print tree like structure s_ztrie_print_tree_line (self, true); ztrie_node_t *child = (ztrie_node_t *) zlistx_first (self->children); while (child) { s_ztrie_print_tree (child); child = (ztrie_node_t *) zlistx_next (self->children); } } void ztrie_print (ztrie_t *self) { assert (self); s_ztrie_print_tree (self->root); } // -------------------------------------------------------------------------- // Self test of this class. void ztrie_test (bool verbose) { printf (" * ztrie: "); // @selftest // Create a new trie for matching strings that can be tokenized by a slash // (e.g. URLs minus the protocol, address and port). ztrie_t *self = ztrie_new ('/'); assert (self); int ret = 0; // Let's start by inserting a couple of routes into the trie. // This one is for the route '/foo/bar' the slash at the beginning of the // route is important because everything before the first delimiter will be // discarded. A slash at the end of a route is optional though. The data // associated with this node is passed without destroy function which means // it must be destroyed by the caller. int foo_bar_data = 10; ret = ztrie_insert_route (self, "/foo/bar", &foo_bar_data, NULL); assert (ret == 0); // Now suppose we like to match all routes with two tokens that start with // '/foo/' but aren't '/foo/bar'. This is possible by using regular // expressions which are enclosed in an opening and closing curly bracket. // Tokens that contain regular expressions are always match after string // based tokens. // Note: There is no order in which regular expressions are sorted thus // if you enter multiple expressions for a route you will have to make // sure they don't have overlapping results. For example '/foo/{[^/]+}' // and '/foo/{\d+} having could turn out badly. int foo_other_data = 100; ret = ztrie_insert_route (self, "/foo/{[^/]+}", &foo_other_data, NULL); assert (ret == 0); // Regular expression are only matched against tokens of the same level. // This allows us to append to are route with a regular expression as if // it were a string. ret = ztrie_insert_route (self, "/foo/{[^/]+}/gulp", NULL, NULL); assert (ret == 0); // Routes are identified by their endpoint, which is the last token of the route. // It is possible to insert routes for a node that already exists but isn't an // endpoint yet. The delimiter at the end of a route is optional and has no effect. ret = ztrie_insert_route (self, "/foo/", NULL, NULL); assert (ret == 0); // If you try to insert a route which already exists the method will return -1. ret = ztrie_insert_route (self, "/foo", NULL, NULL); assert (ret == -1); // It is not allowed to insert routes with empty tokens. ret = ztrie_insert_route (self, "//foo", NULL, NULL); assert (ret == -1); // Everything before the first delimiter is ignored so 'foo/bar/baz' is equivalent // to '/bar/baz'. ret = ztrie_insert_route (self, "foo/bar/baz", NULL, NULL); assert (ret == 0); ret = ztrie_insert_route (self, "/bar/baz", NULL, NULL); assert (ret == -1); // Of course you are allowed to remove routes, in case there is data associated with a // route and a destroy data function has been supplied that data will be destroyed. ret = ztrie_remove_route (self, "/foo"); assert (ret == 0); // Removing a non existent route will as well return -1. ret = ztrie_remove_route (self, "/foo"); assert (ret == -1); // Removing a route with a regular expression must exactly match the entered one. ret = ztrie_remove_route (self, "/foo/{[^/]+}"); assert (ret == 0); // Next we like to match a path by regular expressions and also extract matched // parts of a route. This can be done by naming the regular expression. The name of a // regular expression is entered at the beginning of the curly brackets and separated // by a colon from the regular expression. The first one in this examples is named // 'name' and names the expression '[^/]'. If there is no capturing group defined in // the expression the whole matched string will be associated with this parameter. In // case you don't like the get the whole matched string use a capturing group, like // it has been done for the 'id' parameter. This is nice but you can even match as // many parameter for a token as you like. Therefore simply put the parameter names // separated by colons in front of the regular expression and make sure to add a // capturing group for each parameter. The first parameter will be associated with // the first capturing and so on. char *data = (char *) malloc (80); sprintf (data, "%s", "Hello World!"); ret = ztrie_insert_route (self, "/baz/{name:[^/]+}/{id:--(\\d+)}/{street:nr:(\\a+)(\\d+)}", data, NULL); assert (ret == 0); // There is a lot you can do with regular expression but matching routes // of arbitrary length won't work. Therefore we make use of the asterisk // operator. Just place it at the end of your route, e.g. '/config/bar/*'. ret = ztrie_insert_route (self, "/config/bar/*", NULL, NULL); assert (ret == 0); // Appending to an asterisk as you would to with a regular expression // isn't valid. ret = ztrie_insert_route (self, "/config/bar/*/bar", NULL, NULL); assert (ret == -1); // The asterisk operator will only work as a leaf in the tree. If you // enter an asterisk in the middle of your route it will simply be // interpreted as a string. ret = ztrie_insert_route (self, "/test/*/bar", NULL, NULL); assert (ret == 0); // If a parent has an asterisk as child it is not allowed to have // other siblings. ret = ztrie_insert_route (self, "/config/bar/foo/glup", NULL, NULL); assert (ret != 0); // Test matches bool hasMatch = false; // The route '/bar/foo' will fail to match as this route has never been inserted. hasMatch = ztrie_matches (self, "/bar/foo"); assert (!hasMatch); // The route '/foo/bar' will match and we can obtain the data associated with it. hasMatch = ztrie_matches (self, "/foo/bar"); assert (hasMatch); int foo_bar_hit_data = *((int *) ztrie_hit_data (self)); assert (foo_bar_data == foo_bar_hit_data); // This route is part of another but is no endpoint itself thus the matches will fail. hasMatch = ztrie_matches (self, "/baz/blub"); assert (!hasMatch); // This route will match our named regular expressions route. Thus we can extract data // from the route by their names. hasMatch = ztrie_matches (self, "/baz/blub/--11/abc23"); assert (hasMatch); char *match_data = (char *) ztrie_hit_data (self); assert (streq ("Hello World!", match_data)); zhashx_t *parameters = ztrie_hit_parameters (self); assert (zhashx_size (parameters) == 4); assert (streq ("blub", (char *) zhashx_lookup (parameters, "name"))); assert (streq ("11", (char *) zhashx_lookup (parameters, "id"))); assert (streq ("abc", (char *) zhashx_lookup (parameters, "street"))); assert (streq ("23", (char *) zhashx_lookup (parameters, "nr"))); zhashx_destroy (¶meters); // This will match our asterisk route '/config/bar/*'. As the result we // can obtain the asterisk matched part of the route. hasMatch = ztrie_matches (self, "/config/bar/foo/bar"); assert (hasMatch); assert (streq (ztrie_hit_asterisk_match (self), "foo/bar")); zstr_free (&data); ztrie_destroy (&self); #if defined (__WINDOWS__) zsys_shutdown(); #endif // @end printf ("OK\n"); }