ptree.h File Reference

Patricia binary tree for data search. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Typedefs
typedef _apatnode	APATNODE
	Patricia binary tree node, to search related pointer from string.
typedef _patnode	PATNODE
	Another patricia binary tree node, to search integer value from string.
Functions
int	testbit (char *str, int bitplace)
int	where_the_bit_differ (char *str1, char *str2)
PATNODE *	make_ptree (char **words, int *data, int wordsnum, int bitplace)
void	disp_ptree (PATNODE *node, int level)
int	ptree_search_data (char *str, PATNODE *rootnode)
PATNODE *	ptree_make_root_node (int data)
void	ptree_add_entry (char *str, int data, char *matchstr, PATNODE **rootnode)
void	free_ptree (PATNODE *rootnode)
void *	aptree_search_data (char *str, APATNODE *rootnode)
APATNODE *	aptree_make_root_node (void *data)
void	aptree_add_entry (char *str, void *data, char *matchstr, APATNODE **rootnode)
void	aptree_remove_entry (char *str, APATNODE **rootnode)
void	aptree_traverse_and_do (APATNODE *node, void(*callback)(void *))
void	free_aptree (APATNODE *rootnode)

---

Detailed Description

Patricia binary tree for data search.

Author:

Akinobu LEE

Date:

Fri Feb 11 17:27:24 2005

This is a structure to build a patricia binary tree for searching various data or IDs from its name string.

Revision

1.1.1.1

Definition in file ptree.h.

---

Function Documentation

int testbit (  char *  str, int  bitplace )

String bit test function. Parameters: str  [in] key string bitplace  [in] bit location to test Returns: the content of tested bit in tmp_str, either 0 or 1. Definition at line 36 of file ptree.c. Referenced by aptree_add_entry_at(), make_ptree(), ptree_add_entry_at(), and where_the_bit_differ().

int where_the_bit_differ (  char *  str1, char *  str2 )

Find in which bit the two strings differ, starting from the head. Parameters: str1  [in] string 1 str2  [in] string 2 Returns: the bit location in which the string differs. Definition at line 61 of file ptree.c. Referenced by aptree_add_entry(), and ptree_add_entry().

PATNODE* make_ptree (  char **  words, int *  data, int  wordsnum, int  bitplace )

Make a patricia tree for given string arrays. Recursively called by descending the scan bit. Parameters: words  [in] list of word strings data  [in] integer value corresponding to each string in words wordsnum  [in] number of above bitplace  [in] current scan bit. Returns: pointer to the root node index. Definition at line 105 of file ptree.c. Referenced by make_ptree(), and ngram_make_lookup_tree().

void disp_ptree (  PATNODE *  node, int  level )

Output a tree structure in text for debug, traversing pre-order Parameters: node  [in] root index node level  [in] current tree depth Definition at line 168 of file ptree.c. Referenced by disp_ptree().

int ptree_search_data (  char *  str, PATNODE *  node )

Search for the data whose key string matches the given string. Parameters: str  [in] search key string node  [in] root node of index tree Returns: the exactly found integer value, or the nearest one. Definition at line 246 of file ptree.c. Referenced by ngram_lookup_word(), and set_unigram().

PATNODE* ptree_make_root_node (  int  data  )

Make a root node of a index tree. Parameters: data  [in] the first data Returns: the newly allocated root node. Definition at line 268 of file ptree.c. Referenced by ptree_add_entry(), and set_unigram().

void ptree_add_entry (  char *  str, int  data, char *  matchstr, PATNODE **  rootnode )

Insert a new node to the index tree. Parameters: str  [in] new key string data  [in] new data integer value matchstr  [in] the most matching data already exist in the index tree, as obtained by aptree_search_data() rootnode  [i/o] pointer to root index node Definition at line 326 of file ptree.c. Referenced by set_unigram().

void free_ptree (  PATNODE *  node  )

Free all the sub nodes from specified node. Parameters: node  [in] current node. Definition at line 345 of file ptree.c. Referenced by free_ptree(), and ngram_info_free().

void* aptree_search_data (  char *  str, APATNODE *  node )

Search for the data whose key string matches the given string. Parameters: str  [in] search key string node  [in] root node of index tree Returns: the exactly found data pointer, or the nearest one. Definition at line 103 of file aptree.c. Referenced by add_to_error(), cdset_lookup(), codebook_add(), codebook_lookup(), dens_add(), dens_lookup(), hmm_add_physical_to_logical(), hmm_add_pseudo_phones_sub(), htk_hmmdata_add(), htk_hmmdata_lookup_logical(), htk_hmmdata_lookup_physical(), make_hmm_basephone_list(), mark_word_edge(), new_str2phseq(), rdhmmlist(), regist_cdset(), remove_cdset(), state_add(), state_lookup(), trans_add(), trans_lookup(), var_add(), and var_lookup().

APATNODE* aptree_make_root_node (  void *  data  )

Make a root node of a index tree. Parameters: data  [in] the first data Returns: the newly allocated root node. Definition at line 125 of file aptree.c. Referenced by add_to_error(), aptree_add_entry(), codebook_add(), dens_add(), hmm_add_physical_to_logical(), hmm_add_pseudo_phones_sub(), htk_hmmdata_add(), make_hmm_basephone_list(), rdhmmlist(), regist_cdset(), state_add(), trans_add(), and var_add().

void aptree_add_entry (  char *  str, void *  data, char *  matchstr, APATNODE **  rootnode )

Insert a new node to the index tree. Parameters: str  [in] new key string data  [in] new data pointer matchstr  [in] the most matching data already exist in the index tree, as obtained by aptree_search_data() rootnode  [i/o] pointer to root index node Definition at line 183 of file aptree.c. Referenced by add_to_error(), codebook_add(), dens_add(), hmm_add_physical_to_logical(), hmm_add_pseudo_phones_sub(), htk_hmmdata_add(), make_hmm_basephone_list(), rdhmmlist(), regist_cdset(), state_add(), trans_add(), and var_add().

void aptree_remove_entry (  char *  str, APATNODE **  rootnode )

Remove a node from the index tree. Parameters: str  [in] existing key string (must exist in the index tree) rootnode  [i/o] pointer to root index node Definition at line 254 of file aptree.c. Referenced by remove_cdset().

void aptree_traverse_and_do (  APATNODE *  node, void(*)(void *)  callback )

Recursive function to traverse index tree and execute the callback for all the existing data. Parameters: node  [in] current node callback  [in] callback function Definition at line 276 of file aptree.c. Referenced by aptree_traverse_and_do(), count_all_phone(), print_all_basephone_detail(), print_all_basephone_name(), put_all_cdinfo(), test_interword_triphone(), triphone_callback_left(), and wt_tmix().

void free_aptree (  APATNODE *  node  )

Free all the sub nodes from specified node. Parameters: node  [in] current node. Definition at line 296 of file aptree.c. Referenced by free_aptree().

---