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.0"

Insert

```rust 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

```rust 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

```rust 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

```rust 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

```rust 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

1. Static paths take the highest priority.
2. Parameter paths take second priority.
3. 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.