Router implementation using a radix tree (trie) for URL path matching. More...

#include <stdlib.h>
#include <string.h>
#include "context_internal.h"
#include "csilk/core/internal.h"
#include "csilk/csilk.h"

Include dependency graph for router.c:

Data Structures
struct	csilk_router_node_t
	Node in the router trie — represents a URL path segment. More...

Macros
#define	CSILK_MAX_CHILDREN 128
	Maximum number of children per router tree node.

Enumerations
enum	csilk_node_type_t { CSILK_NODE_STATIC , CSILK_NODE_PARAM , CSILK_NODE_WILDCARD }
	Node type for router trie. More...

Functions
static csilk_router_node_t *	node_new (const char *segment, csilk_node_type_t type)
	Create a new router trie node.

static void	node_free (csilk_router_node_t *node)
	Recursively free a router trie node and all its descendants.

static const char *	get_next_segment (const char *p, size_t len)
	Extract the next path segment from a URL path string.

csilk_router_t *	csilk_router_new ()
	Create a new router instance with an empty root ("") static node.

void	csilk_router_free (csilk_router_t *r)
	Free a router instance and all its trie nodes.

static void	node_collect_routes (csilk_router_node_t node, cJSON routes)
	Internal: recursively traverse the trie and collect all route metadata.

cJSON *	csilk_router_collect_routes (csilk_router_t *r)
	Collect all registered routes from the router tree as a cJSON array.

static void	router_add_full (csilk_router_t r, const char method, const char path, csilk_handler_t handlers, size_t handler_count, const char path_pattern, const char input_type, const char output_type, const char summary, const char description, const char perm_required, const char *perm_resource)
	Register a route with method, path pattern, handler chain, and optional OpenAPI metadata.

void	csilk_router_add_extended (csilk_router_t r, const char method, const char path, csilk_handler_t handlers, size_t handler_count, const char path_pattern, const char input_type, const char output_type, const char summary, const char *description)
	Register a route with full OpenAPI/reflection metadata.

void	csilk_router_add (csilk_router_t r, const char method, const char path, csilk_handler_t handlers, size_t handler_count)
	Register a route with method, path pattern, and handler chain (no OpenAPI metadata).

void	csilk_router_add_perm (csilk_router_t r, const char method, const char path, csilk_handler_t handlers, size_t handler_count, const char perm_required, const char perm_resource)
	Register a route with permission metadata.

void	csilk_router_add_extended_perm (csilk_router_t r, const char method, const char path, csilk_handler_t handlers, size_t handler_count, const char path_pattern, const char input_type, const char output_type, const char summary, const char description, const char perm_required, const char *perm_resource)
	Register a route with full metadata including permissions.

static csilk_handler_t *	match_node (csilk_router_node_t node, const char method, const char path, csilk_ctx_t ctx, csilk_method_handler_t **out_mh)
	Recursively match a request path against the trie from the given node.

csilk_handler_t *	csilk_router_match (csilk_router_t r, const char method, const char *path)
	Match a method+path against the routing table (standalone, no context).

int	csilk_router_match_ctx (csilk_router_t r, csilk_ctx_t c)
	Match the current request context against the routing table and populate path params.

Detailed Description

Router implementation using a radix tree (trie) for URL path matching.

Copyright: MIT License

=== Architecture Overview ===

The router organises registered URL patterns into a compressed trie (radix tree). Each node represents a single path segment, and the path from root to a handler-holding node encodes the full route pattern.

Node types (csilk_node_type_t): STATIC - Matches a literal segment, e.g. "users", "api", "v1". Comparison is a simple strcmp against the request segment. PARAM - Matches any single segment; the matched value is captured as a named parameter. Identified by a ':' prefix in the registered pattern (e.g., "/:id" -> segment="id"). WILDCARD - Matches the remainder of the path (one or more segments). Identified by a '*' prefix (e.g., "WILDCARD filepath"). Once a wildcard node is reached, matching stops and the entire tail of the URL is captured as a single parameter.

Insertion (router_add_full): The path is split into segments by '/'. For each segment, the algorithm checks whether a child node of the same type and segment name already exists. If not, a new node is created and appended. The method handler chain is stored at the final (leaf) node.

Matching (match_node): Recursive depth-first search with backtracking. At each node, the next segment from the request path is extracted via get_next_segment(). The algorithm tries all children in order: STATIC children are compared exactly; PARAM children always match (capturing the segment value); WILDCARD children match the remaining path and terminate the search. When a PARAM branch fails deeper in the tree, the capture is rolled back (params_count decremented, memory freed) so sibling STATIC or PARAM nodes can be tried. The first successful match is returned.

Priority / ordering: Children are tried in insertion order. STATIC and PARAM nodes at the same depth are both explored, but STATIC is attempted first if inserted before a corresponding PARAM. For well-defined priority, register STATIC routes before PARAM routes at the same level. WILDCARD nodes terminate the path and are tried as a fallback.

