#include <sent/stddefs.h>
#include <sent/ptree.h>
Go to the source code of this file.
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. | |
static PATNODE * | new_node () |
Allocate a new node. | |
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. | |
static int | ptree_search_data_r (PATNODE *node, char *str, int maxbitplace) |
Recursive function to search the data in the tree. | |
int | ptree_search_data (char *str, PATNODE *node) |
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. | |
static void | ptree_add_entry_at (char *str, int bitloc, int data, PATNODE **parentlink) |
Insert a new node to the existing 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 *node) |
Free all the sub nodes from specified node. | |
Variables | |
static unsigned char | mbit [] = {0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01} |
Definition in file ptree.c.
int testbit | ( | char * | str, | |
int | bitplace | |||
) |
String bit test function.
str | [in] key string | |
bitplace | [in] bit location to test |
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.
str | [in] key string | |
bitplace | [in] bit place to test. | |
maxbitplace | [in] maximum number of bitplace |
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.
str1 | [in] string 1 | |
str2 | [in] string 2 |
Definition at line 73 of file ptree.c.
Referenced by aptree_add_entry(), and ptree_add_entry().
static PATNODE* new_node | ( | ) | [static] |
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.
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. |
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.
node | [in] root index node | |
level | [in] current tree depth |
Definition at line 179 of file ptree.c.
Referenced by disp_ptree().
static int ptree_search_data_r | ( | PATNODE * | node, | |
char * | str, | |||
int | maxbitplace | |||
) | [static] |
Recursive function to search the data in the tree.
node | [in] current node. | |
str | [in] key string | |
maxbitplace | [in] maximum number of bitplace |
Definition at line 209 of file ptree.c.
Referenced by ptree_search_data().
int ptree_search_data | ( | char * | str, | |
PATNODE * | node | |||
) |
Search for the data whose key string matches the given string.
str | [in] search key string | |
node | [in] root node of index tree |
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.
data | [in] the first data |
Definition at line 252 of file ptree.c.
Referenced by ptree_add_entry(), and set_unigram().
static void ptree_add_entry_at | ( | char * | str, | |
int | bitloc, | |||
int | data, | |||
PATNODE ** | parentlink | |||
) | [static] |
Insert a new node to the existing index tree.
str | [in] new key string | |
bitloc | [in] bit branch to which this node will be added | |
data | [in] new data integer value | |
parentlink | [i/o] the parent node to which this node will be added |
Definition at line 270 of file ptree.c.
Referenced by ptree_add_entry().
void ptree_add_entry | ( | char * | str, | |
int | data, | |||
char * | matchstr, | |||
PATNODE ** | rootnode | |||
) |
Insert a new node to the index tree.
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.
node | [in] current node. |
Definition at line 329 of file ptree.c.
Referenced by free_ptree(), and ngram_info_free().