src/vfer_btree_delay.h File Reference

Header file for btree_delay.c. More...

#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <arpa/inet.h>

Go to the source code of this file.

Data Structures
struct	node
	A node in a btree maintaining min delay history. More...
struct	tree
	A btree maitaining min delay history in an AVL balancing algorithmic fashion. More...
Defines
#define	NODE_BALANCE(NODE)   (NODE_HEIGHT(NODE->right) - NODE_HEIGHT(NODE->left))
#define	NODE_HEIGHT(NODE)   (NODE == NULL ? 0 : NODE->height)
#define	NODE_RECOMPUTE_HEIGHT(NODE)
#define	VALUE_EXPIRED(tv_old, tv_new, tv_window)
Typedefs
typedef node	node_t
	A node in a btree maintaining min delay history.
typedef tree	tree_t
	A btree maitaining min delay history in an AVL balancing algorithmic fashion.
Functions
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)
void	Tree_Set_Window (tree_t *tree, struct timeval window)

---

Detailed Description

Header file for btree_delay.c.

Author:

Ivan Beschastnikh

Defines prototypes of functions implemented in tree_delay.c and the AVL tree and supporting data structures

• 04/30/06 ivan Created

Definition in file vfer_btree_delay.h.

---

Define Documentation

#define NODE_BALANCE

(

NODE

)

(NODE_HEIGHT(NODE->right) - NODE_HEIGHT(NODE->left))

Definition at line 87 of file vfer_btree_delay.h.

#define NODE_HEIGHT

(

NODE

)

(NODE == NULL ? 0 : NODE->height)

Definition at line 90 of file vfer_btree_delay.h.

#define NODE_RECOMPUTE_HEIGHT

(

NODE

)

Value:

{ \
        NODE->height = ((NODE_HEIGHT(NODE->left) > NODE_HEIGHT(NODE->right)) ? NODE_HEIGHT(NODE->left) : NODE_HEIGHT(NODE->right)) + 1; }

Definition at line 93 of file vfer_btree_delay.h.

#define VALUE_EXPIRED	(	tv_old,
		tv_new,
		tv_window		)

Value:

( \
  ((tv_old.tv_sec + tv_window.tv_sec) < tv_new.tv_sec) || \
  (((tv_old.tv_sec + tv_window.tv_sec) == tv_new.tv_sec) && \
    ((tv_old.tv_usec + tv_window.tv_usec) < tv_new.tv_usec)))

Definition at line 80 of file vfer_btree_delay.h.

---

Typedef Documentation

typedef struct node node_t

A node in a btree maintaining min delay history.

A node in a tree maintains a time stamp which determines how fresh the value is, an index for the tree->nodes array (see optimization above), left,right,parent pointers, and a height which is dynamically maintained

typedef struct tree tree_t

A btree maitaining min delay history in an AVL balancing algorithmic fashion.

a tree has a root pointer, a nodes array (see optimization above), a nodes_free counter and free_nodes array (also for optimization) and a window which determines the freshness of data values in the tree (ie. when to expire them)

---

Function Documentation

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.

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.

---