ptree.c

パトリシア検索木を用いた名前検索：データ型が int の場合 [詳細]

#include <sent/stddefs.h>
#include <sent/ptree.h>

ptree.cのインクルード依存関係図

ソースコードを見る。

関数
int	testbit (char *str, int bitplace)
int	where_the_bit_differ (char *str1, char *str2)
static PATNODE *	new_node ()
PATNODE *	make_ptree (char **words, int *data, int wordsnum, int bitplace)
void	disp_ptree (PATNODE *node, int level)
static int	testbit_local (int bitplace)
static int	ptree_search_data_r (PATNODE *node)
int	ptree_search_data (char *str, PATNODE *node)
PATNODE *	ptree_make_root_node (int data)
static void	ptree_add_entry_at (char *str, int bitloc, int data, PATNODE **parentlink)
void	ptree_add_entry (char *str, int data, char *matchstr, PATNODE **rootnode)
void	free_ptree (PATNODE *node)
変数
static char *	tmp_str
	Local work area: current string we are searching for.
static int	maxbitplace
	Local work area: Maximum bit length of tmp_str.

---

説明

パトリシア検索木を用いた名前検索：データ型が int の場合

作者:

Akinobu LEE

日付:

Thu Feb 17 15:34:39 2005

Revision

1.1.1.1

ptree.c で定義されています。

---

関数

int testbit (  char *  str, int  bitplace )

String bit test function. 引数: str  [in] key string bitplace  [in] bit location to test 戻り値: the content of tested bit in tmp_str, either 0 or 1. ptree.c の 36 行で定義されています。 参照元 aptree_add_entry_at(), make_ptree(), ptree_add_entry_at(), と 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. 引数: str1  [in] string 1 str2  [in] string 2 戻り値: the bit location in which the string differs. ptree.c の 61 行で定義されています。 参照元 aptree_add_entry(), と ptree_add_entry().

static PATNODE* new_node (   )  [static]

Allocate a new node. 戻り値: pointer to the new node. ptree.c の 82 行で定義されています。

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. 戻り値: pointer to the root node index. ptree.c の 105 行で定義されています。 参照元 make_ptree(), と 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 ptree.c の 168 行で定義されています。 参照元 disp_ptree().

static int testbit_local (  int  bitplace  )  [static]

Local bit test function for search. 引数: bitplace  [in] bit place to test. 戻り値: the content of tested bit in tmp_str, either 0 or 1. ptree.c の 200 行で定義されています。

static int ptree_search_data_r (  PATNODE *  node  )  [static]

Recursive function to search the data in the tree 引数: node  [in] current node. 戻り値: the found integer value. ptree.c の 224 行で定義されています。 参照元 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 戻り値: the exactly found integer value, or the nearest one. ptree.c の 246 行で定義されています。 参照元 ngram_lookup_word(), と set_unigram().

PATNODE* ptree_make_root_node (  int  data  )

Make a root node of a index tree. 引数: data  [in] the first data 戻り値: the newly allocated root node. ptree.c の 268 行で定義されています。 参照元 ptree_add_entry(), と 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 ptree.c の 286 行で定義されています。 参照元 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 ptree.c の 326 行で定義されています。 参照元 set_unigram().

void free_ptree (  PATNODE *  node  )

Free all the sub nodes from specified node. 引数: node  [in] current node. ptree.c の 345 行で定義されています。 参照元 free_ptree(), と ngram_info_free().

---