src/vfer_btree_delay.h

Go to the documentation of this file.

/*
 * Copyright 2005, 2006, Internet2
 * Legal conditions are in file LICENSE
 * (MD5 = c434f2e53b8089d8b4d0172c7ce07360).
 */
/**
 * @file   vfer_btree_delay.h
 * @author Ivan Beschastnikh
 * @brief  Header file for btree_delay.c
 *
 * Defines prototypes of functions implemented in tree_delay.c and the
 * AVL tree and supporting data structures
 *
 * -     04/30/06        ivan            Created
 */

#ifndef VFER_BTREE_DELAY_H
#define VFER_BTREE_DELAY_H

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

/* this is the number of nodes that are statically allocated as a optimization */
// #define MAX_NODES 8192

/**
 * @brief 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 node {
        int32_t val;            /* delay value */
        struct timeval stamp;   /* timestamp of the last delay of this value */
        /* int index;   */      /* index of this node in the nodes array */
        struct node* left;      /* left child node */
        struct node* right;     /* right child node */
        struct node* parent;    /* parent node of this node */
        int height;             /* height of this node's subtree */
} node_t;

/**
 * @brief 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) */
typedef struct tree{
        node_t* root;           /* root node */
        node_t last_val;        /* last value added to the tree (in case all tree values expire) and the tree becomes empty */
        /* node_t nodes[MAX_NODES]; */ /* statically allocated node array */
        /* int nodes_free;*/            /* total number of nodes that are
                                         * available (not in the tree) */       
        /* int free_nodes[MAX_NODES];*/ /* array of indexes (into nodes
                                         * array) of nodes that are not in
                                         * the tree the first nodes_free
                                         * are >= 0; the reset are set to
                                         * -1 */
        struct timeval window;  /* history window = the time value to
                                 * maintain as the current window for
                                 * delay measurements */
} tree_t;

/* function prototypes */
void    Tree_Init       (tree_t* tree, struct timeval window);
void    Tree_Set_Window (tree_t* tree, struct timeval window);
void    Tree_Insert     (tree_t* tree, int32_t val, struct timeval stamp);
int32_t Tree_Min        (tree_t* tree, struct timeval stamp);
int32_t Tree_Max(tree_t* tree, struct timeval stamp);
void    Tree_Print      (tree_t* tree);

/* useful macros */

/* evaluates to false if tv_old + tv_window < tv_new, ow. evaluates to true */
#define VALUE_EXPIRED(tv_old, tv_new, tv_window) ( \
  ((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)))

/* tree_balance = height(right_subtree) - height(left_subtree) -1,0,1
   is balanced ; anything else is unbalanced */
#define NODE_BALANCE(NODE) (NODE_HEIGHT(NODE->right) - NODE_HEIGHT(NODE->left))

/* evaluates to the height of the node, maps null node to height of 0 */
#define NODE_HEIGHT(NODE) (NODE == NULL ? 0 : NODE->height)

/* recomputes the height for a node based on the height of the left and right subtrees */
#define NODE_RECOMPUTE_HEIGHT(NODE) { \
        NODE->height = ((NODE_HEIGHT(NODE->left) > NODE_HEIGHT(NODE->right)) ? NODE_HEIGHT(NODE->left) : NODE_HEIGHT(NODE->right)) + 1; }


#endif /* VFER_BTREE_DELAY_H */

---