src/test/rbtree_unit_test.c

/*
 * Copyright (C) Igor Sysoev
 * Copyright (C) NGINX, Inc.
 */


#include <njs_main.h>


typedef struct {
    NJS_RBTREE_NODE  (node);
    uint32_t         key;
} njs_rbtree_test_t;


static intptr_t rbtree_unit_test_comparison(njs_rbtree_node_t *node1,
    njs_rbtree_node_t *node2);
static njs_int_t rbtree_unit_test_compare(uint32_t key1, uint32_t key2);
static int njs_cdecl rbtree_unit_test_sort_cmp(const void *one,
    const void *two, void *ctx);


static njs_int_t
rbtree_unit_test(njs_uint_t n)
{
    void               *mark;
    uint32_t           key, *keys;
    njs_uint_t         i;
    njs_rbtree_t       tree;
    njs_rbtree_node_t  *node;
    njs_rbtree_test_t  *items, *item;

    njs_printf("rbtree unit test started: %l nodes\n", (long) n);

    njs_rbtree_init(&tree, rbtree_unit_test_comparison);

    mark = tree.sentinel.right;

    items = malloc(n * sizeof(njs_rbtree_test_t));
    if (items == NULL) {
        return NJS_ERROR;
    }

    keys = malloc(n * sizeof(uint32_t));
    if (keys == NULL) {
        free(items);
        return NJS_ERROR;
    }

    key = 0;

    for (i = 0; i < n; i++) {
        key = njs_murmur_hash2(&key, sizeof(uint32_t));
        keys[i] = key;
        items[i].key = key;
    }

    njs_qsort(keys, n, sizeof(uint32_t), rbtree_unit_test_sort_cmp, NULL);

    for (i = 0; i < n; i++) {
        njs_rbtree_insert(&tree, &items[i].node);
    }

    for (i = 0; i < n; i++) {
        node = njs_rbtree_find(&tree, &items[i].node);

        if (node != (njs_rbtree_node_t *) &items[i].node) {
            njs_printf("rbtree unit test failed: %08uXD not found\n",
                       items[i].key);
            goto fail;
        }
    }

    i = 0;
    node = njs_rbtree_min(&tree);

    while (njs_rbtree_is_there_successor(&tree, node)) {

        item = (njs_rbtree_test_t *) node;

        if (keys[i] != item->key) {
            njs_printf("rbtree unit test failed: %l: %08uXD %08uXD\n",
                       (long) i, keys[i], item->key);
            goto fail;
        }

        i++;
        node = njs_rbtree_node_successor(&tree, node);
    }

    if (i != n) {
        njs_printf("rbtree unit test failed: %l\n", (long) i);
        goto fail;
    }

    for (i = 0; i < n; i++) {
        njs_rbtree_delete(&tree, &items[i].node);
        njs_memset(&items[i], 0xA5, sizeof(njs_rbtree_test_t));
    }

    if (!njs_rbtree_is_empty(&tree)) {
        njs_printf("rbtree unit test failed: tree is not empty\n");
        goto fail;
    }

    /* Check that the sentinel callback was not modified. */

    if (mark != tree.sentinel.right) {
        njs_printf("rbtree sentinel unit test failed\n");
        goto fail;
    }

    free(keys);
    free(items);

    njs_printf("rbtree unit test passed\n");

    return NJS_OK;

fail:

    free(keys);
    free(items);

    return NJS_ERROR;
}


static intptr_t
rbtree_unit_test_comparison(njs_rbtree_node_t *node1, njs_rbtree_node_t *node2)
{
    njs_rbtree_test_t  *item1, *item2;

    item1 = (njs_rbtree_test_t *) node1;
    item2 = (njs_rbtree_test_t *) node2;

    return rbtree_unit_test_compare(item1->key, item2->key);
}


/*
 * Subtraction cannot be used in these comparison functions because
 * the key values are spread uniform in whole 0 .. 2^32 range but are
 * not grouped around some value as timeout values are.
 */

static njs_int_t
rbtree_unit_test_compare(uint32_t key1, uint32_t key2)
{
    if (key1 < key2) {
        return -1;
    }

    if (key1 == key2) {
        return 0;
    }

    return 1;
}


static int njs_cdecl
rbtree_unit_test_sort_cmp(const void *one, const void *two, void *ctx)
{
    const uint32_t  *first, *second;

    first = one;
    second = two;

    if (*first < *second) {
        return -1;
    }

    if (*first == *second) {
        return 0;
    }

    return 1;
}


int
main(void)
{
    return rbtree_unit_test(1000 * 1000);
}