radix_route_matcher

A high-performance route matching library based on Radix Tree (compressed trie) data structure.

Features

• High Performance: Based on Redis's rax implementation in C
• Multiple Match Modes: Exact match, longest prefix match, and iterator-based matching
• Safe Rust API: High-level safe wrapper around C implementation
• C ABI Compatible: Can be used from C/C++ or other FFI-capable languages
• Unicode Support: Full UTF-8 support including Chinese characters

Installation

Add this to your Cargo.toml:

[dependencies]
radix_route_matcher = "0.1"

Usage

Basic Usage

use radix_route_matcher::RadixTree;

let mut tree = RadixTree::new().expect("Failed to create tree");

// Insert routes
tree.insert("/api", 1).unwrap();
tree.insert("/api/users", 2).unwrap();
tree.insert("/api/posts", 3).unwrap();

// Create an iterator for prefix matching operations
let iter = tree.create_iter().unwrap();

// Exact match
assert_eq!(tree.find_exact("/api/users"), Some(2));

// Longest prefix match
assert_eq!(tree.longest_prefix(&iter, "/api/users/123"), Some(2));

// Get all matching prefixes
let matches = tree.find_all_prefixes(&iter, "/api/users/123/profile");
assert_eq!(matches, vec![2, 1]); // ["/api/users", "/api"]

Iterator-Style Matching

use radix_route_matcher::RadixTree;

let mut tree = RadixTree::new().unwrap();
tree.insert("/", 1).unwrap();
tree.insert("/api", 2).unwrap();
tree.insert("/api/v1", 3).unwrap();

let iter = tree.create_iter().unwrap();
let path = "/api/v1/users";
if tree.search(&iter, path) {
    while let Some(idx) = tree.next_prefix(&iter, path) {
        println!("Matched route: {}", idx);
    }
}

Performance

• Insert: O(k) where k is the key length (~447ns per route)
• Query: O(k) where k is the key length (~226ns per query)
• Space: Efficient prefix compression, shared prefixes stored once

API Reference

RadixTree

C API

This library also exports a C-compatible API for use from other languages:

void* radix_tree_new();
int radix_tree_destroy(void* t);
int radix_tree_insert(void* t, const unsigned char* buf, unsigned long len, int idx);
void* radix_tree_find(void* t, const unsigned char* buf, unsigned long len);
int radix_tree_remove(void* t, const unsigned char* buf, unsigned long len);
void* radix_tree_new_it(void* t);
void* radix_tree_search(void* tree, void* it, const unsigned char* buf, unsigned long len);
int radix_tree_up(void* it, const unsigned char* buf, unsigned long len);

License

This project is licensed under the MIT License - see the LICENSE file for details.

This project includes code from the Redis rax implementation by Salvatore Sanfilippo, which is also under a BSD-style license.

Acknowledgments

• Redis rax - The underlying radix tree implementation