tree.h File Reference

#include "request_parser.h"
#include "response.h"

Go to the source code of this file.

Data Structures
struct	node

Typedefs
typedef void(*	callback_t) (request, response *)
typedef struct node	node

Functions
node *	find_node_by_val (node *n, char *val)
	gets the node that matches a given val in a DFS manner
node *	trace_tree (char route[], node *origin_node)
	given a route, return the deepest node that exists in the tree that satisfies the route
node *	trace_tree_exact (char route[], node *root)
	returns the node of the last segment in the URI. If a complete trace isn't found, return null.
void	destroy_tree (node *n)
	Given a root node, deallocate the entire tree.
void	print_tree (node *n, int level)
	Given a root node, print the entire tree in a DFS manner, along with the level of each node.

Typedef Documentation

node

typedef struct node node

Conceptual

If we imagine A single URI is a linked list of nodes, then every registered URI on the server is an N-ary tree of nodes. This N-ary tree is how I've implemented URIs in this library.

Example

In the example below, some will have a child of silly, and silly will have a sibling of goofy. Both silly and goofy have their own children of uri (Note how every node will only point to one other node as "children", even though conceptually there can be many children via siblings). Assume every node has a callback, then the following endpoints will be served.

1. /some
2. /some/silly
3. /some/silly/uri
4. /some/goofy
5. /some/goofy/uri

Legend:
--> : left's "children" points to right
|
v : top's "siblings" points to bottom

some --> silly --> uri
          |
          v
         goofy --> uri

Function Documentation

find_node_by_val()

node * find_node_by_val	(	node *	n,
		char *	val )

gets the node that matches a given val in a DFS manner

Parameters

n	the root of the tree to start searching
val	the string to look for

trace_tree()

node * trace_tree	(	char	route[],
		node *	origin_node )

given a route, return the deepest node that exists in the tree that satisfies the route

Parameters

route

the full route that you wish to find in the tree

Given a route, this function will traverse the tree in a DFS manner, using the route as a guide. As the tree is traversed, currNode is updated to be the most recently found node. When a new currNode is unable to be found, or we've reach the end of the route, return currNode.

trace_tree_exact()

node * trace_tree_exact	(	char	route[],
		node *	root )

returns the node of the last segment in the URI. If a complete trace isn't found, return null.

This is very similar to trace_tree. The key difference is, a node is only returned when the entire route was able to be traced on the tree. This will typically be used for, finding the handling node for an incoming request.