• Stars
    star
    799
  • Rank 57,011 (Top 2 %)
  • Language
    C
  • License
    MIT License
  • Created over 10 years ago
  • Updated about 1 year ago

Reviews

There are no reviews yet. Be the first to send feedback to the community and the maintainers!

Repository Details

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

R3

Build Status

Coverage Status

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.

Requirement

Build Requirement

  • autoconf
  • automake
  • check
  • pkg-config

Runtime Requirement

  • pcre
  • (optional) graphviz version 2.38.0 (20140413.2041)
  • (optional) libjson-c-dev

Pattern Syntax

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

API

#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

r3_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 insertion
int data = 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 insertion
    printf("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;
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.
}


// dump the compiled tree
r3_tree_dump(n, 0);

// 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);

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 entry
match_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.

Routing with conditions

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

int route_data = 3;

// insert the R3Route path into the router tree
r3_tree_insert_routel(n, METHOD_GET | METHOD_POST, "/blog/post", sizeof("/blog/post") - 1, &route_data );

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.
}


// 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 end
match_entry_free(entry);
r3_tree_free(n);

Slug

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.

Optimization

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).

Performance

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 Route Paths Of Benchmark

The R3Route path generator is from stevegraham/rails#1:

#!/usr/bin/env ruby
arr    = ["foo", "bar", "baz", "qux", "quux", "corge", "grault", "garply"]
paths  = arr.permutation(3).map { |a| "/#{a.join '/'}" }
paths.each do |path|
    puts "r3_tree_insert_path(n, \"#{path}\", NULL);"
end

Function prefix mapping

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

Rendering Routes With Graphviz

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;
int err;
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.
}

r3_tree_render_file(n, "png", "check_gvc.png");
r3_tree_free(n);

Imgur

Or you can even export it with dot format:

digraph g {
	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];
        ....

Graphviz Related Functions

int r3_tree_render_file(const R3Node * tree, const char * format, const char * filename);

int r3_tree_render(const R3Node * tree, const char *layout, const char * format, FILE *fp);

int r3_tree_render_dot(const R3Node * tree, const char *layout, FILE *fp);

int r3_tree_render_file(const R3Node * tree, const char * format, const char * filename);

JSON Output

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);

const char *json = r3_node_to_json_pretty_string(n);
printf("Pretty JSON: %s\n",json);

const char *json = r3_node_to_json_string(n);
printf("JSON: %s\n",json);

Use case in PHP

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 yet
list($error, $message) = r3_validate($route); // validate R3Route conditions
if ( $error ) {
    echo $message; // "Method not allowed", "...";
}

Install

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

Run Unit Tests

./configure --enable-check
make check

Enable Graphviz

./configure --enable-graphviz

With jemalloc

./configure --with-malloc=jemalloc

ubuntu PPA

The PPA for libr3 can be found in https://launchpad.net/~r3-team/+archive/libr3-daily.

Binding For Other Languages

Node.js

Ruby

License

This software is released under MIT License.

More Repositories

1

Pux

Pux is a fast PHP Router and includes out-of-box controller tools
C
1,272
star
2

bbgo

The modern cryptocurrency trading bot framework written in Go.
Go
1,209
star
3

goprocinfo

Linux /proc info parser for Go
Go
725
star
4

CLIFramework

A powerful command line application framework for PHP. It's an extensible, flexible component, You can build your command-based application in seconds!
PHP
433
star
5

c6

Compile SASS Faster ! C6 is a SASS-compatible compiler
Go
430
star
6

gomon

Monitor for any changes in your go package and automatically restart commands (run, build, server or anything)
Go
214
star
7

vikube.vim

Operating Kubernetes Cluster from Vim, in Vim
Vim Script
197
star
8

Vimana

Vimana is an easy to use system for searching , installing, and downloading vim script. Vimana provides a command-line interface such like aptitude programe on Debian linux, for you to search , download , install , upgrade scripts from http://www.vim.org (vimonline site).
Perl
183
star
9

guts

Guts is a new language beyonds PHP.
Go
156
star
10

GetOptionKit

An object-oriented option parser library for PHP, which supports type constraints, flag, multiple flag, multiple values, required value checking
PHP
144
star
11

SQLBuilder

