Tree

AVL trees for opdis addresses and instructions. More...

Data Structures
struct	opdis_tree_node_t
	A node in an AVL tree. More...
struct	opdis_tree_base_t
	The base of the tree. More...
Typedefs
typedef void (	OPDIS_TREE_KEY_FN )(void *item)
	Callback to get the key for an item stored in a tree.
typedef int(*	OPDIS_TREE_CMP_FN )(void a, void b)
	Callback to compare two keys.
typedef void(*	OPDIS_TREE_FREE_FN )(void *item)
	Callback to free items stored in the tree.
typedef opdis_tree_base_t *	opdis_tree_t
	A generic AVL tree.
typedef opdis_tree_base_t *	opdis_vma_tree_t
	An AVL tree for storing opdis addresses.
typedef opdis_tree_base_t *	opdis_insn_tree_t
	An AVL tree for storing opdis instructions.
typedef int(*	OPDIS_TREE_FOREACH_FN )(void item, void arg)
	Callback invoked by opdis_tree_foreach.
typedef int(*	OPDIS_ADDR_TREE_FOREACH_FN )(opdis_vma_t addr, void *arg)
	Callback invoked for every address emitted by opdis_vma_tree_foreach.
typedef int(*	OPDIS_INSN_TREE_FOREACH_FN )(opdis_insn_t insn, void arg)
	Callback invoked for each insn emitted by opdis_insn_tree_foreach.
Functions
opdis_tree_t LIBCALL	opdis_tree_init (OPDIS_TREE_KEY_FN key_fn, OPDIS_TREE_CMP_FN cmp_fn, OPDIS_TREE_FREE_FN free_fn)
	Allocate and initialize for an AVL tree.
int LIBCALL	opdis_tree_add (opdis_tree_t tree, void *data)
	Insert a node into the tree.
int LIBCALL	opdis_tree_update (opdis_tree_t tree, void *data)
	Insert or overwrite a node in the tree.
int LIBCALL	opdis_tree_delete (opdis_tree_t tree, void *key)
	Remove an item from the tree.
int LIBCALL	opdis_tree_contains (opdis_tree_t tree, void *key)
	Determine if tree contains data.
void *LIBCALL	opdis_tree_find (opdis_tree_t tree, void *key)
	Find data in a tree.
void *	opdis_tree_closest (opdis_tree_t tree, void *key)
	Find closest match to data in a tree. This returns the item that matches the key, or the item that is closest to (but less than) the key, or NULL if there is no item less than or equal to the key.
void *	opdis_tree_next (opdis_tree_t tree, void *key)
	Find the data succeeding the key in a tree. This returns the item that occurs immediately after key in the tree, or immediately after where key would be if it were in the tree. If there are no items greater than key in the tree, this returns NULL.
void LIBCALL	opdis_tree_foreach (opdis_tree_t tree, OPDIS_TREE_FOREACH_FN fn, void *arg)
	Iterate over the tree, invoking a callback for each item.
size_t LIBCALL	opdis_tree_count (opdis_tree_t tree)
	Return the number of items in the tree.
void LIBCALL	opdis_tree_free (opdis_tree_t tree)
	Free an AVL tree.
opdis_vma_tree_t LIBCALL	opdis_vma_tree_init (void)
	Allocate an Address Tree.
int LIBCALL	opdis_vma_tree_add (opdis_vma_tree_t tree, opdis_vma_t addr)
	Insert an address into the tree.
int LIBCALL	opdis_vma_tree_delete (opdis_vma_tree_t tree, opdis_vma_t addr)
	Delete an address from the tree.
int LIBCALL	opdis_vma_tree_contains (opdis_vma_tree_t tree, opdis_vma_t addr)
	Determine if an address is in the tree.
opdis_vma_t LIBCALL	opdis_vma_tree_find (opdis_vma_tree_t tree, opdis_vma_t addr)
	Find an address in the tree.
