Julius: libsent/src/util/ptree.c File Reference

Go to the source code of this file.


Functions
int	testbit (char *str, int slen, 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.
static int	ptree_replace_data_r (PATNODE node, char str, int val, int maxbitplace)
	Recursive function to replace the data in the tree.
int	ptree_replace_data (char str, int val, PATNODE node)
	Search for the data whose key string matches the given string, and replace its value.
PATNODE *	ptree_make_root_node (int data)
	Make a root node of a index tree.
static void	ptree_add_entry_at (char str, int slen, 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}

Detailed Description

Function Documentation

int testbit	(	char *	str,
		int	slen,
		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(), ptree_replace_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().

static PATNODE* new_node ( ) [static]

Allocate a new node.

Returns:: pointer to the new node.

Definition at line 96 of file ptree.c.

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 119 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 182 of file ptree.c.

static int ptree_search_data_r	(	PATNODE *	node,
		char *	str,
		int	maxbitplace
	)			`[static]`

Recursive function to search the data in the tree.

Parameters:

	node	[in] current node.
	str	[in] key string
	maxbitplace	[in] maximum number of bitplace

Returns:: the found integer value.

Definition at line 212 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.

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 234 of file ptree.c.

Referenced by ngram_lookup_word(), and set_unigram().

static int ptree_replace_data_r	(	PATNODE *	node,
		char *	str,
		int	val,
		int	maxbitplace
	)			`[static]`

Recursive function to replace the data in the tree.

Parameters:

	node	[in] current node.
	str	[in] key string
	val	[in] new value
	maxbitplace	[in] maximum number of bitplace

Returns:: the found integer value.

Definition at line 254 of file ptree.c.

Referenced by ptree_replace_data().

int ptree_replace_data	(	char *	str,
		int	val,
		PATNODE *	node
	)

Search for the data whose key string matches the given string, and replace its value.

Parameters:

	str	[in] search key string
	val	[in] value
	node	[in] root node of index tree

Returns:: the exactly found integer value, or the nearest one.

Definition at line 279 of file ptree.c.

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 300 of file ptree.c.

Referenced by ptree_add_entry(), and set_unigram().

static void ptree_add_entry_at	(	char *	str,
		int	slen,
		int	bitloc,
		int	data,
		PATNODE **	parentlink
	)			`[static]`

Insert a new node to the existing index tree.

Parameters:

	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 318 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.

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 358 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 377 of file ptree.c.

Referenced by free_ptree(), and ngram_info_free().

libsent/src/util/ptree.c File Reference

Functions

Variables

Detailed Description

Function Documentation