# R3: a C router that compiles your paths into a prefix trie

> R3 is a URL router library written in C that compiles your route paths into a prefix tree at start-up and dispatches requests against it, translating simple regular expressions into small scanners so that pcre2 is only needed for complex patterns. It is MIT licensed, sits on a 2.0 branch, and its only tagged release dates from 2014.

**c9s/r3** — libr3 is a high-performance path dispatching library. It compiles your route paths into a prefix tree (trie). By using the constructed prefix trie in the start-up time, you may dispatch your routes with efficiency

- Repository: https://github.com/c9s/r3
- Website: https://c9s.github.io/r3/bench.html
- Stars: 821 · Forks: 84
- Language: C
- License: MIT
- Published: 2026-10-20 · Updated: 2026-10-20 · Language: en
- Canonical page: https://hysenlabs.com/projects/c9s-r3

## Route paths compiled once, dispatched many times

R3 is a URL router library written in C for performance. Its design is stated plainly in the project description: it compiles your route paths into a prefix trie, and by using the prefix tree constructed at start-up time you can dispatch the path to the controller with high efficiency.

That start-up versus request-time split is the whole architecture. A trie is a tree where each node holds a character and the edges branch on it, so a set of paths shares their common prefixes in memory instead of being scanned one after another. In a router this turns a list of string comparisons into a walk down the tree, and the walk happens once per request rather than once per route.

The path syntax is not a framework convention but a small one. A path can contain a slug, a placeholder that captures the string from the URL as a variable:

    /blog/post/{id}      use [^/]+ regular expression by default.
    /blog/post/{id:\d+}  use `\d+` regular expression instead of default.

A slug without a pattern is compiled into the [^/]+ regular expression, so it matches one path segment and stops at the slash. With a colon you supply the pattern yourself, which is how you turn a permissive placeholder into a numeric one.

The library is written in C with a header only public interface, and the repository carries both a C++ header, include/r3.hpp, and a set of examples, simple.c, routing.c and simple_cpp.cpp, which is a reasonable way to check whether the API suits your language before you commit to it. The licence is MIT and the homepage is a benchmark page at c9s.github.io/r3/bench.html.

## Insert, compile, then match

The API has three phases, and the code in the documentation shows them clearly.

First you create the tree and insert paths into it:

```c
#include <r3/r3.h>

// create a router tree with 10 children capacity (this capacity can grow dynamically)
R3Node *n = r3_tree_create(10);

int route_data = 3;

// insert the R3Route path into the router tree
r3_tree_insert_path(n, "/bar", &route_data); // ignore the length of path
```

The capacity given to r3_tree_create is a starting size for the children array, and the documentation notes that it can grow dynamically, so it is a hint rather than a limit. Insertion comes in two forms: r3_tree_insert_path takes the path as a string and ignores its length, while r3_tree_insert_pathl takes an explicit length, which is what you want when the path is already a counted buffer.

Second, you compile the tree, and this is where errors surface:

```c
// let's compile the tree!
char *errstr = NULL;
int err = r3_tree_compile(n, &errstr);
if (err != 0) {
    // fail
    printf("error: %s\n", errstr);
    free(errstr); // errstr is created from `asprintf`, so you have to free it manually.
}
```

The error string comes from asprintf, so the caller has to free it by hand. The documentation makes a point of this, and the extended insertion function r3_tree_insert_pathl_ex returns a NULL node and fills the error string when a pattern fails to compile, which is how you learn that a slug pattern was malformed at start-up rather than on the first request that hits it.

Third, you match requests and free the tree:

```c
// match a route
R3Node *matched_node = r3_tree_matchl(n, "/foo/bar", strlen("/foo/bar"), NULL);
if (matched_node) {
    int ret = *( (int*) matched_node->data );
}

// release the tree
r3_tree_free(n);
```

The matched node carries a data pointer, and in the example it is cast to an int pointer to recover the route data you attached at insertion time. r3_tree_free releases the whole structure, and the documentation is explicit that the node, edge and route objects you inserted are freed with it, so you must not free them yourself.

There is also r3_tree_dump, which prints the compiled tree, and the documentation mentions rendering the routes with Graphviz through a function whose name is cut off in the excerpt.