void LIBCALL	opdis_vma_tree_foreach (opdis_vma_tree_t tree, OPDIS_ADDR_TREE_FOREACH_FN fn, void *arg)
	Invoke a callback for every item in the tree.
void LIBCALL	opdis_vma_tree_free (opdis_vma_tree_t tree)
	Free the address tree.
opdis_insn_tree_t LIBCALL	opdis_insn_tree_init (int manage)
	Allocate an Instruction Tree.
int LIBCALL	opdis_insn_tree_add (opdis_insn_tree_t tree, opdis_insn_t *insn)
	Insert an instruction into the tree.
int LIBCALL	opdis_insn_tree_delete (opdis_insn_tree_t tree, opdis_vma_t addr)
	Delete an instruction from the tree.
int LIBCALL	opdis_insn_tree_contains (opdis_insn_tree_t tree, opdis_vma_t addr)
	Determine if an instruction is in the tree.
opdis_insn_t *LIBCALL	opdis_insn_tree_find (opdis_insn_tree_t tree, opdis_vma_t addr)
	Find an instruction in the tree.
void LIBCALL	opdis_insn_tree_foreach (opdis_insn_tree_t tree, OPDIS_INSN_TREE_FOREACH_FN fn, void *arg)
	Invoke a callback for every item in the tree.
void LIBCALL	opdis_insn_tree_free (opdis_insn_tree_t tree)
	Free the instruction tree.

Detailed Description

AVL trees for opdis addresses and instructions.

Typedef Documentation

int(* OPDIS_ADDR_TREE_FOREACH_FN)(opdis_vma_t, void *)

Callback invoked for every address emitted by opdis_vma_tree_foreach.

Parameters:

	addr	The address.
	arg	Argument provided to opdis_vma_tree_foreach

Note:: A zero return value will break out of the foreach.

int(* OPDIS_INSN_TREE_FOREACH_FN)(opdis_insn_t *, void *)

Callback invoked for each insn emitted by opdis_insn_tree_foreach.

Parameters:

	addr	The instruction.
	arg	Argument provided to opdis_insn_tree_foreach

Note:: A zero return value will break out of the foreach.

int(* OPDIS_TREE_CMP_FN)(void *, void *)

Callback to compare two keys.

Parameters:

	a	The first key.
	b	The second key.

Returns:: -1, 0, 1 if a is <, ==, or > b

This function is called to determine if the first item is before, after, or equal in order to the second item.

int(* OPDIS_TREE_FOREACH_FN)(void *, void *)

Callback invoked by opdis_tree_foreach.

Parameters:

	item	The current item.
	arg	The argument provided to opdis_tree_foreach.

Note:: A zero return value will break out of the foreach.

void(* OPDIS_TREE_FREE_FN)(void *)

Callback to free items stored in the tree.

Parameters:

item

The item to free.

void *(* OPDIS_TREE_KEY_FN)(void *)

Callback to get the key for an item stored in a tree.

Parameters:

item

The item in the tree.

Returns:: Key for item

This function is invoked in order to retrieve the key for an item stored in the tree.

Function Documentation

int opdis_insn_tree_add	(	opdis_insn_tree_t	tree,
		opdis_insn_t *	insn
	)

Insert an instruction into the tree.

Parameters:

	tree	The Instruction Tree.
	insn	The instruction to insert.

Returns:: 1 if instruction was added, 0 if instruction exists.

See also:: opdis_insn_tree_delete

int opdis_insn_tree_contains	(	opdis_insn_tree_t	tree,
		opdis_vma_t	addr
	)

Determine if an instruction is in the tree.

Parameters:

	tree	The Instruction Tree.
	addr	The address to search for.

Returns:: 1 if the address is in the tree, 0 otherwise.

See also:: opdis_tree_contains

int opdis_insn_tree_delete	(	opdis_insn_tree_t	tree,
		opdis_vma_t	addr
	)

Delete an instruction from the tree.

Parameters:

	tree	The Instruction Tree.
	insn	The instruction to delete.