Data Structure Documentation

◆ csilk_router_node_s

struct csilk_router_node_s

Node in the router trie — represents a URL path segment.

Opaque router node type.

The router uses a radix tree (trie) structure where each node represents a path segment. Nodes can be static (e.g., "users"), parameterized (e.g., ":id"), or wildcard (e.g., "*"). Each node stores handlers for matching HTTP methods at that path.

Nodes form a compressed radix tree (Patricia trie) for efficient path matching. Each node may hold handlers for one or more HTTP methods.

Collaboration diagram for csilk_router_node_t:

[legend]

Data Fields
struct csilk_router_node_s *	children[CSILK_MAX_CHILDREN]	Child nodes array.
int	children_count	Number of child nodes.
csilk_method_handler_t *	handlers	Method handlers for this node.
char *	segment	URL path segment.
csilk_node_type_t	type	Type of node (static/param/wildcard).

Macro Definition Documentation

◆ CSILK_MAX_CHILDREN

#define CSILK_MAX_CHILDREN 128

Maximum number of children per router tree node.

Enumeration Type Documentation

◆ csilk_node_type_t

enum csilk_node_type_t

Node type for router trie.

CSILK_NODE_STATIC - Matches a literal path segment (e.g., "users"). strcmp equality is required for a match. CSILK_NODE_PARAM - Matches any single path segment. The segment name (without ':' prefix) becomes the parameter key. e.g., ":id" captures "42" as ctx->params["id"]. CSILK_NODE_WILDCARD - Matches the remainder of the URL path (any number of segments including none). The segment name (without '*' prefix) becomes the parameter key. e.g., "WILDCARD path" captures "foo/bar/baz" for request "/foo/bar/baz". Wildcard is terminal and always tried last during matching.

Enumerator
CSILK_NODE_STATIC
CSILK_NODE_PARAM
CSILK_NODE_WILDCARD

Function Documentation

◆ csilk_router_add()

void csilk_router_add	(	csilk_router_t *	r,
		const char *	method,
		const char *	path,
		csilk_handler_t *	handlers,
		size_t	handler_count
	)

Register a route with method, path pattern, and handler chain (no OpenAPI metadata).

Register a route with one or more handlers.

Convenience wrapper around csilk_router_add_extended() that passes NULL for all optional metadata fields.

Parameters

r	The router instance.
method	HTTP method.
path	URL path pattern.
handlers	Array of handler functions.
handler_count	Number of handlers.

◆ csilk_router_add_extended()

void csilk_router_add_extended	(	csilk_router_t *	r,
		const char *	method,
		const char *	path,
		csilk_handler_t *	handlers,
		size_t	handler_count,
		const char *	path_pattern,
		const char *	input_type,
		const char *	output_type,
		const char *	summary,
		const char *	description
	)

Register a route with full OpenAPI/reflection metadata.

Extended version of csilk_router_add that also stores metadata for automatic OpenAPI spec generation and request/response binding.

Parameters

r	Router instance.
method	HTTP method string.
path	URL pattern (e.g., "/users/:id").
handlers	Array of handler functions.
handler_count	Number of handlers in `handlers`.
path_pattern	Canonical path pattern string for documentation (may differ from the radix-tree path).
input_type	Registered type name for request-body binding (NULL if there is no request body).
output_type	Registered type name for response serialisation (NULL if raw response is used).
summary	Short summary of the operation (NULL to omit from spec).
description	Detailed description of the operation (NULL to omit).

◆ csilk_router_add_extended_perm()

void csilk_router_add_extended_perm	(	csilk_router_t *	r,
		const char *	method,
		const char *	path,
		csilk_handler_t *	handlers,
		size_t	handler_count,
		const char *	path_pattern,
		const char *	input_type,
		const char *	output_type,
		const char *	summary,
		const char *	description,
		const char *	perm_required,
		const char *	perm_resource
	)

Register a route with full metadata including permissions.

Combines csilk_router_add_extended with permission metadata in a single call. The permission fields are used by csilk_perm_auto_middleware.

Parameters

r	The router instance.
method	HTTP method.
path	URL path pattern.
handlers	Array of handler functions.
handler_count	Number of handlers.
path_pattern	Original path pattern for OpenAPI metadata.
input_type	Registered type name for request body, or NULL.
output_type	Registered type name for response body, or NULL.
summary	OpenAPI operation summary, or NULL.
description	OpenAPI operation description, or NULL.
perm_required	Permission identifier (e.g., "read"), or NULL.
perm_resource	Resource pattern (e.g., "users:*"), or NULL.

◆ csilk_router_add_perm()

