rb_tests.c

Go to the documentation of this file.

/*
 *   This library is free software; you can redistribute it and/or
 *   modify it under the terms of the GNU Lesser General Public
 *   License as published by the Free Software Foundation; either
 *   version 2.1 of the License, or (at your option) any later version.
 *
 *   This library is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 *   Lesser General Public License for more details.
 *
 *   You should have received a copy of the GNU Lesser General Public
 *   License along with this library; if not, write to the Free Software
 *   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
 */
 
/** Tests for rbtrees
 *
 * @file src/lib/util/test//rb_tests.c
 *
 * @copyright 2021 Arran Cudbard-Bell <a.cudbardb@freeradius.org>
 */
#include "acutest_common_init.h"
#include "acutest_helpers.h"
#include <freeradius-devel/util/rand.h>
#include <freeradius-devel/util/rb.h>
 
#define MAXSIZE 128
 
typedef struct {
        uint32_t        num;
        fr_rb_node_t    node;
} fr_rb_tree_test_node_t;
 
static fr_cmp_ret_t fr_rb_tree_test_cmp(void const *one, void const *two)
{
        fr_rb_tree_test_node_t const *a = one, *b = two;
        return CMP(a->num, b->num);
}
 
static int fr_rb_qsort_cmp(void const *one, void const *two)
{
        fr_rb_tree_test_node_t const *a = one, *b = two;
        return CMP(a->num, b->num);
}
 
static void test_fr_rb_iter_inorder(void)
{
        fr_rb_tree_t            *t;
        fr_rb_tree_test_node_t  sorted[MAXSIZE];
        fr_rb_tree_test_node_t  *p;
        size_t                  n, i;
        fr_rb_iter_inorder_t    iter;
 
        TEST_CASE("in-order iterator");
        t = fr_rb_inline_alloc(NULL, fr_rb_tree_test_node_t, node, fr_rb_tree_test_cmp, NULL);
        TEST_CHECK(t != NULL);
 
        n = (fr_rand() % MAXSIZE) + 1;
 
        /*
         *      Initialise the test nodes
         *      with random numbers.
         */
        for (i = 0; i < n; i++) {
                p = talloc(t, fr_rb_tree_test_node_t);
                p->num = fr_rand();
                sorted[i].num = p->num;
                fr_rb_insert(t, p);
        }
 
        qsort(sorted, n, sizeof(fr_rb_tree_test_node_t), fr_rb_qsort_cmp);
 
        for (p = fr_rb_iter_init_inorder(t, &iter), i = 0;
             p;
             p = fr_rb_iter_next_inorder(t, &iter), i++) {
                TEST_MSG("Checking sorted[%zu] s = %u vs n = %u", i, sorted[i].num, p->num);
                TEST_CHECK(sorted[i].num == p->num);
        }
 
        talloc_free(t);
}
 
/*
 *      There's no natural test for pre- and post-order traversal
 *      as there is for in-order, so we must content ourselves
 *      with static test data.
 */
static uint32_t pre_post_input[] = {0, 15, 256, 49, 3, 8192, 144, 4, 4096, 25194};
static uint32_t pre_output[] = {15, 3, 0, 4, 256, 49, 144, 8192, 4096, 25194};
static uint32_t post_output[] = {0, 4, 3, 144, 49, 4096, 25194, 8192, 256, 15};
 
static void test_fr_rb_iter_preorder(void)
{
        fr_rb_tree_t                    *t;
        fr_rb_tree_test_node_t          *p;
        size_t                          i;
        fr_rb_iter_preorder_t   iter;
 
        TEST_CASE("pre-order iterator");
        /*
         *      Build a tree from pre_post_input.
         */
        t = fr_rb_inline_alloc(NULL, fr_rb_tree_test_node_t, node, fr_rb_tree_test_cmp, NULL);
        TEST_CHECK(t != NULL);
 
        for (i = 0; i < sizeof(pre_post_input) / sizeof(uint32_t); i++) {
                p = talloc(t, fr_rb_tree_test_node_t);
                p->num = pre_post_input[i];
                fr_rb_insert(t, p);
        }
 
        for (p = fr_rb_iter_init_preorder(t, &iter), i = 0;
             p;
             p = fr_rb_iter_next_preorder(t, &iter), i++) {
                TEST_MSG("Checking pre_output[%zu] = %u vs n = %u", i, pre_output[i], p->num);
                TEST_CHECK(pre_output[i] == p->num);
        }
 
        talloc_free(t);
}
 
static void test_fr_rb_iter_postorder(void)
{
        fr_rb_tree_t                    *t;
        fr_rb_tree_test_node_t          *p;
        size_t                          i;
        fr_rb_iter_postorder_t  iter;
 
        TEST_CASE("post-order iterator");
        /*
         *      Build a tree from pre_post_input.
         */
        t = fr_rb_inline_alloc(NULL, fr_rb_tree_test_node_t, node, fr_rb_tree_test_cmp, NULL);
        TEST_CHECK(t != NULL);
 
        for (i = 0; i < sizeof(pre_post_input) / sizeof(uint32_t); i++) {
                p = talloc(t, fr_rb_tree_test_node_t);
                p->num = pre_post_input[i];
                fr_rb_insert(t, p);
        }
 
        for (p = fr_rb_iter_init_postorder(t, &iter), i = 0;
             p;
             p = fr_rb_iter_next_postorder(t, &iter), i++) {
                TEST_MSG("Checking post_output[%zu] s = %u vs n = %u", i, post_output[i], p->num);
                TEST_CHECK(post_output[i] == p->num);
        }
 
        talloc_free(t);
}
 