Returns:: 1 on success, 0 on failure.

See also:: opdis_insn_tree_add

Note:: The instruction is freed if the Instruction Tree was created with manage set to 1.

opdis_insn_t * opdis_insn_tree_find	(	opdis_insn_tree_t	tree,
		opdis_vma_t	addr
	)

Find an instruction in the tree.

Parameters:

	tree	The Instruction Tree.
	addr	The address of the instruction.

Returns:: The instruction or NULL.

See also:: opdis_tree_find

void opdis_insn_tree_foreach	(	opdis_insn_tree_t	tree,
		OPDIS_INSN_TREE_FOREACH_FN	fn,
		void *	arg
	)

Invoke a callback for every item in the tree.

Parameters:

	tree	The Instruction Tree.
	fn	The callback to invoke for each instruction.
	arg	An optional argument to pass to the callback function.

void opdis_insn_tree_free ( opdis_insn_tree_t tree )

Free the instruction tree.

Parameters:

tree

The instruction Tree.

See also:: opdis_insn_tree_init

Note:: The instructions in the tree are freed if the Instruction Tree was created with manage set to 1.

opdis_tree_t opdis_insn_tree_init ( int manage )

Allocate an Instruction Tree.

Parameters:

manage

1 if tree should free items on deletion; 0 otherwise.

Returns:: The allocated tree.

See also:: opdis_insn_tree_free

This creates a balanced binary tree of instructions keyed by VMA (NOT offset).

int opdis_tree_add	(	opdis_tree_t	tree,
		void *	data
	)

Insert a node into the tree.

Parameters:

	tree	The AVL tree.
	data	The data to insert.

Returns:: 1 on if the node was inserted, 0 on if node exists.

See also:: opdis_tree_update opdis_tree_delete

Note:: If the data already exists in the tree (i.e. the key compare callback returns 0), then the tree is unchanged and this routine returns zero. Use opdis_tree_update to overwrite an existing node.

void * opdis_tree_closest	(	opdis_tree_t	tree,
		void *	key
	)

Find closest match to data in a tree. This returns the item that matches the key, or the item that is closest to (but less than) the key, or NULL if there is no item less than or equal to the key.

Parameters:

	tree	The AVL tree.
	key	The key of the item to match.

Returns:: The item that is the closest match, or NULL.

int opdis_tree_contains	(	opdis_tree_t	tree,
		void *	key
	)

Determine if tree contains data.

Parameters:

	tree	The AVL tree.
	key	The key of the item to search for.

Returns:: 1 if the item is stored, 0 otherwise.

See also:: opdis_tree_find

This function returns true (1) if tree contains a node with the given key. This is used instead of opdis_tree_find in trees where the node data (e.g. integers or pointers) could be zero, as the opdis_tree_find return value of NULL for not found will be zero regardless of whether the data is in the tree.

size_t opdis_tree_count ( opdis_tree_t tree )

Return the number of items in the tree.

Parameters:

tree

The AVL tree.

Returns:: The number of nodes in the tree.

int opdis_tree_delete	(	opdis_tree_t	tree,
		void *	key
	)

Remove an item from the tree.

Parameters:

	tree	The AVL tree.
	key	The key of the item to remove.

Returns:: 1 on success, 0 on failure.

See also:: opdis_tree_add

This routine removes the item from the tree and invokes the OPDIS_TREE_FREE_FN to free it.

void * opdis_tree_find	(	opdis_tree_t	tree,
		void *	key
	)

Find data in a tree.

Parameters:

	tree	The AVL tree.
	key	The key of the item to return.

Returns:: The item stored in the tree or NULL.

See also:: opdis_tree_contains

void opdis_tree_foreach	(	opdis_tree_t	tree,
		OPDIS_TREE_FOREACH_FN	fn,
		void *	arg
	)

Iterate over the tree, invoking a callback for each item.

Parameters:

	tree	The AVL tree.
	fn	The callback function to invoke.
	arg	An optional argument to pass to the callback.

