src/vfer_btree_delay.c

Go to the documentation of this file.

/*
 * Copyright 2005, 2006, Internet2
 * Legal conditions are in file LICENSE
 * (MD5 = c434f2e53b8089d8b4d0172c7ce07360).
 */
/**
 * @file   vfer_btree_delay.c
 * @author Ivan Beschastnikh
 * @brief  Implements the AVL tree delay history data structure
 *
 * Implements the AVL tree to maintain delay history
 *
 * -     04/30/06        ivan            Created
 */

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

/* static functions prototype */
        static void     Tree_Print_Helper       (node_t* node);
inline  static node_t*  Tree_Acquire_Node       (tree_t* tree);
inline  static void     Tree_Release_Node       (tree_t* tree, node_t* node);
inline  static void     Tree_RotateR            (tree_t* tree, node_t* node);
inline  static void     Tree_RotateL            (tree_t* tree, node_t* node);
inline  static void     Tree_Delete             (tree_t* tree, node_t* node);
inline  static void     Tree_Balance            (tree_t* tree, node_t* node);
        
/**
 * Recursively prints the node, and the left, and right subtrees of the node
 *
 * @param node pointer to a delay node in the tree structure
 */
static void Tree_Print_Helper(node_t* node) {
        printf("[%d](", node->val);
        if (node->left != NULL) {
                Tree_Print_Helper(node->left);
        }
        printf(")(");
        if (node->right != NULL) {
                Tree_Print_Helper(node->right);
        }
        printf(")");
        return;
}

/**
 * Acquires a preallocated node
 *
 * @param tree binary delay tree structure pointer 
 * @return NULL if no more nodes available
 *         otherwise returns a pointer to a preallocated node
 */
inline static node_t* Tree_Acquire_Node(tree_t* tree) {
        node_t* ret;
        /* if (tree->nodes_free == 0) return NULL;
           ret = &(tree->nodes[tree->free_nodes[0]]); 
           tree->free_nodes[0] = tree->free_nodes[tree->nodes_free - 1];
           tree->nodes_free--; */
        
        ALLOC(ret, node_t*, node_t, 1);
        if (ret == NULL) {
                ERROR_PRINT("btree_delay.c", "Tree_Acquire_Node", "ERROR: Failed to alloc a btree node");
                return NULL;
        }
        ret->parent = ret->right = ret->left = NULL;
        ret->height = 1;
        return ret;
}

/**
 * Releases a preallocated node
 *
 * @param tree binary delay tree structure pointer
 * @param node pointer to a delay node in the tree structure
 */
inline static void Tree_Release_Node(tree_t* tree, node_t* node) {
        /* tree->free_nodes[tree->nodes_free] = node->index;
           tree->nodes_free++; */
        RELEASE(node, 1);
}

/**
 * Performs a right rotation on the tree at node node
 *
 * @param tree binary delay tree structure pointer
 * @param node pointer to a delay node in the tree structure
 */
inline static void Tree_RotateR(tree_t* tree, node_t* node) {
        node_t* left_child;
        
        left_child                      = node->left;
        left_child->parent              = node->parent;
        node->left                      = left_child->right;
        if (left_child->right != NULL) {
                left_child->right->parent = node;
        }
        left_child->right               = node;
        node->parent                    = left_child;

        if (left_child->parent == NULL) {
                tree->root = left_child;
        } else {
                if (left_child->parent->right == node) {
                        left_child->parent->right = left_child;
                } else {
                        left_child->parent->left = left_child;
                }
        }
        NODE_RECOMPUTE_HEIGHT(node);
        NODE_RECOMPUTE_HEIGHT(left_child);

//      printf("rotater: \n");
//      Tree_Print(tree);
        return;
} /* Tree_RotateR() */

/**
 * Performs a left rotation on the tree at node node
 *
 * @param tree binary delay tree structure pointer
 * @param node pointer to a delay node in the tree structure
 */
inline static void Tree_RotateL(tree_t* tree, node_t* node) {
        node_t* right_child;

        right_child                     = node->right;
        right_child->parent             = node->parent;
        node->right                     = right_child->left;
        if (right_child->left != NULL) {
                right_child->left->parent = node;
        }
        right_child->left               = node;
        node->parent                    = right_child;

        if (right_child->parent == NULL) {
                tree->root = right_child;
        } else {
                if (right_child->parent->right == node) {
                        right_child->parent->right = right_child;
                } else {
                        right_child->parent->left = right_child;
                }
        }

        NODE_RECOMPUTE_HEIGHT(node);
        NODE_RECOMPUTE_HEIGHT(right_child);

//      printf("rotatel: \n");
//      Tree_Print(tree);
        return;
} /* Tree_RotateL() */