void csilk_router_add_perm	(	csilk_router_t *	r,
		const char *	method,
		const char *	path,
		csilk_handler_t *	handlers,
		size_t	handler_count,
		const char *	perm_required,
		const char *	perm_resource
	)

Register a route with permission metadata.

Same as csilk_router_add but also stores permission requirement for interface-level access control. The auto-check middleware (csilk_perm_auto_middleware) reads these fields at request time.

Parameters

r	The router instance.
method	HTTP method.
path	URL path pattern.
handlers	Array of handler functions.
handler_count	Number of handlers.
perm_required	Permission identifier (e.g., "read", "write"), or NULL.
perm_resource	Resource pattern (e.g., "users:*"), or NULL.

◆ csilk_router_collect_routes()

cJSON * csilk_router_collect_routes ( csilk_router_t * r )

Collect all registered routes from the router tree as a cJSON array.

Traverses the entire trie and returns a JSON array where each element is an object with method, path, input_type, output_type, summary, and description fields.

Parameters

r	The router instance.

Returns: A cJSON array of route objects. Caller must free with cJSON_Delete(). Returns NULL if the router is NULL or allocation fails.

◆ csilk_router_free()

void csilk_router_free ( csilk_router_t * r )

Free a router instance and all its trie nodes.

Destroy the router and release all its resources.

Recursively frees the entire trie starting from the root node, then frees the router struct itself.

Parameters

r	The router to free (may be NULL).

◆ csilk_router_match()

csilk_handler_t * csilk_router_match	(	csilk_router_t *	r,
		const char *	method,
		const char *	path
	)

Match a method+path against the routing table (standalone, no context).

Match a raw method+path to handlers (standalone, no context).

Direct matching without populating path parameters. Useful for checking whether a route exists without processing a full request.

Parameters

r	The router instance.
method	HTTP method.
path	URL path.

Returns: Pointer to the handler array if matched, NULL otherwise.

Note: No parameter capture is performed since no context is provided.

◆ csilk_router_match_ctx()

int csilk_router_match_ctx	(	csilk_router_t *	r,
		csilk_ctx_t *	c
	)

Match the current request context against the routing table and populate path params.

Match the current request against the router and update the context.

Sets the context's handlers array, handler index (reset to -1), and current_handler metadata on a successful match. Path parameters are captured into the context's params array.

Parameters

r	The router instance.
c	The request context (must have method and path set).

Returns: 1 if a matching route was found, 0 otherwise.

Note: On success, the context is ready for csilk_next() to begin handler execution. On failure, the caller should send a 404 response.

◆ csilk_router_new()

csilk_router_t * csilk_router_new ( void )

Create a new router instance with an empty root ("") static node.

Create a new empty router.

Returns: A new csilk_router_t, or NULL on allocation failure.

Note: The router must be freed with csilk_router_free(). The root node is a static node with an empty segment, representing the root "/".

◆ get_next_segment()

static const char * get_next_segment	(	const char **	p,
		size_t *	len
	)

static

Extract the next path segment from a URL path string.

get_next_segment is the bridge between the raw URL path and the trie traversal. It consumes one segment at a time, providing the atomic unit that each trie node represents.

Behaviour:

Skip all leading '/' characters — this normalises paths such as "//foo//bar" into the same segments as "/foo/bar".
If the remaining string is empty after skipping slashes, return NULL (no more segments).
Record the start pointer, then advance until the next '/' or end-of-string. The characters in between form one segment.
Allocate and return a heap copy of that segment.
Advance the caller's pointer (p) past the consumed segment so that repeated calls walk sequentially through the path.

Example: for path "/users/42/profile" Call 1: returns "users", p -> "/42/profile" Call 2: returns "42", p -> "/profile" Call 3: returns "profile", p -> "" Call 4: returns NULL

Edge cases:

Leading slashes are always skipped, so path "/" yields NULL (zero segments), matching the root node.
Paths with trailing slashes like "/users/" return "users" then NULL — the trailing '/' is consumed but produces no segment.

Parameters

p	[in/out] Pointer to the current position in the path string. Updated to point past the extracted segment.
len	[out] Pointer to receive the length of the segment.

Returns: A pointer to the start of the segment within the original path string, or NULL if no more segments are found.

◆ match_node()

static csilk_handler_t * match_node	(	csilk_router_node_t *	node,
		const char *	method,
		const char *	path,
		csilk_ctx_t *	ctx,
		csilk_method_handler_t **	out_mh
	)

static

Recursively match a request path against the trie from the given node.

This is the core matching function. It implements a depth-first, backtracking search over the radix tree:

