heap_tests.c

Go to the documentation of this file.

#include "acutest.h"
#include <freeradius-devel/util/time.h>
#include <freeradius-devel/util/rand.h>
 
#include "../heap.c"
 
static bool fr_heap_check(fr_heap_t *h, void *data)
{
        unsigned int i;
 
        if (!h || (h->num_elements == 0)) return false;
 
        for (i = 0; i < h->num_elements; i++) {
                if (h->p[i + 1] == data) {
                        return true;
                }
        }
 
        return false;
}
 
typedef struct {
        int             data;
        unsigned int    heap;           /* for the heap */
} heap_thing;
 
 
/*
 *  cc -g -DTESTING -I .. heap.c -o heap
 *
 *  ./heap
 */
static fr_cmp_ret_t heap_cmp(void const *one, void const *two)
{
        heap_thing const *a = one, *b = two;
 
        return CMP_PREFER_SMALLER(a->data, b->data);
}
 
#define HEAP_TEST_SIZE (4096)
 
static void heap_test(int skip)
{
        fr_heap_t       *hp;
        int             i;
        heap_thing      *array;
        int             left;
        int             ret;
        fr_fast_rand_t  rand_ctx;
 
        rand_ctx.a = fr_rand();
        rand_ctx.b = fr_rand();
 
        hp = fr_heap_alloc(NULL, heap_cmp, heap_thing, heap, 0);
        TEST_CHECK(hp != NULL);
 
        array = calloc(HEAP_TEST_SIZE, sizeof(heap_thing));
 
        /*
         *      Initialise random values
         */
        for (i = 0; i < HEAP_TEST_SIZE; i++) array[i].data = fr_fast_rand(&rand_ctx) % 65537;
 
#if 0
        for (i = 0; i < HEAP_TEST_SIZE; i++) {
                printf("Array %d has value %d at offset %d\n",
                       i, array[i].data, array[i].heap);
        }
#endif
 
        TEST_CASE("insertions");
        for (i = 0; i < HEAP_TEST_SIZE; i++) {
                FR_HEAP_VERIFY(hp);
                TEST_CHECK((ret = fr_heap_insert(&hp, &array[i])) >= 0);
                TEST_MSG("insert failed, returned %i - %s", ret, fr_strerror());
 
                TEST_CHECK(fr_heap_check(hp, &array[i]));
                TEST_MSG("element %i inserted but not in heap", i);
        }
 
        TEST_CASE("deletions");
        {
                int entry;
 
                for (i = 0; i < HEAP_TEST_SIZE / skip; i++) {
                        entry = i * skip;
 
                        FR_HEAP_VERIFY(hp);
                        TEST_CHECK(array[entry].heap != 0);
                        TEST_MSG("element %i removed out of order", entry);
 
                        TEST_CHECK((ret = fr_heap_extract(&hp, &array[entry])) >= 0);
                        TEST_MSG("element %i removal failed, returned %i - %s", entry, ret, fr_strerror());
 
                        TEST_CHECK(!fr_heap_check(hp, &array[entry]));
                        TEST_MSG("element %i removed but still in heap", entry);
 
                        TEST_CHECK(array[entry].heap == 0);
                        TEST_MSG("element %i removed out of order", entry);
                }
        }
 
        left = fr_heap_num_elements(hp);
        for (i = 0; i < left; i++) {
                heap_thing *t;
 
                FR_HEAP_VERIFY(hp);
                TEST_CHECK((t = fr_heap_peek(hp)) != NULL);
                TEST_MSG("expected %i elements remaining in the heap", left - i);
 
                TEST_CHECK(fr_heap_extract(&hp, t) >= 0);
                TEST_MSG("failed extracting %i", i);
        }
 
        TEST_CHECK((ret = fr_heap_num_elements(hp)) == 0);
        TEST_MSG("%i elements remaining", ret);
 
        talloc_free(hp);
        free(array);
}
 
static void heap_test_skip_0(void)
{
        heap_test(1);
}
 
static void heap_test_skip_2(void)
{
        heap_test(2);
}
 
static void heap_test_skip_10(void)
{
        heap_test(10);
}
 
#define HEAP_CYCLE_SIZE (1600000)
 