/**
 * Rotates the node to be deleted down into a leaf node, then
 * prunes it off directly
 *
 * @param tree binary delay tree structure pointer
 * @param node pointer to a delay node in the tree structure
 */
inline static void Tree_Delete(tree_t* tree, node_t* node) {
        /* loop until node is a leaf by rotating the tree at the node
           so as to make the node travel always end up lower */
        while (node->left != NULL || node->right != NULL) {
                if (node->left == NULL) {
                        Tree_RotateL(tree, node);
                } else {
                        Tree_RotateR(tree, node);
                }
        }

        /* now we have to sever the link from the parent node to this
           node and make sure to handle all the corner cases */
        if (node->parent == NULL) {
                tree->root = NULL;
        } else {
                if (node->parent->left == node) {
                        node->parent->left = NULL;
                } else {
                        node->parent->right = NULL;
                }
        }
        Tree_Release_Node(tree, node);
//      printf("delete: \n");
//      Tree_Print(tree);
} /* Tree_Delete() */

/**
 * Walks up from the node in question and rotate right/left the subtrees
 * until we reach root if any of them need balancing
 *
 * @param tree binary delay tree structure pointer
 * @param node pointer to a delay node in the tree structure
 */
inline static void Tree_Balance(tree_t* tree, node_t* node) {
        node_t* parent;

        while (node != NULL) {
                parent = node->parent;

                if (node->left != NULL &&
                    node->height == node->left->height) {
                        node->height++;
                }
                if (node->right != NULL &&
                    node->height == node->right->height) {
                        node->height++;
                }
                
//              /* printf("balancing node[%d] height[%d] balance[%d]\n", node->val, node->height, NODE_BALANCE(node)); */
//              
                if (NODE_BALANCE(node) < -1) {
                        Tree_RotateR(tree, node);
                } else if (NODE_BALANCE(node) > 1) {
                        Tree_RotateL(tree, node);
                }
                node = parent;
        }
//      printf("balance: \n");
//      Tree_Print(tree);
        return;
} /* Tree_Balance() */


/**
 * Initializes the tree with a specific delay window size
 *
 * @param tree binary delay tree structure pointer
 * @param window window size to initiailize the tree with
 */
void Tree_Init(tree_t* tree, struct timeval window) {
        /* int i;
        node_t* nodes;
        nodes = tree->nodes;
        for (i = 0; i < MAX_NODES; i++) {
                nodes[i].index = i;
                nodes[i].height = 1;
                nodes[i].parent = nodes[i].right = nodes[i].left = NULL;
                tree->free_nodes[i] = i;
                } */
        tree->root = NULL;
        /* tree->nodes_free = MAX_NODES; */
        tree->window = window;
        tree->last_val.val = 0;
        tree->last_val.stamp.tv_sec = 0;
        tree->last_val.stamp.tv_usec = 0;
        
} /* Tree_Init() */

/**
 * Sets a new delay window to use for the tree
 *
 * @param tree binary delay tree structure pointer
 * @param window new delay window
 */
void Tree_Set_Window(tree_t* tree, struct timeval window) {
        tree->window = window;
} /* Tree_Set_Window() */

/**
 * 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.
 *
 * @param tree binary delay tree structure pointer
 * @param val delay value to insert
 * @param stamp timestamp of when the delay value was taken
 */
