lib/include/tree.h File Reference

A small tree library for the sensor node. More...

#include <inttypes.h>

Go to the source code of this file.

Data Structures
struct	node_t
Typedefs
typedef tree_node *	node_ptr
Enumerations
enum
Functions
void	print_tree (node_ptr starting_point)
	Print out the current tree in ASCII.
void	clear_tree ()
	Delete all nodes in the tree.
node_ptr	get_root ()
	Return a pointer to the root of the tree.
uint8_t	insert (uint16_t key)
	insert a new node into the tree.
node_ptr	find (uint16_t key)
	Locate a particular value and return a pointer to that node.
node_ptr	find_node (uint16_t key)
	Same as find.
uint8_t	delete (uint16_t key)
	Delete a particular node from the tree.
uint8_t	left_rotate_node (uint16_t key)
	preform a left rotation on the node given by key
uint8_t	right_rotate_node (uint16_t key)
	preform a right rotation on the node given by key
uint8_t	left_rotate (node_ptr x)
	preform a left rotation on the node pointed to by x
uint8_t	right_rotate (node_ptr x)
	preform a right rotation on the node pointed to by x
void	splay (node_ptr x)
	Splay the node pointed to by x.
void	splay_node (uint16_t key)
	Search for a node and splay it.
node_ptr	get_min ()
	get a pointer to the node with the lowest value
node_ptr	get_max ()
	get a pointer to the node with the highest value
uint16_t	count_nodes (node_ptr starting_point)
	count the number of nodes in the tree
uint16_t	get_total (node_ptr starting_point)
	Total up all of the keys in the tree.

---

Detailed Description

Note: These routines may blow the stack or cause fragmentation in memory, use at your own risk.

Definition in file tree.h.

---

Function Documentation

uint16_t count_nodes (  node_ptr  starting_point  )

Parameters: starting_point  Root of subtree to count nodes of. Returns: Number of nodes in specified subtree.

uint8_t delete (  uint16_t  key  )

Parameters: key  Node to delete from tree. Returns: TREE_NODE_NOT_FOUND If the particular node wasn't found TREE_OK if node was found and properly removed.

node_ptr find (  uint16_t  key  )

Parameters: key  Value to search for. Returns: node_ptr Pointer to node if found, NULL if not

uint16_t get_total (  node_ptr  starting_point  )

Note: the return value is only 16 bits and will most likely overflow on a decent sized tree.

uint8_t insert (  uint16_t  key  )

Parameters: key  Value to insert into the tree Returns: TREE_NODE_EXISTS if that key is already in the tree TREE_OUT_OF_MEM if there is no more memory left TREE_OK if the insertion was successful

uint8_t left_rotate (  node_ptr  x  )

Parameters: x  pointer to node to preform rotation on. Returns: TREE_NODE_NOT_FOUND If the particular key wasn't found. TREE_INVALID_ROTATION If the rotation isn't possible. TREE_OK If the rotation was successful.

uint8_t left_rotate_node (  uint16_t  key  )

Parameters: key  Node to search for and rotate Returns: TREE_NODE_NOT_FOUND If the particular key wasn't found. TREE_INVALID_ROTATION If the rotation isn't possible. TREE_OK If the rotation was successful.

uint8_t right_rotate (  node_ptr  x  )

Parameters: x  pointer to node to preform rotation on. Returns: TREE_NODE_NOT_FOUND If the particular key wasn't found. TREE_INVALID_ROTATION If the rotation isn't possible. TREE_OK If the rotation was successful.

uint8_t right_rotate_node (  uint16_t  key  )

Parameters: key  Node to search for and rotate Returns: TREE_NODE_NOT_FOUND If the particular key wasn't found. TREE_INVALID_ROTATION If the rotation isn't possible. TREE_OK If the rotation was successful.

void splay (  node_ptr  x  )

Parameters: x  Pointer to node to be splayed.

void splay_node (  uint16_t  key  )

Parameters: key  Node to search for and splay.

---