Documentation
¶
Overview ¶
Package radix provides a radix tree (prefix tree) implementation optimized for URL path matching with support for parameterized segments.
The tree provides O(k) lookup complexity where k is the number of path segments (typically 3-5 for REST APIs), making it ideal for routing and path matching.
Example usage:
tree := radix.New[*MyHandler]()
tree.Insert("/users/{id}", handler1)
tree.Insert("/users/{id}/posts", handler2)
handler, path, found := tree.Lookup("/users/123/posts")
// handler = handler2, path = "/users/{id}/posts", found = true
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type PathLookup ¶
type PathLookup interface {
// Lookup finds the PathItem for a given URL path.
// Returns the matched PathItem, the path template (e.g., "/users/{id}"), and whether found.
Lookup(urlPath string) (pathItem *v3.PathItem, matchedPath string, found bool)
}
PathLookup defines the interface for radix tree path matching implementations. The default implementation provides O(k) lookup where k is the path segment count.
Note: This interface handles URL path matching only. HTTP method validation is performed separately after the PathItem is retrieved, since a single path (e.g., "/users/{id}") can support multiple HTTP methods (GET, POST, PUT, DELETE).
type PathTree ¶
type PathTree struct {
// contains filtered or unexported fields
}
PathTree is a radix tree optimized for OpenAPI path matching. It provides O(k) lookup where k is the number of path segments (typically 3-5), with minimal allocations during lookup.
This is a thin wrapper around the generic Tree, specialized for OpenAPI PathItem values. It implements the PathLookup interface.
func BuildPathTree ¶
BuildPathTree creates a PathTree from an OpenAPI document. This should be called once during validator initialization.
func NewPathTree ¶
func NewPathTree() *PathTree
NewPathTree creates a new empty radix tree for path matching.
func (*PathTree) Insert ¶
Insert adds a path and its PathItem to the tree. Path should be in OpenAPI format, e.g., "/users/{id}/posts"
func (*PathTree) Lookup ¶
Lookup finds the PathItem for a given request path. Returns the PathItem, the matched path template, and whether a match was found.
type Tree ¶
type Tree[T any] struct { // contains filtered or unexported fields }
Tree is a radix tree optimized for URL path matching. It supports both literal path segments and parameterized segments like {id}. T is the type of value stored at leaf nodes.
func (*Tree[T]) Insert ¶
Insert adds a path and its associated value to the tree. The path should use {param} syntax for parameterized segments. Examples: "/users", "/users/{id}", "/users/{userId}/posts/{postId}"
Returns true if a new path was inserted, false if an existing path was updated.
func (*Tree[T]) Lookup ¶
Lookup finds the value for a given URL path. Returns the value, the matched path template, and whether a match was found.
Literal matches take precedence over parameter matches per OpenAPI specification. For example, "/users/admin" will match "/users/admin" before "/users/{id}".
Source Files