Trie datastructure with utility functions. More...

#include "dtrie.h"
#include "../../dprint.h"
#include "../../mem/shm_mem.h"
#include "../../mem/mem.h"

Include dependency graph for dtrie.c:

Functions

void dtrie_clear (struct dtrie_node_t *root, dt_delete_func_t delete_payload, const unsigned int branches)
Deletes everything but the root node.
void ** dtrie_contains (struct dtrie_node_t *root, const char *number, const unsigned int numberlen, const unsigned int branches)
Check if the trie contains a number.
void dtrie_delete (struct dtrie_node_t *root, struct dtrie_node_t *node, dt_delete_func_t delete_payload, const unsigned int branches)
Deletes a subtree and frees memory including node.
void dtrie_destroy (struct dtrie_node_t **root, dt_delete_func_t delete_payload, const unsigned int branches)
Deletes the whole tree and frees the memory including the root node.
struct dtrie_node_t * dtrie_init (const unsigned int branches)
Allocates memory for the root node and initializes it.
int dtrie_insert (struct dtrie_node_t *root, const char *number, const unsigned int numberlen, void *data, const unsigned int branches)
Insert a number with a corresponding id.
unsigned int dtrie_leaves (const struct dtrie_node_t *root, const unsigned int branches)
Returns the number of leaf nodes in the given tree.
unsigned int dtrie_loaded_nodes (const struct dtrie_node_t *root, const unsigned int branches)
Returns the number of nodes in the given tree that holds custom data.
void ** dtrie_longest_match (struct dtrie_node_t *root, const char *number, const unsigned int numberlen, int *nmatchptr, const unsigned int branches)
Find the longest prefix match of number in root.
unsigned int dtrie_size (const struct dtrie_node_t *root, const unsigned int branches)
Returns the number of nodes in the given tree.

Detailed Description

Provides a generic trie datastructure and utility functions to initialize and manage individual nodes. Its optimized towards the usecase of a matching tree that contains only digits, e.g. for LCR or blacklist modules. Nevertheless it also supports the matching of characters when configured correctly. For normal digit only matching you need to use a branches parameter of 10, when you use 128, the complete standard ascii charset is available for matching. The trie is setup in shared memory.

Module: CARRIERROUTE :: The Kamailio carrierroute Module
Module: USERBLACKLIST :: The Kamailio userblacklist Module

Definition in file dtrie.c.

Function Documentation

void dtrie_clear	(	struct dtrie_node_t *	root,
		dt_delete_func_t	delete_payload,
		const unsigned int	branches
	)

Deletes everything but the root node, the root node is new initialized. This could be used to create an empty tree like after dtrie_init. It also deletes eventual payload on all nodes including the root node.

Parameters:

	root	root node
	delete_payload	pointer to a function for deleting payload. If NULL, it will not be used.
	branches	number of branches in the trie

Definition at line 113 of file dtrie.c.

References dtrie_delete().

Referenced by db_reload_source().

Here is the call graph for this function:

Here is the caller graph for this function:

void** dtrie_contains	(	struct dtrie_node_t *	root,
		const char *	number,
		const unsigned int	numberlen,
		const unsigned int	branches
	)

Parameters:

	root	root node
	number	matched prefix
	numberlen	length of number
	branches	number of branches in the trie

Returns:: the address of the pointer in the tree node if number is found in root, NULL if the number is not found.

Definition at line 249 of file dtrie.c.

References dtrie_longest_match().

Referenced by add_failure_route_to_tree(), and add_route_to_tree().

Here is the call graph for this function:

Here is the caller graph for this function:

void dtrie_delete	(	struct dtrie_node_t *	root,
		struct dtrie_node_t *	node,
		dt_delete_func_t	delete_payload,
		const unsigned int	branches
	)

Parameters:

	root	root node of the whole tree
	node	root of the subtree
	delete_payload	pointer to a function for deleting payload. If NULL, it will not be used.
	branches	number of branches in the trie

Note:: Memory for the root node is not freed.

Definition at line 75 of file dtrie.c.

References dtrie_node_t::child, dtrie_node_t::data, and dtrie_delete().

Referenced by dtrie_clear(), dtrie_delete(), and dtrie_destroy().

Here is the call graph for this function:

Here is the caller graph for this function:

void dtrie_destroy	(	struct dtrie_node_t **	root,
		dt_delete_func_t	delete_payload,
		const unsigned int	branches
	)

Parameters:

	root	root node
	delete_payload	pointer to a function for deleting payload. If NULL, it will not be used.
	branches	number of branches in the trie

Definition at line 101 of file dtrie.c.

References dtrie_delete().

Referenced by create_domain_data(), and destroy_domain_data().

Here is the call graph for this function:

Here is the caller graph for this function:

struct dtrie_node_t* dtrie_init ( const unsigned int branches ) [read]

Parameters:

branches

number of branches in the trie

Returns:: pointer to an initialized root node on success, NULL otherwise.

Definition at line 47 of file dtrie.c.

References dtrie_node_t::child, and root.

Referenced by add_source(), and create_domain_data().

Here is the caller graph for this function:

int dtrie_insert	(	struct dtrie_node_t *	root,
		const char *	number,
		const unsigned int	numberlen,
		void *	data,
		const unsigned int	dtrie_size
	)

Insert a number with a corresponding id. Nodes are created if necessary and the node after the last digit is marked with the given id.

Parameters:

	root	root node
	number	inserted number string
	numberlen	number of individual numbers in number
	data	pointer to some custom data
	branches	number of branches in the trie

Returns:: 0 on success, -1 otherwise.

Definition at line 120 of file dtrie.c.

References dtrie_node_t::child, and dtrie_node_t::data.

Referenced by add_failure_route_to_tree(), add_route_to_tree(), and db_reload_source().

Here is the caller graph for this function:

unsigned int dtrie_leaves	(	const struct dtrie_node_t *	root,
		const unsigned int	branches
	)

Returns the number of leaf nodes in the given tree. On leaf nodes the leaf flag is set, on other nodes it is cleared.

Parameters:

	root	root node
	branches	number of branches in the trie

Returns:: number of leaf nodes

Definition at line 200 of file dtrie.c.

References dtrie_node_t::child, and dtrie_leaves().

Referenced by dtrie_leaves().

Here is the call graph for this function:

Here is the caller graph for this function:

unsigned int dtrie_loaded_nodes	(	const struct dtrie_node_t *	root,
		const unsigned int	branches
	)

Returns the number of nodes in the given tree that are loaded with data (data != NULL).

Parameters:

	root	root node
	branches	number of branches in the trie

Returns:: number of nodes in the tree with custom data

Definition at line 184 of file dtrie.c.

References dtrie_node_t::child, dtrie_node_t::data, and dtrie_loaded_nodes().

Referenced by dtrie_loaded_nodes().

Here is the call graph for this function:

Here is the caller graph for this function:

void** dtrie_longest_match	(	struct dtrie_node_t *	root,
		const char *	number,
		const unsigned int	numberlen,
		int *	nmatchptr,
		const unsigned int	branches
	)

Find the longest prefix match of number in root. Set *data according to value in the tree.

Parameters:

	root	root node
	number	matched prefix
	numberlen	length of number
	nmatchptr	if not NULL store the number of matched digits or -1 if not found.
	branches	number of branches in the trie