A powerful, fast, cross-platform SQL Builder for PHP. Convert your structured data into SQL queries with a fluent style interface and targeting on all the mainstream database (MySQL, PostgreSQL, SQLite)
PHP
142
star
12

h3

The Fast HTTP header parser library
C
130
star
13

perlomni.vim

perl omnicompletion for vim (including base class function compleltions .. etc)
Vim Script
128
star
14

github-taiwan

Taiwan Developers on Github
Perl
119
star
15

Roller

A simple, fast router for PHP5.3/4, support APC cache, RESTful, highly extendable and flexible.
PHP
86
star
16

hypergit.vim

This git plugin provides many awesome features so that you don't need to type commands anymore..
Vim Script
61
star
17

App-gh

GitHub Command-line Utility.
Perl
54
star
18

AssetKit

A Modular Asset Toolkit for PHP Applications
HTML
52
star
19

fsrename

FSRename V2 - A simple, powerful rename tool supports complex filtering
Go
51
star
20

xarray

The missing PHP array functions you are looking for, implemented in extension
C
42
star
21

ts-webpack-starter

Template project based on TypeScript, Typings, Babel and Webpack
JavaScript
41
star
22

GenPHP

A Powerful,Flexible Code Generator for PHP, can generate anything what you want for your project.
PHP
40
star
23

CodeGen

Transform your dynamic calls to static calls!
PHP
38
star
24

PHPRelease

PHPRelease manages your package release process.
PHP
32
star
25

requestgen

request builder generator for Go!
Go
32
star
26

cpan.vim

vim plugin for perl hackers. for you to search installed module/all modules and integrated with perldoc window
Vim Script
30
star
27

php-ext-skeleton

The minimal PHP extension skeleton
C
29
star
28

reducer

Fast Map & Reduce php7 extension for large array
C
27
star
29

Plack-Middleware-OAuth

Plack Middleware for OAuth1 and OAuth2
Perl
27
star
30

goenv

Go project environment builder - build isolated workspace for your go project
27
star
31

phpunit.vim

phpunit plugin for Vim editor
Vim Script
25
star
32

callbackgen

callbackgen generates callback pattern for your callback fields.
Go
25
star
33

typeloy

typeloy is a meteor application deployment tool written in typescript.
TypeScript
25
star
34

vim-dev-plugin

A Vim plugin for developing VimL.
Vim Script
25
star
35

cpansearch

CPAN module search in C.
C
24
star
36

vim-makefile

A lightweight non-dependency Makefile for install, uninstall, bundle, distribute Vim plugin scripts.
Vim Script
24
star
37

GoTray

Go application manager in your system status bar. (for Mac OS X)
24
star
38

gsession.vim

gsession.vim saves your session files into the same directory (~/.vim/session/) by default. and auto-detect your session file to load session file when you are opening vim editor without arguments.
Vim Script
24
star
39

FastCommit

Integrating GIT commit flow with your own editor easily!
23
star
40

zh-stroke-data

εΈΈη”¨εœ‹ε­—ζ¨™ζΊ–ε­—ι«”η­†εŠƒ XML 資料ζͺ”
JavaScript
22
star
41

WireRoom

Collaborative Chatroom For Hackers
JavaScript
20
star
42

gatsby

Gatsby Database Toolkit For Go (ORM, SQL Builder and SQLUtils)
Go
20
star
43

SimpleBench

SimpleBench provides suckless benchmark tools for PHP5.3
PHP
20
star
44

WebUI

Abstract PHP interface for building common HTML components with microdata
PHP
20
star
45

markdown-git-wiki

This is a pure git wiki (not a web server or web app), this utility only provides the functionbility of translating markdown pages into web pages. links between pages can be named by "[[Link]]". so your git wiki is just a git repository.
Perl
19
star
46

gitorbit

GitHub-like Git Server, let you control the permission via mongodb or LDAP
Go
18
star
47

jira.sh

JIRA Client for Bash Scripts
Shell
18
star
48

perldoc-zhtw-translation

Perldoc Translation in zh-tw
Perl
18
star
49

LazyBone

MicroFramework: LazyRecord + BackBone + Roller RESTful Router
JavaScript
18
star
50

php-r3

high performance r3 router extension for PHP
C
17
star
51

colorselector.vim

