src/vfer_test_btree.c

Go to the documentation of this file.

/*
 * Copyright 2005, 2006, Internet2
 * Legal conditions are in file LICENSE
 * (MD5 = c434f2e53b8089d8b4d0172c7ce07360).
 */
/**
 * @file   vfer_test_btree.c
 * @author Ivan Beschastnikh
 * @brief  Tests the btree_delay implementation for storing moving delay history
 *
 * This file tests the moving(in time) delay hist implementation as an
 * AVL tree.
 *
 * -     04/30/06        ivan            Created
 */

#include "vfer_btree_delay.h"
#include "vfer_tests.h"

/**
 * Program entrance, arguments aren't used
 */
int main() {
        tree_t t;
        struct timeval tv;
        int r, j, min;

        TEST_INIT("TEST_BTREE", "test_btree.c", stdout, stdout);
        srand(time(NULL));

        /* initialize with window of 2 seconds */
        tv.tv_usec = 0;
        tv.tv_sec = 2;
        Tree_Init(&t, tv);

        /* insert a number in the middle of the window & check that min is correct */
        tv.tv_sec = 1;
        Tree_Insert(&t, 5, tv);
        TEST_CHECK((Tree_Min(&t, tv) == 5), "Tree_Min[1] incorrect return value");

        /* insert a number with a stamp expiring the first number & check that min is correct */
        tv.tv_sec = 4;
        Tree_Insert(&t, 6, tv);
        TEST_CHECK((Tree_Min(&t, tv) == 6), "Tree_Min[2] incorrect return value");

        /* check corner case where a val is on the edge of the window (check by using min) */
        tv.tv_sec = 6;
        Tree_Insert(&t, 7, tv);
        TEST_CHECK((Tree_Min(&t, tv) == 6), "Tree_Min[3] incorrect return value");

        /* expire the value in the tree and make sure min returns the last value inserted */
        tv.tv_sec = 9;
        TEST_CHECK((Tree_Min(&t, tv) == 7), "Tree_Min[4] incorrect return value");

        /* set the window to a high value, and make sure that min is
         * preserved for a long time & is consistent */
        tv.tv_sec = 256;
        Tree_Set_Window(&t, tv);
        min = 128;
        for (j = 0; j < 256; j++) {
                tv.tv_sec = j;
                r = rand() % 128;
                if (r < min) min = r;
                Tree_Insert(&t, r, tv);
                TEST_CHECK((Tree_Min(&t, tv) == min), "Tree_Min[loop] incorrect return value");
        }
        
        /* enqueue another set of values but this time in increasing
         * order & then check that they expire in a sliding window
         * fashion */
        for (j = 0; j < 256; j++) {
                tv.tv_sec = 256+j;
                Tree_Insert(&t, j, tv);
        }
        for (j = 0; j < 256; j++) {
                tv.tv_sec = 512+j;
                TEST_CHECK((Tree_Min(&t, tv) == j), "Tree_Min[loop2] incorrect return value");
        }

        TEST_SUMMARY();
        return 0;
} /* main() */

---