src/vfer_btree_delay.c File Reference

Implements the AVL tree delay history data structure. More...

#include "vfer_btree_delay.h"
#include "vfer.h"

Go to the source code of this file.

Functions
static node_t *	Tree_Acquire_Node (tree_t *tree)
static void	Tree_Balance (tree_t *tree, node_t *node)
static void	Tree_Delete (tree_t *tree, node_t *node)
void	Tree_Init (tree_t *tree, struct timeval window)
void	Tree_Insert (tree_t *tree, int32_t val, struct timeval stamp)
int32_t	Tree_Max (tree_t *tree, struct timeval stamp)
int32_t	Tree_Min (tree_t *tree, struct timeval stamp)
void	Tree_Print (tree_t *tree)
static void	Tree_Print_Helper (node_t *node)
static void	Tree_Release_Node (tree_t *tree, node_t *node)
static void	Tree_RotateL (tree_t *tree, node_t *node)
static void	Tree_RotateR (tree_t *tree, node_t *node)
void	Tree_Set_Window (tree_t *tree, struct timeval window)

---

Detailed Description

Implements the AVL tree delay history data structure.

Author:

Ivan Beschastnikh

Implements the AVL tree to maintain delay history

• 04/30/06 ivan Created

Definition in file vfer_btree_delay.c.

---

Function Documentation

static node_t * Tree_Acquire_Node

(

tree_t *

tree

)

[inline, static]

Acquires a preallocated node

Parameters:

tree

binary delay tree structure pointer

Returns:

NULL if no more nodes available otherwise returns a pointer to a preallocated node

Definition at line 53 of file vfer_btree_delay.c.

static void Tree_Balance	(	tree_t *	tree,
		node_t *	node
	)			[inline, static]

Walks up from the node in question and rotate right/left the subtrees until we reach root if any of them need balancing

Parameters:

	tree	binary delay tree structure pointer
	node	pointer to a delay node in the tree structure

Definition at line 194 of file vfer_btree_delay.c.

static void Tree_Delete	(	tree_t *	tree,
		node_t *	node
	)			[inline, static]

Rotates the node to be deleted down into a leaf node, then prunes it off directly

Parameters:

	tree	binary delay tree structure pointer
	node	pointer to a delay node in the tree structure

Definition at line 160 of file vfer_btree_delay.c.

void Tree_Init	(	tree_t *	tree,
		struct timeval	window
	)

Initializes the tree with a specific delay window size

Parameters:

	tree	binary delay tree structure pointer
	window	window size to initiailize the tree with

Definition at line 230 of file vfer_btree_delay.c.

void Tree_Insert	(	tree_t *	tree,
		int32_t	val,
		struct timeval	stamp
	)

Inserts a new delay value into the tree. Prunes any values that are outside of the delay history while doing so. Updates the last_val added to tree to the inserted value and timestamp.

Parameters:

	tree	binary delay tree structure pointer
	val	delay value to insert
	stamp	timestamp of when the delay value was taken

Definition at line 268 of file vfer_btree_delay.c.

int32_t Tree_Max	(	tree_t *	tree,
		struct timeval	stamp
	)

Retrieves the maximum delay from the tree. Returns the last value added to the tree if the tree is empty (all values were expired).

Parameters:

	tree	binary delay tree structure pointer
	stamp	current timestamp with which to possibly prune values in the tree

Definition at line 413 of file vfer_btree_delay.c.

int32_t Tree_Min	(	tree_t *	tree,
		struct timeval	stamp
	)

Retrieves the minimum delay from the tree. Returns the last value added to the tree if the tree is empty (all values were expired).

Parameters:

	tree	binary delay tree structure pointer
	stamp	current timestamp with which to possibly prune values in the tree

Definition at line 377 of file vfer_btree_delay.c.

void Tree_Print

(

tree_t *

tree

)

Prints the tree by using the print helper function for recursion

Parameters:

tree

binary delay tree structure pointer

Definition at line 447 of file vfer_btree_delay.c.

static void Tree_Print_Helper

(

node_t *

node

)

[static]

Recursively prints the node, and the left, and right subtrees of the node

Parameters:

node

pointer to a delay node in the tree structure

Definition at line 33 of file vfer_btree_delay.c.

static void Tree_Release_Node	(	tree_t *	tree,
		node_t *	node
	)			[inline, static]

Releases a preallocated node

Parameters:

	tree	binary delay tree structure pointer
	node	pointer to a delay node in the tree structure

Definition at line 76 of file vfer_btree_delay.c.

static void Tree_RotateL	(	tree_t *	tree,
		node_t *	node
	)			[inline, static]

Performs a left rotation on the tree at node node

Parameters:

	tree	binary delay tree structure pointer
	node	pointer to a delay node in the tree structure

Definition at line 123 of file vfer_btree_delay.c.

static void Tree_RotateR	(	tree_t *	tree,
		node_t *	node
	)			[inline, static]

Performs a right rotation on the tree at node node

Parameters:

	tree	binary delay tree structure pointer
	node	pointer to a delay node in the tree structure

Definition at line 88 of file vfer_btree_delay.c.

void Tree_Set_Window	(	tree_t *	tree,
		struct timeval	window
	)

Sets a new delay window to use for the tree

Parameters:

	tree	binary delay tree structure pointer
	window	new delay window

Definition at line 255 of file vfer_btree_delay.c.

---