static void heap_test_order(void)
{
        fr_heap_t       *hp;
        int             i;
        heap_thing      *array;
        heap_thing      *thing, *prev = NULL;
        int             data = 0;
        unsigned int    count = 0;
        int             ret;
        fr_fast_rand_t  rand_ctx;
 
        rand_ctx.a = fr_rand();
        rand_ctx.b = fr_rand();
 
        hp = fr_heap_alloc(NULL, heap_cmp, heap_thing, heap, 0);
        TEST_CHECK(hp != NULL);
 
        array = calloc(HEAP_TEST_SIZE, sizeof(heap_thing));
 
        /*
         *      Initialise random values
         */
        for (i = 0; i < HEAP_TEST_SIZE; i++) array[i].data = fr_fast_rand(&rand_ctx) % 65537;
 
        TEST_CASE("insertions");
        for (i = 0; i < HEAP_TEST_SIZE; i++) {
                TEST_CHECK((ret = fr_heap_insert(&hp, &array[i])) >= 0);
                TEST_MSG("insert failed, returned %i - %s", ret, fr_strerror());
 
                TEST_CHECK(fr_heap_check(hp, &array[i]));
                TEST_MSG("element %i inserted but not in heap", i);
        }
 
        TEST_CASE("ordering");
 
        while ((fr_heap_pop((void **)&thing, &hp) == 0) && thing) {
                TEST_CHECK(thing->data >= data);
                TEST_MSG("Expected data >= %i, got %i", data, thing->data);
                if (thing->data >= data) data = thing->data;
                TEST_CHECK(thing != prev);
                prev = thing;
                count++;
        }
 
        TEST_CHECK(count == HEAP_TEST_SIZE);
 
        talloc_free(hp);
        free(array);
}
 
#define HEAP_ITER_SIZE  20
 
static void heap_iter(void)
{
        fr_heap_t       *hp;
        heap_thing      *array;
        unsigned int    data_set;
 
        hp = fr_heap_alloc(NULL, heap_cmp, heap_thing, heap, 0);
        TEST_CHECK(hp != NULL);
 
        array = calloc(HEAP_ITER_SIZE, sizeof(heap_thing));
 
        for (size_t i = 0; i < HEAP_ITER_SIZE; i++) {
                array[i].data = i;
                TEST_CHECK(fr_heap_insert(&hp, &array[i])  >= 0);
        }
 
        data_set = 0;
        fr_heap_foreach(hp, heap_thing, item) {
                TEST_CHECK((data_set & (1U << item->data)) == 0);
                data_set |= (1U << item->data);
        }}
        TEST_CHECK(data_set == ((1U << HEAP_ITER_SIZE) - 1U));
 
        talloc_free(hp);
        free(array);
}
 
