R3 is an URL router library with high performance, thus, it's implemented in C. It compiles your R3Route paths into a prefix trie.
By using the prefix tree constructed in the start-up time, you can dispatch the path to the controller with high efficiency.
- autoconf
- automake
- check
- pkg-config
- pcre
- (optional) graphviz version 2.38.0 (20140413.2041)
- (optional) libjson-c-dev
/blog/post/{id} use [^/]+ regular expression by default.
/blog/post/{id:\d+} use `\d+` regular expression instead of default.
#include<r3/r3.h>// create a router tree with 10 children capacity (this capacity can grow dynamically)R3Node*n=r3_tree_create(10);
introute_data=3;
// insert the R3Route path into the router treer3_tree_insert_path(n, "/bar", &route_data); // ignore the length of pathr3_tree_insert_pathl(n, "/zoo", strlen("/zoo"), &route_data );
r3_tree_insert_pathl(n, "/foo/bar", strlen("/foo/bar"), &route_data );
r3_tree_insert_pathl(n ,"/post/{id}", strlen("/post/{id}") , &route_data );
r3_tree_insert_pathl(n, "/user/{id:\\d+}", strlen("/user/{id:\\d+}"), &route_data );
// if you want to catch error, you may call the extended path function for insertionintdata=10;
char*errstr=NULL;
R3Node*ret=r3_tree_insert_pathl_ex(n, "/foo/{name:\\d{5}", strlen("/foo/{name:\\d{5}"), NULL, &data, &errstr);
if (ret==NULL) {
// failed insertionprintf("error: %s\n", errstr);
free(errstr); // errstr is created from `asprintf`, so you have to free it manually.
}
// let's compile the tree!char*errstr=NULL;
interr=r3_tree_compile(n, &errstr);
if (err!=0) {
// failprintf("error: %s\n", errstr);
free(errstr); // errstr is created from `asprintf`, so you have to free it manually.
}
// dump the compiled treer3_tree_dump(n, 0);
// match a routeR3Node*matched_node=r3_tree_matchl(n, "/foo/bar", strlen("/foo/bar"), NULL);
if (matched_node) {
intret=*( (int*) matched_node->data );
}
// release the treer3_tree_free(n);Capture Dynamic Variables
If you want to capture the variables from regular expression, you will need to
create a match_entry object and pass the object to r3_tree_matchl function,
the catched variables will be pushed into the match entry structure:
match_entry*entry=match_entry_create("/foo/bar");
// free the match entrymatch_entry_free(entry);And you can even specify the request method restriction:
entry->request_method=METHOD_GET;
entry->request_method=METHOD_POST;
entry->request_method=METHOD_GET | METHOD_POST;When using match_entry, you may match the R3Route with r3_tree_match_entry function:
R3Node*matched_node=r3_tree_match_entry(n, entry);Release Memory
To release the memory, you may call r3_tree_free(R3Node *tree) to release the whole tree structure,
node*, edge*, route* objects that were inserted into the tree will be freed.
// create a router tree with 10 children capacity (this capacity can grow dynamically)n=r3_tree_create(10);
introute_data=3;
// insert the R3Route path into the router treer3_tree_insert_routel(n, METHOD_GET | METHOD_POST, "/blog/post", sizeof("/blog/post") -1, &route_data );
char*errstr=NULL;
interr=r3_tree_compile(n, &errstr);
if (err!=0) {
// failprintf("error: %s\n", errstr);
free(errstr); // errstr is created from `asprintf`, so you have to free it manually.
}
// in your http server handler// create the match entry for capturing dynamic variables.match_entry*entry=match_entry_create("/blog/post");
entry->request_method=METHOD_GET;
R3Route*matched_R3Route=r3_tree_match_route(n, entry);
matched_route->data; // get the data from matched route// free the objects at the endmatch_entry_free(entry);
r3_tree_free(n);A slug is a placeholder, which captures the string from the URL as a variable. Slugs will be compiled into regular expression patterns.
Slugs without patterns (like /user/{userId}) will be compiled into the [^/]+ pattern.
To specify the pattern of a slug, you may write a colon to separate the slug name and the pattern:
"/user/{userId:\\d+}"
The above R3Route will use \d+ as its pattern.
Simple regular expressions are optimized through a regexp pattern to opcode translator, which translates simple patterns into small & fast scanners.
By using this method, r3 reduces the matching overhead of pcre library.
Optimized patterns are: [a-z]+, [0-9]+, \d+, \w+, [^/]+, [^-]+ or .*.
Slugs without specified regular expression will be compiled into the [^/]+ pattern. therefore, it's optimized too.
Complex regular expressions will still use libpcre to match URL (partially).
The routing benchmark from stevegraham/rails' PR stevegraham/rails#1:
omg 10462.0 (±6.7%) i/s - 52417 in 5.030416s
And here is the result of the router journey:
omg 9932.9 (±4.8%) i/s - 49873 in 5.033452s
r3 uses the same R3Route path data for benchmarking, and here is the benchmark:
3 runs, 5000000 iterations each run, finished in 1.308894 seconds
11460057.83 i/sec
The R3Route path generator is from stevegraham/rails#1:
#!/usr/bin/env rubyarr=["foo","bar","baz","qux","quux","corge","grault","garply"]paths=arr.permutation(3).map{ |a| "/#{a.join'/'}"}paths.eachdo |path|
puts"r3_tree_insert_path(n, \"#{path}\", NULL);"end| Function Prefix | Description |
|---|---|
r3_tree_* | Tree related operations, which require a node to operate a whole tree |
r3_node_* | Single node related operations, which do not go through its own children or parent. |
r3_edge_* | Edge related operations |
r3_route_* | Route related operations, which are needed only when the tree is defined by routes |
match_entry_* | Match entry related operations, a match_entry is just like the request parameters |
The r3_tree_render_file API let you render the whole R3Route trie into a image.
To use graphviz, you need to enable graphviz while you run configure:
./configure --enable-graphviz
Here is the sample code of generating graph output:
R3Node*n=r3_tree_create(1);
r3_tree_insert_path(n, "/foo/bar/baz", NULL);
r3_tree_insert_path(n, "/foo/bar/qux", NULL);
r3_tree_insert_path(n, "/foo/bar/quux", NULL);
r3_tree_insert_path(n, "/foo/bar/corge", NULL);
r3_tree_insert_path(n, "/foo/bar/grault", NULL);
r3_tree_insert_path(n, "/garply/grault/foo", NULL);
r3_tree_insert_path(n, "/garply/grault/bar", NULL);
r3_tree_insert_path(n, "/user/{id}", NULL);
r3_tree_insert_path(n, "/post/{title:\\w+}", NULL);
char*errstr=NULL;
interr;
err=r3_tree_compile(n, &errstr);
if (err!=0) {
// failprintf("error: %s\n", errstr);
free(errstr); // errstr is created from `asprintf`, so you have to free it manually.
}
r3_tree_render_file(n, "png", "check_gvc.png");
r3_tree_free(n);
Or you can even export it with dot format:
digraphg {
graph [bb="0,0,205.1,471"];
node [label="\N"];
"{root}" [height=0.5,
pos="35.097,453",
width=0.97491];
"#1" [height=0.5,
pos="35.097,366",
width=0.75];
....intr3_tree_render_file(constR3Node*tree, constchar*format, constchar*filename);
intr3_tree_render(constR3Node*tree, constchar*layout, constchar*format, FILE*fp);
intr3_tree_render_dot(constR3Node*tree, constchar*layout, FILE*fp);
intr3_tree_render_file(constR3Node*tree, constchar*format, constchar*filename);You can render the whole tree structure into json format output.
Please run configure with the --enable-json option.
Here is the sample code to generate JSON string:
json_object*obj=r3_node_to_json_object(n);
constchar*json=r3_node_to_json_pretty_string(n);
printf("Pretty JSON: %s\n",json);
constchar*json=r3_node_to_json_string(n);
printf("JSON: %s\n",json);not implemented yet
// Here is the paths data structure$paths = [
'/blog/post/{id}' => [ 'controller' => 'PostController' , 'action' => 'item' , 'method' => 'GET' ] ,
'/blog/post' => [ 'controller' => 'PostController' , 'action' => 'list' , 'method' => 'GET' ] ,
'/blog/post' => [ 'controller' => 'PostController' , 'action' => 'create' , 'method' => 'POST' ] ,
'/blog' => [ 'controller' => 'BlogController' , 'action' => 'list' , 'method' => 'GET' ] ,
];
$rs = r3_compile($paths, 'persisten-table-id');
$ret = r3_dispatch($rs, '/blog/post/3' );
list($complete, $route, $variables) = $ret;
// matched conditions aren't done yetlist($error, $message) = r3_validate($route); // validate R3Route conditionsif ( $error ) {
echo$message; // "Method not allowed", "...";
}sudo apt-get install check libpcre3 libpcre3-dev libjemalloc-dev libjemalloc1 build-essential libtool automake autoconf pkg-config
sudo apt-get install graphviz-dev graphviz # if you want graphviz
./autogen.sh
./configure && make
sudo make install
And we support debian-based distro now!
sudo apt-get install build-essential autoconf automake libpcre3-dev pkg-config debhelper libtool check
mv dist-debian debian
dpkg-buildpackage -b -us -uc
sudo gdebi ../libr3*.deb
./configure --enable-check
make check
./configure --enable-graphviz
./configure --with-malloc=jemalloc
./configure --with-pcre=pcre-config path # such as /usr/local/bin/pcre-config The PPA for libr3 can be found in https://launchpad.net/~r3-team/+archive/libr3-daily.
- Perl Router::R3 by @CindyLinz https://metacpan.org/pod/Router::R3
- Python pyr3 by @lucemia https://github.com/lucemia/pyr3
- Python pyr3 by @thedrow https://github.com/thedrow/pyr3
- Haskell r3 by @MnO2 https://github.com/MnO2/r3
- Vala r3-vala by @Ronmi https://github.com/Ronmi/r3-vala
Node.js
- node-r3 by @othree https://github.com/othree/node-r3
- node-libr3 by @caasi https://github.com/caasi/node-r3
Ruby
- Ruby rr3 by @tonytonyjan https://github.com/tonytonyjan/rr3
- mruby r3 https://github.com/rail44/mruby-r3
- mruby rake r3 https://github.com/rail44/mruby-rack-r3
This software is released under MIT License.