provide emacs-like colorscheme selector buffer.
Makefile
17
star
52

jchash

Jump Consistent Hashing Algorithm implemented in PHP 7 Extension
C
16
star
53

ClassMap

Generate class mapping file in PHP, to improve classloader performance.
PHP
16
star
54

router-benchmark

PHP Router Benchmark
PHP
14
star
55

rockhopper

rockhopper is an embeddable migration tool written by Go
Go
14
star
56

go-aes-crypt

Go
13
star
57

php-FastRequire

SPL class loader is slow! Now you can skip the SPL functions to load your minimal class requirements directly.
13
star
58

GrindKit

PHP GrindKit for reading cachegrind compatible file.
PHP
13
star
59

MiniPear

MiniPear creates local pear channel mirrors for offline usage.
PHP
12
star
60

simple-commenter.vim

simple commenter plugin
Vim Script
11
star
61

cascading.vim

Vim Script
11
star
62

ConfigKit

Toolkit for Config Files, use fast but readable YAML config file for your PHP project.
PHP
11
star
63

ClassTemplate

Class template for PHP
PHP
11
star
64

umobi

Β΅Mobi - Micro Mobile Web Framework for Smartphones & Tablets.
JavaScript
10
star
65

xfile

PHP Extension for file operations
C
10
star
66

PJSON

PJSONEncoder implements a JSON encoder with PHP object to JavaScript object translation support.
PHP
10
star
67

kubernetes-term

Connecting xterm.js to kubernetes exec spdy stream with socket.io
Go
9
star
68

perl-poppler

basic porting of poppler
Perl
9
star
69

phpkmp

Knuth-Morris-Pratt algorithm implemented in C, PHP and PHP Extension
C
9
star
70

PerlTW-Planet

Perl Taiwan Planet
CSS
9
star
71

vagrant-kubeadm

Vagrant for kubeadm
Shell
8
star
72

sid

Sequential ID generator as a micro-service, implemented in Go
Go
8
star
73

Git-Release

A Git Release Manager
Perl
8
star
74

ZLogger

A Simple Logger for PHP based on ZeroMQ
PHP
8
star
75

d3-kmeans

A simple, lightweight, single-dimension k-means clustering algorithm implemented in javascript for d3.
JavaScript
8
star
76

alpine-dlib

base image for dlib application
Shell
8
star
77

lftp-sync.vim

lftp sync plugin for vim.
Vim Script
8
star
78

vimomni.vim

a better completion for VimL.
Vim Script
8
star
79

requestgen-tutorial

Go
8
star
80

universal

The general purpose standard library for PHP.
PHP
8
star
81

glusterfs-deploy

Shell
7
star
82

inflect

Inflector for Go
Go
7
star
83

taipei.pm

Taipei.pm
Perl
7
star
84

ssh-authorizedkey

AuthorizedKey Encoder implemented in Go
Go
7
star
85

chrome-extension-template

7
star
86

action-js

The powerful javascript library for connecting form components with backend protocols.
JavaScript
7
star
87

bufexplorer

Vim Script
7
star
88

more.vim

δΈ€η”¨ε°±ζ„›δΈŠηš„δΈ­ζ–‡ε‡ζ–‡η”’η”Ÿε™¨δΉ‹ Vim Plugin
Vim Script
7
star
89

c9s

7
star
90

Kendo

The Powerful Access Control Framework
PHP
7
star
91

CacheKit

Generic cache interface for FileSystem cache, Memcached, ApcCache, ... etc
PHP
7
star
92

VersionKit

Version String Utilities
PHP
7
star
93

PHPUnit_TestMore

let you define Test::More-like unit tests and base on the great PHPUnit testing framework.
PHP
7
star
94

dlib-serving

Run dlib model inference as a gRPC server
CMake
7
star
95

CurlKit

A tiny curl based library for managing request/response/download task.
PHP
7
star
96

zhwrap.vim

Chinese text wrapping vim plugin.
Vim Script
6
star
97

go-duck

Duck Typing for Go
Go
6
star
98

model-serving-proto

gRPC protobuf files that define the common model serving interface
Python
6
star
99

OAuthProvider

PHP
6
star
100

php-fileutil

Fast File Utility Functions in PHP Extension and Pure PHP.
C
6
star