libsent/include/sent/ptree.h File Reference

Patricia binary tree for data search. More...

Go to the source code of this file.

Data Structures

struct  APATNODE
 Patricia binary tree node, to search related pointer from string. More...
struct  PATNODE
 Another patricia binary tree node, to search integer value from string. More...

Functions

int testbit (char *str, int bitplace)
 String bit test function.
int testbit_max (char *str, int bitplace, int maxbitplace)
 Local bit test function for search.
int where_the_bit_differ (char *str1, char *str2)
 Find in which bit the two strings differ, starting from the head.
PATNODE * make_ptree (char **words, int *data, int wordsnum, int bitplace)
 Make a patricia tree for given string arrays.
void disp_ptree (PATNODE *node, int level)
 Output a tree structure in text for debug, traversing pre-order.
int ptree_search_data (char *str, PATNODE *rootnode)
 Search for the data whose key string matches the given string.
PATNODE * ptree_make_root_node (int data)
 Make a root node of a index tree.
void ptree_add_entry (char *str, int data, char *matchstr, PATNODE **rootnode)
 Insert a new node to the index tree.
void free_ptree (PATNODE *rootnode)
 Free all the sub nodes from specified node.
void * aptree_search_data (char *str, APATNODE *rootnode)
 Search for the data whose key string matches the given string.
APATNODE * aptree_make_root_node (void *data)
 Make a root node of a index tree.
void aptree_add_entry (char *str, void *data, char *matchstr, APATNODE **rootnode)
 Insert a new node to the index tree.
void aptree_remove_entry (char *str, APATNODE **rootnode)
 Remove a node from the index tree.
void aptree_traverse_and_do (APATNODE *node, void(*callback)(void *))
 Recursive function to traverse index tree and execute the callback for all the existing data.
void free_aptree (APATNODE *rootnode)
 Free all the sub nodes from specified node.

Detailed Description

Patricia binary tree for data search.

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

Author:
Akinobu LEE
Date:
Fri Feb 11 17:27:24 2005
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 40 of file ptree.c.

Referenced by aptree_add_entry_at(), make_ptree(), ptree_add_entry_at(), and where_the_bit_differ().

int testbit_max ( char *  str,
int  bitplace,
int  maxbitplace 
)

Local bit test function for search.

Parameters:
str [in] key string
bitplace [in] bit place to test.
maxbitplace [in] maximum number of bitplace
Returns:
the content of tested bit in tmp_str, either 0 or 1.

Definition at line 58 of file ptree.c.

Referenced by aptree_remove_entry_r(), aptree_search_data_r(), and ptree_search_data_r().

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 73 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 116 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 179 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 231 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 252 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 310 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 329 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 76 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 97 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 155 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 224 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 243 of file aptree.c.

Referenced by aptree_traverse_and_do(), count_all_phone(), free_cdset(), list_error(), 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 263 of file aptree.c.

Referenced by free_aptree(), free_cdset(), and hmminfo_free().

Generated on Tue Dec 18 16:01:37 2007 for Julius by  doxygen 1.5.4