## Simple patterns skip pcre2 altogether

The optimisation story is the most interesting technical decision in the library, and it is described with unusual precision.

Simple regular expressions are optimized through a regexp pattern to opcode translator, which translates simple patterns into small and fast scanners. By using this method, r3 reduces the matching overhead of the pcre2 library.

The optimized patterns are a short list: [a-z]+, [0-9]+, \d+, \w+, [^/]+, [^-]+ and .*. Slugs without a specified regular expression are compiled into the [^/]+ pattern, so the default case is optimized too, which means the common case of a plain placeholder costs nothing extra.

Complex regular expressions will still use libpcre2 to match the URL, partially. That word partially is the important one: the trie still does the prefix work, and pcre2 is consulted for the segment that needs a real engine. So the fallback is not a return to scanning every route, it is a narrower use of the slower library.

The runtime dependency list backs this up. pcre2 is the only required runtime library, and the optional ones are graphviz at version 2.38.0 or later for rendering the route tree and libjson-c-dev. The build dependencies are autoconf, automake, check and pkg-config, which is the standard autotools set, and the repository also carries a CMakeLists.txt, a cmake directory, configure.ac, Makefile.am and an r3.pc.in for pkg-config integration.

For a router library, this is the difference between being fast in principle and being fast in the case you actually have, which is usually a set of paths with the occasional slug.

## Capturing variables and matching on the request method

Matching a path is only half the job, because a route usually has to hand back the values it captured and honour the HTTP method.

For capture you create a match_entry, which the function prefix table describes as being just like the request parameters:

```c
match_entry * entry = match_entry_create("/foo/bar");

// free the match entry
match_entry_free(entry);
```

The captured variables are pushed into the match entry structure, so you read them from there after the match rather than from the node.

On the same object you can restrict the match to a request method:

```c
entry->request_method = METHOD_GET;
entry->request_method = METHOD_POST;
entry->request_method = METHOD_GET | METHOD_POST;
```

The bitmask form is what makes method routing cheap, since a route can accept several methods without needing several routes.

When you use a match_entry, the matching function changes accordingly, from r3_tree_matchl to r3_tree_match_entry:

```c
R3Node * matched_node = r3_tree_match_entry(n, entry);
```

There is a third variant for the case where the tree was built from routes rather than plain paths, which is how you get method information attached to the tree itself. Inserting with r3_tree_insert_routel takes the method mask, the path and its length, and matching with r3_tree_match_route returns an R3Route rather than a node:

```c
r3_tree_insert_routel(n, METHOD_GET | METHOD_POST, "/blog/post", sizeof("/blog/post") - 1, &route_data );
```

The function prefix table in the documentation organises the API into families: r3_tree_* for operations on a whole tree, r3_node_* for a single node, r3_edge_* for edges, r3_route_* for the route based operations, and match_entry_* for the request parameter object.

## The benchmark compares against the Rails router proposal

The performance section in the documentation is specific about its provenance, which is worth reading carefully before quoting a number.

The routing benchmark comes from a pull request in stevegraham's rails repository, and the documentation quotes the original figure for omg at 10462.0 per second with a 6.7 percent variation over 52417 iterations in 5.030416 seconds, then the result of the router journey at 9932.9 per second with a 4.8 percent variation.

The R3 benchmark is presented with the same route path data, and the figures quoted are three runs of 5000000 iterations each, finished in 1.308894 seconds, and 11460057.83 iterations per second.

Those two sets of numbers are not directly comparable, and the documentation does not pretend they are. The Rails figures come from a benchmark harness with its own iteration structure and overhead, while the R3 figure is a direct count of matching operations against the compiled tree. The meaningful comparison is against the router journey figure, the one that measures matching rather than the harness, and on that basis R3 is several times faster than the Ruby prototype.

The route data itself is generated by a small Ruby script included in the documentation, which permutes a list of path segments to produce the route set, and the repository carries both gen_routes.rb and gen_route_tests.rb, plus a run-benchmark script and the benchmark HTML page that serves as the project homepage.

The honest summary is that R3's dispatch is fast on a synthetic route set with many shared prefixes, which is the case a trie is built for, and that nobody has published a comparison against the routers people actually use in production.

