struct Oak::Tree(T)

Overview

A high-performance radix tree (compressed trie) for path matching.

Oak::Tree is optimized for HTTP routing and similar use cases where:

Example

tree = Oak::Tree(Symbol).new
tree.add "/users/:id", :show_user
tree.add "/users/:id/posts", :user_posts

result = tree.find "/users/123/posts"
result.payload      # => :user_posts
result.params["id"] # => "123"

Performance

See PERFORMANCE.md for detailed benchmarks.

Defined in:

oak/tree.cr

Constructors

Instance Method Summary

Constructor Detail

def self.new #

[View source]

Instance Method Detail

def add(path, payload) #

Adds a path and its associated payload to the tree.

Supports:

  • Static paths: /users/new
  • Named parameters: /users/:id
  • Glob wildcards: /search/*query
  • Optional segments: /products(/free)/:id

Example

tree.add "/users/:id", :show_user
tree.add "/posts/:year/:month/:slug", :show_post
tree.add "/search/*query", :search
tree.add "/products(/free)/:id", :show_product

Multiple payloads can be added to the same path for constraint-based routing.


[View source]
def find(path) : Result(T) #

Finds the first matching result for the given path.

This is optimized for single-match lookups (40-60% less allocation than search().first?). Use this when you only need one result.

Example

result = tree.find "/users/123"
if result.found?
  puts result.payload      # First matching payload
  puts result.params["id"] # => "123"
end

Returns an empty Result if no match found (check with result.found?).


[View source]
def initialize #

[View source]
def search(path) #

Searches the tree and returns all matching results as an array.

Use when you need multiple results (e.g., constraint-based routing). For single matches, prefer #find() for better performance.

Example

results = tree.search "/users/123"
results.each do |result|
  puts result.payload
end

[View source]
def search(path, &block : Result(T) -> _) #

Searches the tree and yields each matching result to the block.

This is more efficient than search(path).each as it doesn't allocate an intermediate array.

Example

tree.search("/users/123") do |result|
  if route = result.payloads.find(&.matches?(request))
    route.call(context)
    break
  end
end

[View source]
def visualize #

Returns a visual representation of the tree structure for debugging.

Example

puts tree.visualize
# ⌙
#   ⌙ /users (payloads: 1)
#     ⌙ /:id (payloads: 1)
#       ⌙ /posts (payloads: 1)

[View source]