Module radix_tree 

Copyright © 2025-2026 Wenze Wei. All Rights Reserved.

This file is part of Ri. The Ri project belongs to the Dunimd Team.

Licensed under the Apache License, Version 2.0 (the “License”); You may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an “AS IS” BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.

Radix Tree Router

This module implements a Radix Tree (also known as a compact prefix tree) for efficient route matching with O(k) time complexity, where k is the path length.

Key Features

• O(k) Lookup: Route matching is independent of the number of registered routes
• Dynamic Parameters: Supports :param for named path segments
• Wildcard Routes: Supports *path for catching all remaining path segments
• Method-based Routing: Each HTTP method has its own radix tree
• Thread-safe: Uses RwLock for safe concurrent access

Path Pattern Syntax

• /users/:id - Matches /users/123, extracts id = "123"
• /files/*path - Matches /files/docs/readme.txt, extracts path = "docs/readme.txt"
• /api/v1/users - Exact match for static paths

Algorithm

The radix tree stores path segments as nodes, sharing common prefixes:

Root
├── api
│   └── v1
│       ├── users (handler)
│       └── users/
│           └── :id (handler with param extraction)
└── health (handler)

Structs

PathSegment

Represents a single segment in a path pattern.

RadixNode

A node in the radix tree.

RiRadixTree

A Radix Tree for efficient route matching.

RouteMatch

Result of a route match operation.

Enums

SegmentType

Represents the type of a path segment in the radix tree.