/*
 *      primality test used in fr_rb_delete_iter() test.
 */
static bool is_prime(uint32_t n)
{
        uint32_t        i, q;
 
        if (n < 2) return false;
 
        for (i = 2; (q = n / i) >= i; i++) {
                if (i * q == n) return false;
        }
        return true;
}
 
static uint32_t non_primes[] = { 1,  4,  6,  8,  9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27, 28,
                                 30, 32, 33, 34, 35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 49, 50};
 
static void test_fr_rb_iter_delete(void)
{
        fr_rb_tree_t                    *t;
        size_t                          i;
        fr_rb_tree_test_node_t          *p;
        fr_rb_iter_inorder_t    iter;
 
        t = fr_rb_inline_alloc(NULL, fr_rb_tree_test_node_t, node, fr_rb_tree_test_cmp, NULL);
        TEST_CHECK(t != NULL);
 
        /*
         *      Initialise the test nodes
         *      with integers from 1 to 50.
         */
        for (i = 1; i <= 50; i++) {
                p = talloc(t, fr_rb_tree_test_node_t);
                p->num = i;
                fr_rb_insert(t, p);
        }
 
        /*
         *      Remove the primes.
         */
        for (p = fr_rb_iter_init_inorder(t, &iter);
             p;
             p = fr_rb_iter_next_inorder(t, &iter)) {
                if (is_prime(p->num)) fr_rb_iter_delete_inorder(t, &iter);
        }
 
        /*
         *      Check that all the non-primes are still there.
         */
        for (p = fr_rb_iter_init_inorder(t, &iter), i = 0;
             p;
             p = fr_rb_iter_next_inorder(t, &iter), i++) {
                TEST_MSG("Checking non_primes[%zu] = %u vs p->num = %u", i, non_primes[i], p->num);
                TEST_CHECK(non_primes[i] == p->num);
        }
 
        talloc_free(t);
}
 
static bool poisoned;
 
static fr_cmp_ret_t fr_rb_tree_test_poison_cmp(void const *one, void const *two)
{
        if (poisoned) {
                fr_strerror_const("Poisoned comparator");
                return CMP_ERR;
        }
 
        return fr_rb_tree_test_cmp(one, two);
}
 
/*
 *      A comparator returning CMP_ERR must fail the operation closed,
 *      report the error through the int return, and leave the
 *      tree structurally intact.
 */
static void test_fr_rb_cmp_err(void)
{
        fr_rb_tree_t            *t;
        fr_rb_tree_test_node_t  nodes[8];
        fr_rb_tree_test_node_t  needle;
        size_t                  i;
        void                    *found;
 
        TEST_CASE("comparator error fails closed");
        t = fr_rb_inline_alloc(NULL, fr_rb_tree_test_node_t, node, fr_rb_tree_test_poison_cmp, NULL);
        TEST_CHECK(t != NULL);
 
        poisoned = false;
        for (i = 0; i < NUM_ELEMENTS(nodes); i++) {
                nodes[i].num = i * 16;
                TEST_CHECK(fr_rb_insert(t, &nodes[i]) == 0);
        }
 
        poisoned = true;
        needle.num = 3 * 16;
 
        TEST_CHECK(fr_rb_find(&found, t, &needle) == -1);
        TEST_CHECK(found == NULL);
 
        needle.num = 9 * 16;
        TEST_CHECK(fr_rb_insert(t, &needle) == -1);
        TEST_CHECK(fr_rb_num_elements(t) == NUM_ELEMENTS(nodes));
 
        found = &needle;
        TEST_CHECK(fr_rb_find_or_insert(&found, t, &needle) == -1);
        TEST_CHECK(found == NULL);
 
        needle.num = 3 * 16;
        TEST_CHECK(fr_rb_remove(&found, t, &needle) == -1);
        TEST_CHECK(found == NULL);
 
        TEST_CHECK(fr_rb_delete(t, &needle) == -1);
        TEST_CHECK(fr_rb_num_elements(t) == NUM_ELEMENTS(nodes));
 
        /*
         *      Once the comparator recovers every element is still
         *      present and findable.
         */
        poisoned = false;
        for (i = 0; i < NUM_ELEMENTS(nodes); i++) {
                needle.num = i * 16;
                TEST_CHECK(fr_rb_find(&found, t, &needle) == 0);
                TEST_CHECK(found == &nodes[i]);
        }
 
        talloc_free(t);
}
 
TEST_LIST = {
        { "fr_rb_iter_inorder",            test_fr_rb_iter_inorder },
        { "fr_rb_iter_preorder",           test_fr_rb_iter_preorder },
        { "fr_rb_iter_postorder",          test_fr_rb_iter_postorder },
        { "fr_rb_iter_delete",             test_fr_rb_iter_delete },
        { "fr_rb_cmp_err",                 test_fr_rb_cmp_err },
 
        TEST_TERMINATOR
};