#include <assert.h>
#include "spacedef.h"
#include "debug.h"
#include "decoderTree.h"
#include "alpha.h"
#include "arithmetic/coder.h"
#include "arithmetic/bitio.h"
#include <obstack.h>

Macros
#define	ROOT -1
	Flag to indicate a node is the root. More...

#define	obstack_chunk_alloc malloc

#define	obstack_chunk_free free

Functions
static void	fastCanonize (decoderTree_t tree, Uint xLeft, Uint xRight, decoderTree_t node, decoderTree_t r, Uint uLeft, Uint uRight, Uint vLeft, Uint *vRight)
	Calculates the canonical decomposition of a string in a faster way. More...

static void	canonize (decoderTree_t tree, Uint xLeft, Uint xRight, decoderTree_t node, decoderTree_t r, Uint uLeft, Uint uRight, Uint vLeft, Uint *vRight)
	Calculates the canonical decomposition of a string. More...

static decoderTree_t	insert (decoderTree_t r, decoderTree_t node, Uint uLeft, Uint uRight, Uint vLeft, Uint vRight, BOOL decoder)
	Inserts a new node in the FSM closure of the tree. More...

static void	verify (const decoderTree_t root, decoderTree_t node, BOOL fast, BOOL decoder)
	Verifies that the tail of node is in the tree, adding it if necessary and continuing recursively on the children of root. More...

void	verifyDecoder (const decoderTree_t root, decoderTree_t node)
	Verify*, only called by the decoder routine. More...

static void	propagateTransitions (decoderTree_t *transitions, decoderTree_t tree)
	Adds to the FSM a set of transitions originating from tree if thew were not defined by verify. More...

static BOOL	readEncoder (FILE *file)
	Reads a bit from the file using an arithmetic decoder. More...

static int	readDecoderTreeRec (decoderTree_t t, FILE *file)
	Reads a decoder tree from its encoded representation on a file. More...

void	initDecoderTreeStack ()

decoderTree_t	initDecoderTree (BOOL useMalloc)
	Creates and initializes a new decoder tree structure instance. More...

void	freeDecoderTree (decoderTree_t tree, BOOL deleteText)
	Deletes a decoder tree structure instance. More...

void	makeDecoderFsm (decoderTree_t tree)
	Calculates the FSM closure of this tree. More...

decoderTree_t	readDecoderTree (FILE *file)
	Creates a new decoder tree reading it from a file. More...

BOOL	isRootDecoderTree (decoderTree_t tree)
	Indicates if the parameter node is the root of the tree. More...

Variables
static Ushort	internalNodes
	Number of internal nodes in the tree. More...

static Uint	totalNodes
	Total number of nodes in the tree. More...

static struct obstack	nodeStack

Macro Definition Documentation

#define obstack_chunk_alloc malloc

Definition at line 33 of file decoderTree.c.

#define obstack_chunk_free free

Definition at line 34 of file decoderTree.c.

#define ROOT -1

Flag to indicate a node is the root.

Definition at line 31 of file decoderTree.c.

Function Documentation

static void canonize	(	decoderTree_t	tree,
		Uint	xLeft,
		Uint	xRight,
		decoderTree_t	node,
		decoderTree_t *	r,
		Uint *	uLeft,
		Uint *	uRight,
		Uint *	vLeft,
		Uint *	vRight
	)

static

Calculates the canonical decomposition of a string.

Parameters

[in]	tree	node from where to start the search.
[in]	xLeft	left index in the input data of the string to canonize.
[in]	xRight	right index in the input data of the string to canonize.
[in]	node	tree node with a pointer to the data string. Used by GETINDEX2.
[out]	r	node whose label is the longest prefix of the string in the tree.
[out]	uLeft	index of the leftmost character of the string u in the input data. ru is the longest prefix of the string which is a word of the tree.
[out]	uRight	index of the rightmost character of the string u in the input data. ru is the longest prefix of the string which is a word of the tree.
[out]	vLeft	index of the leftmost character of the remaining part of the string (after ru).
[out]	vRight	index of the rightmost character of the remaining part of the string (after ru).

Definition at line 109 of file decoderTree.c.

static void fastCanonize	(	decoderTree_t	tree,
		Uint	xLeft,
		Uint	xRight,
		decoderTree_t	node,
		decoderTree_t *	r,
		Uint *	uLeft,
		Uint *	uRight,
		Uint *	vLeft,
		Uint *	vRight
	)

static

Calculates the canonical decomposition of a string in a faster way.

It is only possible to use this variant in some special cases.

Parameters