## MIT, a 2.0 branch, and a release tag from 2014

The maintenance picture needs stating carefully, because the artefacts disagree with each other.

The repository's default branch is 2.0, the package manifest records the version as 2.0.0, and the version is written into the source at build time through config.h.cmake and the r3.pc.in template. But the only GitHub release is 1.0.0, dated 2014-05-21, and the last push to the repository was on 2026-09-15.

So the code is being worked on, and the branch layout says the project is on its second line, but there is no tagged 2.0 release to install. Anyone depending on this has to vendor from the branch and decide for themselves which commit to take.

That is a small project by any measure. The source tree is a handful of files, with src/ holding edge.c, gvc.c, json.c, list.c, match_entry.c, node.c, slug.c, str.c and token.c, and include/ holding r3.h, r3.hpp, r3_gvc.h, r3_json.h, r3_list.h, r3_slug.h, memory.h and str_array.h. The presence of a php/ directory and a package.json whose repository field points at brendanashworth/r3 rather than c9s/r3 suggests the project has been forked and maintained from more than one place.

The licence is MIT, with COPYING and LICENSE files at the root, which is the most permissive option available and means you can vendor the sources into a proprietary project without much ceremony, though your counsel should confirm the terms.

The build and test tooling in the tree gives a good sense of the project's habits: autogen.sh, a Travis configuration, a coveralls badge, a CHANGES.md, HACKING.md and an INSTALL file.

## Conclusion

R3 suits a systems programmer who needs a router inside something that is not a web framework, a proxy, a server with an unusual language, or an embedded component where a small C library with a clear API is worth more than a large dependency. It is the wrong choice if you want routing with batteries included, since R3 matches paths and nothing else, and it is the wrong choice if you need a maintained release stream, since the only tagged release is 1.0.0 from 2014 while the working branch is 2.0. Verify three things before you build on it: that your path patterns fall into the optimized set or that pcre2 is available for the rest, that your build system can produce the library with its autotools or CMake setup, and that the version you vendor from the 2.0 branch is what you want, since the release tags do not describe it.

## FAQ

### What is R3, the C router library?

It is a URL router library implemented in C for performance. It compiles your route paths into a prefix trie at start-up time and then dispatches incoming paths against that tree, and it can capture slug values and match on the HTTP method.

### What does a slug like {id} compile to?

A slug without a pattern is compiled into the [^/]+ regular expression, so it matches a single path segment. You can supply your own pattern with a colon, for example /blog/post/{id:\d+}, which uses the \d+ pattern instead.

### Which regular expressions does R3 optimize?

Simple patterns are translated into small fast scanners by a regexp pattern to opcode translator, which covers [a-z]+, [0-9]+, \d+, \w+, [^/]+, [^-]+ and .*. Complex patterns still use libpcre2, so pcre2 is a runtime requirement.

### What do I need to build and run R3?

The build needs autoconf, automake, check and pkg-config, and the runtime needs pcre2, with graphviz and libjson-c-dev optional. The repository ships both an autotools setup with configure.ac and Makefile.am and a CMakeLists.txt, plus a pkg-config template.

### How do I match a request and read the captured values?

Create a match_entry with match_entry_create, set its request_method if the route is method specific, and pass it to r3_tree_match_entry. The captured variables are pushed into the match entry, and you free it with match_entry_free when you are done.

### Is R3 still maintained, and which version should I use?

The default branch is 2.0 and the last push was on 2026-09-15, but the only tagged GitHub release is 1.0.0 from 2014-05-21, so there is no 2.0 release to install. The licence is MIT, with the licence files at the root of the repository.

## Sources

- [c9s/r3 on GitHub](https://github.com/c9s/r3)
- [License: MIT](https://github.com/c9s/r3/blob/2.0/LICENSE)
- [Project website](https://c9s.github.io/r3/bench.html)
- [README](https://github.com/c9s/r3/blob/2.0/README.md)
- [Releases](https://github.com/c9s/r3/releases)

---

Hysen Labs editorial analysis, written from the project's own repository and release notes. Cite the canonical page: https://hysenlabs.com/projects/c9s-r3