void opdis_tree_free ( opdis_tree_t tree )

Free an AVL tree.

Parameters:

tree

The AVL tree to free.

See also:: opdis_tree_init

Note:: This routine invokes opdis_tree_delete on every node in the tree, then frees the tree itself. When this returns, tree points to an invalid object.

opdis_tree_t opdis_tree_init	(	OPDIS_TREE_KEY_FN	key_fn,
		OPDIS_TREE_CMP_FN	cmp_fn,
		OPDIS_TREE_FREE_FN	free_fn
	)

Allocate and initialize for an AVL tree.

Parameters:

	key_fn	Callback to use for key retrieval.
	cmp_fn	Callback to use for key comparison.
	free_fn	Callback to use to free items or NULL.

Returns:: The allocated binary tree.

See also:: opdis_tree_free

Note:: If free_fn is NULL, then items stored in the tree will not be freed when deleted or when the tree is destroyed.

void * opdis_tree_next	(	opdis_tree_t	tree,
		void *	key
	)

Find the data succeeding the key in a tree. This returns the item that occurs immediately after key in the tree, or immediately after where key would be if it were in the tree. If there are no items greater than key in the tree, this returns NULL.

Parameters:

	tree	The AVL tree.
	key	The key of the item to match.

Returns:: The item that is next, or NULL.

int opdis_tree_update	(	opdis_tree_t	tree,
		void *	data
	)

Insert or overwrite a node in the tree.

Parameters:

	tree	The AVL tree.
	data	The data to insert.

Returns:: 1 on success, 0 on failure.

See also:: opdis_tree_add opdis_tree_delete

This routine will insert a node into the tree. If the data already exists in the tree (i.e. the key compare callback returns 0), then the data in the tree is freed and replaced.

int opdis_vma_tree_add	(	opdis_vma_tree_t	tree,
		opdis_vma_t	addr
	)

Insert an address into the tree.

Parameters:

	tree	The Address Tree.
	addr	The address to insert.

Returns:: 1 if address was added, 0 if address exists.

See also:: opdis_vma_tree_delete

int opdis_vma_tree_contains	(	opdis_vma_tree_t	tree,
		opdis_vma_t	addr
	)

Determine if an address is in the tree.

Parameters:

	tree	The Address Tree.
	addr	The address to search for.

Returns:: 1 if the address is in the tree, 0 otherwise.

See also:: opdis_tree_contains

int opdis_vma_tree_delete	(	opdis_vma_tree_t	tree,
		opdis_vma_t	addr
	)

Delete an address from the tree.

Parameters:

	tree	The Address Tree.
	addr	The address to delete.

Returns:: 1 on success, 0 on failure.

See also:: opdis_vma_tree_add

opdis_vma_t opdis_vma_tree_find	(	opdis_vma_tree_t	tree,
		opdis_vma_t	addr
	)

Find an address in the tree.

Parameters:

	tree	The Address Tree.
	addr	The address to search for.

Returns:: The address or OPDIS_INVALID_ADDR.

See also:: opdis_tree_find

void opdis_vma_tree_foreach	(	opdis_vma_tree_t	tree,
		OPDIS_ADDR_TREE_FOREACH_FN	fn,
		void *	arg
	)

Invoke a callback for every item in the tree.

Parameters:

	tree	The Address Tree.
	fn	The callback to invoke for each address.
	arg	An optional argument to pass to the callback function.

void opdis_vma_tree_free ( opdis_vma_tree_t tree )

Free the address tree.

Parameters:

tree

The Address Tree.

See also:: opdis_vma_tree_init

opdis_vma_tree_t opdis_vma_tree_init ( void )

Allocate an Address Tree.

Returns:: The allocated tree.

See also:: opdis_vma_tree_free

This creates a balanced binary tree of addresses. In this tree, the key is the same as the data: its primary use is to keep track of addresses which have been visited.

Tree

Data Structures

Typedefs

Functions

Detailed Description

Typedef Documentation

Function Documentation