radixtree

A radix tree implementation for router, and provides CRUD operations.

Radixtree is part of treemux, on top of which updates and removes are added.

Usage

Add this to your Cargo.toml:

radixtree = "0.1"

Insert

use radixtree::{Node, Method};

fn main() {
    let mut tree = Node::new();
    tree.insert(Method::GET, "/", "GET");
    tree.insert(Method::POST, "/", "POST");
    tree.insert(Method::PUT, "/", "PUT");
    tree.insert(Method::DELETE, "/", "DELETE");

    let result = tree.search(Method::GET, "/");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"GET");

    let result = tree.search(Method::POST, "/");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"POST");

    let result = tree.search(Method::PUT, "/");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"PUT");

    let result = tree.search(Method::DELETE, "/");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"DELETE");
}

Update

use radixtree::{Node, Method};

fn main() {
    let mut tree = Node::new();
    tree.insert(Method::GET, "/", "GET");
    tree.insert(Method::POST, "/", "POST");
    tree.insert(Method::PUT, "/", "PUT");
    tree.insert(Method::DELETE, "/", "DELETE");

    tree.update(Method::GET, "/", "UPDATE GET");
    tree.update(Method::POST, "/", "UPDATE POST");
    tree.update(Method::PUT, "/", "UPDATE PUT");
    tree.update(Method::DELETE, "/", "UPDATE DELETE");

    let result = tree.search(Method::GET, "/");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"UPDATE GET");

    let result = tree.search(Method::POST, "/");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"UPDATE POST");

    let result = tree.search(Method::PUT, "/");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"UPDATE PUT");

    let result = tree.search(Method::DELETE, "/");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"UPDATE DELETE");
}

Remove

use radixtree::{Node, Method};

fn main() {
    let mut tree = Node::new();
    tree.insert(Method::GET, "/", "GET");
    tree.insert(Method::POST, "/", "POST");
    tree.insert(Method::PUT, "/", "PUT");
    tree.insert(Method::DELETE, "/", "DELETE");

    tree.remove("/");

    let result = tree.search(Method::GET, "/");
    assert!(result.is_none());

    let result = tree.search(Method::POST, "/");
    assert!(result.is_none());

    let result = tree.search(Method::PUT, "/");
    assert!(result.is_none());

    let result = tree.search(Method::DELETE, "/");
    assert!(result.is_none());
}

Parameter Paths

use radixtree::{Node, Method};

fn main() {
    let mut tree = Node::new();
    tree.insert(Method::GET, "/user/$id", "GET");

    let result = tree.search(Method::GET, "/user/1");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"GET");

    tree.update(Method::GET, "/user/$id", "UPDATE GET");

    let result = tree.search(Method::GET, "/user/1");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"UPDATE GET");

    tree.remove("/user/$id");

    let result = tree.search(Method::GET, "/user/1");
    assert!(result.is_none());
}

Wildcard Star

use radixtree::{Node, Method};

fn main() {
    let mut tree = Node::new();
    tree.insert(Method::GET, "/image/*", "GET");

    let result = tree.search(Method::GET, "/image/hello.jpeg");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"GET");

    let result = tree.search(Method::GET, "/image/jpg/hello.jpg");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"GET");

    let result = tree.search(Method::GET, "/image/png/hello.png");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"GET");

    tree.update(Method::GET, "/image/*", "UPDATE GET");

    let result = tree.search(Method::GET, "/image/hello.jpeg");
    assert!(result.is_some());
    assert_eq!(result.unwrap().value(), &"UPDATE GET");

    tree.remove("/image/*");

    let result = tree.search(Method::GET, "/image/hello.jpeg");
    assert!(result.is_none());
}

Match Rules

Some examples of valid URL paths are:

/abc/def
/favicon.ico
/user/$id
/id/$id/name/$name
/$year/$month
/$year/$month/$day
/images/*
/images/$category/*

Note that all of the above URL paths may exist in the radix tree at the same time.

Paths starting with $ indicate parameter paths. Parameter paths only match a single path segment. That is, the path /user/$id will match on /user/1 or /user/2, but not /user/1/2.

Wildcard * can match any path. For example, the path /image/* will match on /image/png/hello.png, /image/jpg/hello.jpg or image/hello.jpeg.

Match Priority

Static paths take the highest priority.
Parameter paths take second priority.
Finally, the wildcard * matches paths where static paths and parameter paths do not match.

Author

Zhenwei Guo (Ilqjx)

License

This project is licensed under the MIT license.

A cargo plugin for showing a tree-like overview of a crate's modules.

cargo-modules Synopsis A cargo plugin for showing an overview of a crate's modules. Motivation With time, as your Rust projects grow bigger and bigger

445 Jan 3, 2023

A minimal `syn` syntax tree pretty-printer

prettyplease::unparse A minimal syn syntax tree pretty-printer. Overview This is a pretty-printer to turn a syn syntax tree into a String of well-form

429 Dec 28, 2022

Embeddable tree-walk interpreter for a "mostly lazy" Lisp-like scripting language.

ceceio Embeddable tree-walk interpreter for a "mostly lazy" Lisp-like scripting language. Just a work-in-progress testbed for now. Sample usage us

7 Aug 18, 2022

Key-value store for embedded systems, for raw NOR flash, using an LSM-Tree.

ekv Key-value store for embedded systems, for raw NOR flash, using an LSM-Tree. Features None yet TODO Everything Minimum supported Rust version (MSRV

16 Nov 22, 2022

A tutorial of building an LSM-Tree storage engine in a week! (WIP)

LSM in a Week Build a simple key-value storage engine in a week! Tutorial The tutorial is available at https://skyzh.github.io/mini-lsm. You can use t