/*
* $Id: dtrie.h 5237 2008-11-21 10:17:10Z henningw$
*
* Copyright (C) 2008 1&1 Internet AG
*
* This file is part of Kamailio, a free SIP server.
*
* Kamailio is free software; you can redistribute it and/or modify
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version
*
* Kamailio is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
*/

/**
* \file
* \brief Trie datastructure with utility functions
*
* 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: \ref carrierroute
* - Module: \ref userblacklist
*/

#ifndef _DTRIE_H_
#define _DTRIE_H_

/*! Trie node */
struct dtrie_node_t {
struct dtrie_node_t **child; /*!< children */
void *data; /*!< custom data */
};

/*! Function signature for destroying the payload. First parameter is the payload. */
typedef void(*dt_delete_func_t)(void *);

/*!
* \brief Allocates memory for the root node and initializes it
* \param branches number of branches in the trie
* \return pointer to an initialized root node on success, NULL otherwise.
*/
struct dtrie_node_t *dtrie_init(const unsigned int branches);

/*!
* \brief Deletes a subtree and frees memory including node
* \param root root node of the whole tree
* \param node root of the subtree
* \param delete_payload pointer to a function for deleting payload. If NULL, it will not be used.
* \param branches number of branches in the trie
* \note Memory for the root node is not freed.
*/
void dtrie_delete(struct dtrie_node_t *root, struct dtrie_node_t *node,
dt_delete_func_t delete_payload, const unsigned int branches);

/*!
* \brief Deletes the whole tree and frees the memory including the root node
* \param root root node
* \param delete_payload pointer to a function for deleting payload. If NULL, it will not be used.
* \param branches number of branches in the trie
*/
void dtrie_destroy(struct dtrie_node_t **root, dt_delete_func_t delete_payload,
const unsigned int branches);

/*!
* \brief Deletes everything but the root node
*
* 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.
* \param root root node
* \param delete_payload pointer to a function for deleting payload. If NULL, it will not be used.
* \param branches number of branches in the trie
*/
void dtrie_clear(struct dtrie_node_t *root, dt_delete_func_t delete_payload,
const unsigned int branches);

/*!
* \brief Insert a number with a corresponding id
*
* 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.
* \param root root node
* \param number inserted number string
* \param numberlen number of individual numbers in number
* \param data pointer to some custom data
* \param branches number of branches in the trie
* \return 0 on success, -1 otherwise.
*/
int dtrie_insert(struct dtrie_node_t *root, const char *number, const unsigned int numberlen,
void *data, const unsigned int dtrie_size);

/*!
* \brief Returns the number of nodes in the given tree
* \param root root node
* \param branches number of branches in the trie
* \return number of nodes in tree, at least 1
*/
unsigned int dtrie_size(const struct dtrie_node_t *root, const unsigned int branches);

/*!
* \brief Returns the number of nodes in the given tree that holds custom data.
*
* Returns the number of nodes in the given tree that are loaded with data (data != NULL).
* \param root root node
* \param branches number of branches in the trie
* \return number of nodes in the tree with custom data
*/
unsigned int dtrie_loaded_nodes(const struct dtrie_node_t *root, const unsigned int branches);

/*!
* \brief Returns the number of leaf nodes in the given tree
*
* Returns the number of leaf nodes in the given tree.
* On leaf nodes the leaf flag is set, on other nodes it is cleared.
* \param root root node
* \param branches number of branches in the trie
* \return number of leaf nodes
*/
unsigned int dtrie_leaves(const struct dtrie_node_t *root, const unsigned int branches);

/*!
*\brief Find the longest prefix match of number in root.
*
* Find the longest prefix match of number in root.
* Set *data according to value in the tree.
* \param root root node
* \param number matched prefix
* \param numberlen length of number
* \param nmatchptr if not NULL store the number of matched digits or -1 if not found.
* \param branches number of branches in the trie
* \return the address of the pointer in the tree node if number is found in root, NULL if the number is not found.
*/
void **dtrie_longest_match(struct dtrie_node_t *root, const char *number,
const unsigned int numberlen, int *nmatchptr, const unsigned int branches);

/*!
* \brief Check if the trie contains a number
* \param root root node
* \param number matched prefix
* \param numberlen length of number
* \param branches number of branches in the trie
* \return the address of the pointer in the tree node if number is found in root, NULL if the number is not found.
*/
void **dtrie_contains(struct dtrie_node_t *root, const char *number,
const unsigned int numberlen, const unsigned int branches);

#endif