static void heap_cycle(void)
{
        fr_heap_t       *hp;
        int             i;
        heap_thing      *array;
        int             to_remove;
        int             inserted, removed;
        int             ret;
        fr_time_t       start_insert, start_remove, start_swap, end;
        fr_fast_rand_t  rand_ctx;
 
        rand_ctx.a = fr_rand();
        rand_ctx.b = fr_rand();
 
        hp = fr_heap_alloc(NULL, heap_cmp, heap_thing, heap, 0);
        TEST_CHECK(hp != NULL);
 
        array = calloc(HEAP_CYCLE_SIZE, sizeof(heap_thing));
 
        /*
         *      Initialise random values
         */
        for (i = 0; i < HEAP_CYCLE_SIZE; i++) array[i].data = fr_fast_rand(&rand_ctx) % 65537;
 
        start_insert = fr_time();
        TEST_CASE("insertions");
        for (i = 0; i < HEAP_CYCLE_SIZE; i++) {
                TEST_CHECK((ret = fr_heap_insert(&hp, &array[i])) >= 0);
                TEST_MSG("insert failed, returned %i - %s", ret, fr_strerror());
        }
        TEST_CHECK(fr_heap_num_elements(hp) == HEAP_CYCLE_SIZE);
 
        TEST_CASE("pop");
 
        /*
         *      Remove a random number of elements from the heap
         */
        to_remove = fr_heap_num_elements(hp) / 2;
        start_remove = fr_time();
        for (i = 0; i < to_remove; i++) {
                heap_thing *t;
 
                TEST_CHECK((t = fr_heap_peek(hp)) != NULL);
                TEST_MSG("expected %i elements remaining in the heap", to_remove - i);
 
                TEST_CHECK(fr_heap_extract(&hp, t) >= 0);
                TEST_MSG("failed extracting %i - %s", i, fr_strerror());
        }
 
        /*
         *      Now swap the inserted and removed set creating churn
         */
        start_swap = fr_time();
        inserted = 0;
        removed = 0;
 
        for (i = 0; i < HEAP_CYCLE_SIZE; i++) {
                if (!fr_heap_entry_inserted(array[i].heap)) {
                        TEST_CHECK((ret = fr_heap_insert(&hp, &array[i])) >= 0);
                        TEST_MSG("insert failed, returned %i - %s", ret, fr_strerror());
                        inserted++;
                } else {
                        TEST_CHECK((ret = fr_heap_extract(&hp, &array[i])) >= 0);
                        TEST_MSG("element %i removal failed, returned %i - %s", i, ret, fr_strerror());
                        removed++;
                }
        }
 
        TEST_CHECK(removed == (HEAP_CYCLE_SIZE - to_remove));
        TEST_MSG("expected %i", HEAP_CYCLE_SIZE - to_remove);
        TEST_MSG("got %i", removed);
 
        TEST_CHECK(inserted == to_remove);
        TEST_MSG("expected %i", to_remove);
        TEST_MSG("got %i", inserted);
 
        end = fr_time();
 
        TEST_MSG_ALWAYS("\ncycle size: %d\n", HEAP_CYCLE_SIZE);
        TEST_MSG_ALWAYS("insert: %.2fs\n", fr_time_delta_unwrap(fr_time_sub(start_remove, start_insert)) / (double)NSEC);
        TEST_MSG_ALWAYS("extract: %.2fs\n", fr_time_delta_unwrap(fr_time_sub(start_swap, start_remove))/ (double)NSEC);
        TEST_MSG_ALWAYS("swap: %.2fs\n", fr_time_delta_unwrap(fr_time_sub(end, start_swap)) / (double)NSEC);
 
        talloc_free(hp);
        free(array);
}
 
static bool poisoned;
 
static fr_cmp_ret_t heap_poison_cmp(void const *one, void const *two)
{
        if (poisoned) {
                fr_strerror_const("Poisoned comparator");
                return CMP_ERR;
        }
 
        return heap_cmp(one, two);
}
 
/*
 *      A comparator returning CMP_ERR must complete the operation
 *      structurally (no lost or duplicated elements), report the error
 *      through the int return, and leave the ordering undefined
 *      until the offending element is removed.
 */
static void heap_test_cmp_err(void)
{
        fr_heap_t       *hp;
        heap_thing      values[8] = {};
        void            *found;
        size_t          i;
        unsigned int    popped;
 
        TEST_CASE("comparator error reported, heap structurally intact");
        hp = fr_heap_alloc(NULL, heap_poison_cmp, heap_thing, heap, 0);
        TEST_ASSERT(hp != NULL);
 
        poisoned = false;
        for (i = 0; i < NUM_ELEMENTS(values); i++) {
                values[i].data = (int)(NUM_ELEMENTS(values) - i);
                TEST_CHECK(fr_heap_insert(&hp, &values[i]) == 0);
        }
 
        poisoned = true;
 
        TEST_CHECK(fr_heap_pop(&found, &hp) == -1);
        TEST_CHECK(found == NULL);
        TEST_CHECK(fr_heap_num_elements(hp) == NUM_ELEMENTS(values) - 1);
 
        /*
         *      Once the comparator recovers, every remaining element pops
         *      back out exactly once.
         */
        poisoned = false;
        popped = 0;
        while ((fr_heap_pop(&found, &hp) == 0) && found) {
                popped++;
        }
        TEST_CHECK(popped == NUM_ELEMENTS(values) - 1);
        TEST_CHECK(fr_heap_num_elements(hp) == 0);
 
        talloc_free(hp);
}
 
TEST_LIST = {
        /*
         *      Basic tests
         */
        { "heap_test_skip_0",           heap_test_skip_0        },
        { "heap_test_skip_2",           heap_test_skip_2        },
        { "heap_test_skip_10",          heap_test_skip_10       },
        { "heap_test_order",            heap_test_order         },
        { "heap_iter",                  heap_iter               },
        { "heap_cycle",                 heap_cycle              },
        { "heap_test_cmp_err",          heap_test_cmp_err       },
        TEST_TERMINATOR
};