[in]	tree	node from where to start the search.
[in]	xLeft	left index in the input data of the string to canonize.
[in]	xRight	right index in the input data of the string to canonize.
[in]	node	tree node with a pointer to the data string. Used by GETINDEX2.
[out]	r	node whose label is the longest prefix of the string in the tree.
[out]	uLeft	index of the leftmost character of the string v in the input data. ru is the longest prefix of the string which is a word of the tree.
[out]	uRight	index of the leftmost character of the string v in the input data. ru is the longest prefix of the string which is a word of the tree.
[out]	vLeft	index of the leftmost character of the remaining part of the string (after ru).
[out]	vRight	index of the rightmost character of the remaining part of the string (after ru).

Definition at line 60 of file decoderTree.c.

void freeDecoderTree	(	decoderTree_t	tree,
		BOOL	deleteText
	)

Deletes a decoder tree structure instance.

Parameters

[in,out]	tree	the tree to delete.
[in]	deleteText	if the string pointed by this node must be deleted

Definition at line 648 of file decoderTree.c.

decoderTree_t initDecoderTree ( BOOL useMalloc )

Creates and initializes a new decoder tree structure instance.

Returns: a new decoder tree instance.

Definition at line 597 of file decoderTree.c.

void initDecoderTreeStack ( )

Definition at line 584 of file decoderTree.c.

static decoderTree_t insert	(	decoderTree_t	r,
		decoderTree_t	node,
		Uint	uLeft,
		Uint	uRight,
		Uint	vLeft,
		Uint	vRight,
		BOOL	decoder
	)

static

Inserts a new node in the FSM closure of the tree.

Parameters

[in]	r	parent of the new node to be added.
[in]	node	tree node with a pointer to the data string. Used by GETINDEX2.
[in]	uLeft	index of the leftmost character of the u string.
[in]	uRight	index of the rightmost character of the u string.
[in]	vLeft	index of the leftmost character of the v string.
[in]	vRight	index of the rightmost character of the v string.
[in]	decoder	flag to indicate insert is called from the decoder routine

Returns: a pointer the new added node.

Definition at line 166 of file decoderTree.c.

BOOL isRootDecoderTree ( decoderTree_t tree )

Indicates if the parameter node is the root of the tree.

Parameters

[in] tree tree node.

Returns: True if the node is the root, False otherwise.

Definition at line 717 of file decoderTree.c.

void makeDecoderFsm ( decoderTree_t tree )

Calculates the FSM closure of this tree.

Parameters

[in] tree the tree to process.

Definition at line 665 of file decoderTree.c.

static void propagateTransitions	(	decoderTree_t *	transitions,
		decoderTree_t	tree
	)

static

Adds to the FSM a set of transitions originating from tree if thew were not defined by verify.

Parameters

[in]	transitions	set of transitions.
[in]	tree	origin node of the transitions.

Definition at line 427 of file decoderTree.c.

decoderTree_t readDecoderTree ( FILE * file )

Creates a new decoder tree reading it from a file.

Parameters

[in] file file to read the tree from.

Returns: a new decoder tree.

Definition at line 683 of file decoderTree.c.

static int readDecoderTreeRec	(	decoderTree_t	t,
		FILE *	file
	)

static

Reads a decoder tree from its encoded representation on a file.

Parameters

[in]	t	root of the tree.
[in]	file	input file pointer.

Definition at line 496 of file decoderTree.c.

static BOOL readEncoder ( FILE * file )

static

Reads a bit from the file using an arithmetic decoder.

Each bit indicates if a node of the tree is internal (True) or a leaf (False).

Parameters

[in] file input file pointer.

Returns: the readed bit.

Definition at line 448 of file decoderTree.c.

static void verify	(	const decoderTree_t	root,
		decoderTree_t	node,
		BOOL	fast,
		BOOL	decoder
	)

static

Verifies that the tail of node is in the tree, adding it if necessary and continuing recursively on the children of root.

Parameters

[in]	root	node to use as the start point in the search of canonize.
[in]	node	node to verify.
[in]	fast	flag to indicate that it is possible to use fastCanonize in this invocation of verify.
[in]	decoder	flag to indicate verify is called from the decoder routine

Definition at line 374 of file decoderTree.c.

void verifyDecoder	(	const decoderTree_t	root,
		decoderTree_t	node
	)

Verify*, only called by the decoder routine.

Definition at line 418 of file decoderTree.c.

Variable Documentation

Ushort internalNodes

static

Number of internal nodes in the tree.

Equals the number of ones in the natural code file.

Definition at line 37 of file decoderTree.c.

struct obstack nodeStack

static

Definition at line 43 of file decoderTree.c.

Uint totalNodes

static

Total number of nodes in the tree.

Definition at line 40 of file decoderTree.c.

Macros

Functions

Variables

Macro Definition Documentation

Function Documentation

Variable Documentation