Base case: if the remaining path is empty, "/", or NULL, check whether the current node has a handler for the given HTTP method. If so, return it — this is a successful terminal match.
Extract the next segment from the request path via get_next_segment().
Try children in insertion order. For each child:
- STATIC: match if child->segment == extracted segment (strcmp).
- PARAM: always match; capture segment value into ctx->params.
- WILDCARD: always match; capture the entire remaining path into ctx->params. Since wildcard consumes everything, check its handlers directly (no further recursion).
Recurse: if the child matches, call match_node() on it with the remaining path pointer (p). Propagate the result back up.
Backtrack: if recursion returns NULL (no handler found deeper), undo any PARAM capture that was made for this branch (decrement params_count, free key/value strings). Continue to the next sibling child.
If no child matches or all branches return NULL, free the segment and return NULL — no route matched.

=== Why backtracking matters === Consider routes: GET /users/:id (PARAM) GET /users/me (STATIC) Request: GET /users/me

The algorithm tries STATIC "me" first (if inserted first). If STATIC has a handler for GET, it is returned immediately. If STATIC had no handler, the search backtracks and tries PARAM ":id", which matches "me" as a parameter. This ensures STATIC routes take priority over PARAM routes when both could match.

Parameters

node	Current trie node to match against.
method	HTTP method to match.
path	Remaining path string (may be "" or "/" for exact match).
ctx	Request context for parameter capture (may be NULL for standalone matching).
out_mh	[out] Optional pointer to receive the matched method handler metadata (for OpenAPI metadata access).

Returns: Pointer to the NULL-terminated handler array, or NULL if no match.

Note: Parameter and wildcard values are strdup'd and must be freed by the caller (or during csilk_ctx_cleanup()).

◆ node_collect_routes()

static void node_collect_routes	(	csilk_router_node_t *	node,
		cJSON *	routes
	)

static

Internal: recursively traverse the trie and collect all route metadata.

For each node, iterates the method handler linked list and adds a route object (method, path, input_type, output_type, summary, description) to the cJSON array. Then recurses into child nodes.

Parameters

node	Current trie node.
routes	cJSON array to append route objects to.

◆ node_free()

static void node_free ( csilk_router_node_t * node )

static

Recursively free a router trie node and all its descendants.

Frees the segment string, the linked list of method handlers (including method, handlers array, and path strings), recursively frees all child nodes, and finally frees the node itself.

Parameters

node	The node to free (may be NULL).

◆ node_new()

static csilk_router_node_t * node_new	(	const char *	segment,
		csilk_node_type_t	type
	)

static

Create a new router trie node.

Allocates and initializes a node with the given path segment and type. The segment string is duplicated internally.

Parameters

segment	The path segment name (e.g., "users", "id" for ":id").
type	The node type (static, param, or wildcard).

Returns: A new csilk_router_node_t, or NULL on allocation failure.

Note: The returned node must be freed with node_free().

◆ router_add_full()

static void router_add_full	(	csilk_router_t *	r,
		const char *	method,
		const char *	path,
		csilk_handler_t *	handlers,
		size_t	handler_count,
		const char *	path_pattern,
		const char *	input_type,
		const char *	output_type,
		const char *	summary,
		const char *	description,
		const char *	perm_required,
		const char *	perm_resource
	)

static

Register a route with method, path pattern, handler chain, and optional OpenAPI metadata.

Walks the path string, segment by segment, inserting nodes into the trie. Path segments prefixed with ':' are treated as parameters (e.g., "/:id"), and segments prefixed with '*' are treated as wildcards that match the remainder of the path (e.g., "/assets/star-path"). The method handler is stored at the final node with the provided metadata. If a route with the same method already exists at the same path, the new registration is silently ignored (no override).

Parameters

r	The router instance.
method	HTTP method (e.g., "GET", "POST").
path	URL path pattern (e.g., "/users/:id").
handlers	Array of handler functions (NULL-terminated).
handler_count	Number of handlers (excluding the NULL terminator).
path_pattern	Original path pattern for OpenAPI metadata (may differ from `path` if prefix was prepended by group).
input_type	Registered type name for request body, or NULL.
output_type	Registered type name for response body, or NULL.
summary	OpenAPI operation summary, or NULL.
description	OpenAPI operation description, or NULL.

Note: The router does NOT support overriding an existing route — duplicate method+path registrations are silently dropped.; The handler array is copied; the caller may free it after this call.

Data Structures

Macros

Enumerations

Functions

Detailed Description

Data Structure Documentation

◆ csilk_router_node_s

Macro Definition Documentation

◆ CSILK_MAX_CHILDREN

Enumeration Type Documentation

◆ csilk_node_type_t

Function Documentation

◆ csilk_router_add()

◆ csilk_router_add_extended()

◆ csilk_router_add_extended_perm()

◆ csilk_router_add_perm()

◆ csilk_router_collect_routes()

◆ csilk_router_free()

◆ csilk_router_match()

◆ csilk_router_match_ctx()

◆ csilk_router_new()

◆ get_next_segment()

◆ match_node()

◆ node_collect_routes()

◆ node_free()

◆ node_new()

◆ router_add_full()