void Tree_Insert(tree_t* tree, int32_t val, struct timeval stamp) {
        node_t* root;
        node_t* tmp;

        /* update the last value added to tree to inserted value */
        tree->last_val.val = val;
        tree->last_val.stamp = stamp;
        
        root = tree->root;
        do {
                if (root == NULL) {
                        /* besides entering the func with an empty
                         * tree we can also get here by expiring all
                         * the nodes in a tree */
                        root = Tree_Acquire_Node(tree);
                        if (root == NULL) {
//                              /* printf("Tree_Insert Reached max nodes, node acquistion failed\n"); */
                                return;
                        }
                        root->val       = val;
                        root->stamp     = stamp;
                        tree->root      = root;
//                      printf("insert1: \n");
//                      Tree_Print(tree);
                        return;
                }
                
                if (val == root->val) {
                        root->stamp = stamp;
//                      printf("insert2: \n");
//                      Tree_Print(tree);
                        return;
                }

                /* on our walk prune those nodes that are too old
                 * (outside the current history window) */
                if (VALUE_EXPIRED(root->stamp, stamp, tree->window)) {
                        /* printf("expired node[%u %u] stamp[%u %u] win[%u %u]",
                           root->stamp.tv_sec, root->stamp.tv_usec,
                           stamp.tv_sec, stamp.tv_usec,
                           tree->window.tv_sec, tree->window.tv_usec); */
                        tmp = root->parent;
                        Tree_Delete(tree, root);
                        if (tmp == NULL) {
                                root = tree->root;
                        } else {
                                root = tmp;
                        }
                        continue;
                }
                if (val < root->val) {
                        if (root->left == NULL) {
                                goto add_left;
                        }
                        root = root->left;
                } else { /* if (val > root->val) */
                        if (root->right == NULL) {
                                goto add_right;
                        }
                        root = root->right;
                }
        } while (1);
 add_left:
        /* printf("adding left of node[%d]\n", root->val); */
        root->left              = Tree_Acquire_Node(tree);
        if (root->left == NULL) {
//              printf("insert3: \n");
//              Tree_Print(tree);
                return;
        }
        root->left->val         = val;
        root->left->stamp       = stamp;
        root->left->parent      = root;
        /* only balance the tree if we added to the height of the tree */
        if (root->right == NULL) {
                root->height = 2;
        }
        Tree_Balance(tree, root->parent);
//      printf("insert4: \n");
//      Tree_Print(tree);
        return;
 add_right:
////    printf("adding right of node[%d]\n", root->val);
        root->right             = Tree_Acquire_Node(tree);
        if (root->right == NULL) {
//              printf("insert5: \n");
//              Tree_Print(tree);
                return;
        }
        root->right->val        = val;
        root->right->stamp      = stamp;
        root->right->parent     = root;
        /* only balance the tree if we added to the height of the tree */
        if (root->left == NULL) {
                root->height = 2;
        }
        Tree_Balance(tree, root->parent);
//      printf("insert6: \n");
//      Tree_Print(tree);
        return;
} /* Tree_Add() */

/**
 * Retrieves the minimum delay from the tree. Returns the last value
 * added to the tree if the tree is empty (all values were expired).
 *
 * @param tree binary delay tree structure pointer
 * @param stamp current timestamp with which to possibly prune values in the tree
 */
int32_t Tree_Min(tree_t* tree, struct timeval stamp) {
        node_t* root;
        node_t* tmp;

        if (tree->root == NULL) {
                return tree->last_val.val;
        }

        root = tree->root;
        do {
                /* on our walk to find the min, prune those nodes that
                 * are too old (outside the current history window) */
                while (VALUE_EXPIRED(root->stamp, stamp, tree->window)) {
                        tmp = root->parent;
                        Tree_Delete(tree, root);
                        if (tmp == NULL) {
                                if (tree->root == NULL) {
                                        /* expired all nodes in the tree */
                                        return tree->last_val.val;
                                }
                                root = tree->root;
                        } else {
                                root = tmp;
                        }
                }
        } while ((root->left != NULL) && (root = root->left));
        return root->val;
} /* Tree_Min() */

/**
 * Retrieves the maximum delay from the tree. Returns the last value
 * added to the tree if the tree is empty (all values were expired).
 *
 * @param tree binary delay tree structure pointer
 * @param stamp current timestamp with which to possibly prune values in the tree
 */
int32_t Tree_Max(tree_t* tree, struct timeval stamp) {
        node_t* root;
        node_t* tmp;

        if (tree->root == NULL) {
                return tree->last_val.val;
        }

        root = tree->root;
        do {
                /* on our walk to find the max, prune those nodes that
                 * are too old (outside the current history window) */
                while (VALUE_EXPIRED(root->stamp, stamp, tree->window)) {
                        tmp = root->parent;
                        Tree_Delete(tree, root);
                        if (tmp == NULL) {
                                if (tree->root == NULL) {
                                        /* expired all nodes in the tree */
                                        return tree->last_val.val;
                                }
                                root = tree->root;
                        } else {
                                root = tmp;
                        }
                }
        } while ((root->right != NULL) && (root = root->right));
        return root->val;
} /* Tree_Max() */

/**
 * Prints the tree by using the print helper function for recursion
 *
 * @param tree binary delay tree structure pointer
 */
void Tree_Print(tree_t* tree) {
        if (tree->root != NULL) {
                Tree_Print_Helper(tree->root);
                printf("\n");
        } else {
                printf("Empty Tree\n");
        }
} /* Tree_Print() */

---