path: root/test/nxt_rbtree_unit_test.c

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

#include <nxt_main.h>


#define NXT_RBTREE_COMPARISON  1


typedef struct {
    NXT_RBTREE_NODE  (node);
    uint32_t         key;
} nxt_rbtree_test_t;


#if (NXT_RBTREE_COMPARISON)
static nxt_int_t nxt_rbtree_unit_test_comparison(nxt_rbtree_node_t *node1,
    nxt_rbtree_node_t *node2);
#else
static void nxt_rbtree_unit_test_insertion(nxt_rbtree_node_t *node,
    nxt_rbtree_node_t *new_node, nxt_rbtree_node_t *sentinel);
static nxt_rbtree_test_t *nxt_rbtree_unit_test_find(nxt_rbtree_t *tree,
    uint32_t key);
#endif
static nxt_int_t nxt_rbtree_unit_test_compare(uint32_t key1, uint32_t key2);
static int nxt_cdecl nxt_rbtree_unit_test_sort_cmp(const void *one,
    const void *two);


nxt_int_t
nxt_rbtree_unit_test(nxt_thread_t *thr, nxt_uint_t n)
{
    void               *mark;
    uint32_t           key, *keys;
    nxt_uint_t         i;
    nxt_nsec_t         start, end;
    nxt_rbtree_t       tree;
    nxt_rbtree_node_t  *node;
    nxt_rbtree_test_t  *items, *item;

    nxt_thread_time_update(thr);

    nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree unit test started: %ui", n);

#if (NXT_RBTREE_COMPARISON)
    nxt_rbtree_init(&tree, nxt_rbtree_unit_test_comparison, NULL);
#else
    nxt_rbtree_init(&tree, NULL, nxt_rbtree_unit_test_insertion);
#endif

    mark = tree.sentinel.right;

    items = nxt_malloc(n * sizeof(nxt_rbtree_test_t));
    if (items == NULL) {
        return NXT_ERROR;
    }

    keys = nxt_malloc(n * sizeof(uint32_t));
    if (keys == NULL) {
        nxt_free(keys);
        return NXT_ERROR;
    }

    key = 0;

    for (i = 0; i < n; i++) {
        key = nxt_murmur_hash2(&key, sizeof(uint32_t));

        keys[i] = key;
        items[i].key = key;
    }

    nxt_qsort(keys, n, sizeof(uint32_t), nxt_rbtree_unit_test_sort_cmp);

    nxt_thread_time_update(thr);
    start = nxt_thread_monotonic_time(thr);

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

    for (i = 0; i < n; i++) {
#if (NXT_RBTREE_COMPARISON)
        node = nxt_rbtree_find(&tree, &items[i].node);

        if (node != (nxt_rbtree_node_t *) &items[i].node) {
#else
        if (nxt_rbtree_unit_test_find(&tree, items[i].key) != &items[i]) {
#endif
            nxt_log_alert(thr->log, "rbtree unit test failed: %08XD not found",
                          items[i].key);
            goto fail;
        }
    }

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

    while (nxt_rbtree_is_there_successor(&tree, node)) {

        item = (nxt_rbtree_test_t *) node;

        if (keys[i] != item->key) {
            nxt_log_alert(thr->log, "rbtree unit test failed: %i: %08XD %08XD",
                          i, keys[i], item->key);
            goto fail;
        }

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

    if (i != n) {
        nxt_log_alert(thr->log, "rbtree unit test failed: %ui", i);
        goto fail;
    }

    for (i = 0; i < n; i++) {
        nxt_rbtree_delete(&tree, &items[i].node);
        nxt_memset(&items[i], 0xA5, sizeof(nxt_rbtree_test_t));
    }

    nxt_thread_time_update(thr);
    end = nxt_thread_monotonic_time(thr);

    if (!nxt_rbtree_is_empty(&tree)) {
        nxt_log_alert(thr->log, "rbtree unit test failed: tree is not empty");
        goto fail;
    }

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

    if (mark != tree.sentinel.right) {
        nxt_log_alert(thr->log, "rbtree sentinel unit test failed");
        goto fail;
    }

    nxt_free(keys);
    nxt_free(items);

    nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree unit test passed %0.3fs",
                  (end - start) / 1000000000.0);

    return NXT_OK;

fail:

    nxt_free(keys);
    nxt_free(items);

    return NXT_ERROR;
}


#if (NXT_RBTREE_COMPARISON)

static nxt_int_t
nxt_rbtree_unit_test_comparison(nxt_rbtree_node_t *node1,
    nxt_rbtree_node_t *node2)
{
    nxt_rbtree_test_t  *item1, *item2;

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

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

#else

static void
nxt_rbtree_unit_test_insertion(nxt_rbtree_node_t *node,
    nxt_rbtree_node_t *new_node, nxt_rbtree_node_t *sentinel)
{
    nxt_int_t          n;
    nxt_rbtree_node_t  **child;
    nxt_rbtree_test_t  *item, *new_item;

    new_item = (nxt_rbtree_test_t *) new_node;
    child = &node;

    while (*child != sentinel) {
        node = *child;

        nxt_prefetch(node->left);
        nxt_prefetch(node->right);

        item = (nxt_rbtree_test_t *) node;

        n = nxt_rbtree_unit_test_compare(new_item->key, item->key);
        child = (n < 0) ? &node->left : &node->right;
    }

    *child = new_node;

    new_node->parent = node;
}


static nxt_rbtree_test_t *
nxt_rbtree_unit_test_find(nxt_rbtree_t *tree, uint32_t key)
{
    nxt_int_t          n;
    nxt_rbtree_node_t  *next, *sentinel;
    nxt_rbtree_test_t  *item;

    next = nxt_rbtree_root(tree);
    sentinel = nxt_rbtree_sentinel(tree);

    while (next != sentinel) {
        nxt_prefetch(next->left);
        nxt_prefetch(next->right);

        item = (nxt_rbtree_test_t *) next;

        n = nxt_rbtree_unit_test_compare(key, item->key);

        if (n < 0) {
            next = next->left;

        } else if (n > 0) {
            next = next->right;

        } else {
            return (nxt_rbtree_test_t *) next;
        }
    }

    return NULL;
}

#endif


/*
 * 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 nxt_int_t
nxt_rbtree_unit_test_compare(uint32_t key1, uint32_t key2)
{
    if (key1 < key2) {
        return -1;
    }

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

    return 1;
}


static int nxt_cdecl
nxt_rbtree_unit_test_sort_cmp(const void *one, const void *two)
{
    const uint32_t  *first, *second;

    first = one;
    second = two;

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

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

    return 1;
}


#if (NXT_UNIT_TEST_RTDTSC)

#define NXT_RBT_STEP      (21 * nxt_pagesize / 10 / sizeof(nxt_rbtree_test_t))

static nxt_rbtree_t       mb_tree;
static nxt_rbtree_test_t  *mb_nodes;


nxt_int_t
nxt_rbtree_mb_start(nxt_thread_t *thr)
{
    uint32_t    key;
    uint64_t    start, end;
    nxt_uint_t  i, n;

    n = NXT_RBT_STEP;

    mb_nodes = nxt_malloc(NXT_RBT_NODES * n * sizeof(nxt_rbtree_test_t));
    if (mb_nodes == NULL) {
        return NXT_ERROR;
    }

#if (NXT_RBTREE_COMPARISON)
    nxt_rbtree_init(&mb_tree, nxt_rbtree_unit_test_comparison, NULL);
#else
    nxt_rbtree_init(&mb_tree, NULL, nxt_rbtree_unit_test_insertion);
#endif

    key = 0;

    for (i = 0; i < NXT_RBT_NODES; i++) {
        key = nxt_murmur_hash2(&key, sizeof(uint32_t));
        mb_nodes[n * i].key = key;
    }

    for (i = 0; i < NXT_RBT_NODES - 2; i++) {
        nxt_rbtree_insert(&mb_tree, &mb_nodes[n * i].node);
    }

    n *= (NXT_RBT_NODES - 2);

    start = nxt_rdtsc();
    nxt_rbtree_insert(&mb_tree, &mb_nodes[n].node);
    end = nxt_rdtsc();

    nxt_log_error(NXT_LOG_NOTICE, thr->log,
                  "rbtree mb cached insert: %L cycles", end - start);

    return NXT_OK;
}


void
nxt_rbtree_mb_insert(nxt_thread_t *thr)
{
    uint64_t    start, end;
    nxt_uint_t  n;

    n = NXT_RBT_STEP;
    n *= (NXT_RBT_NODES - 1);

    start = nxt_rdtsc();
    nxt_rbtree_insert(&mb_tree, &mb_nodes[n].node);
    end = nxt_rdtsc();

    nxt_log_error(NXT_LOG_NOTICE, thr->log,
                  "rbtree mb insert: %L cycles", end - start);
}


void
nxt_rbtree_mb_delete(nxt_thread_t *thr)
{
    uint64_t    start, end;
    nxt_uint_t  n;

    n = NXT_RBT_STEP;
    n *= (NXT_RBT_NODES / 4 + 1);

    start = nxt_rdtsc();
    nxt_rbtree_delete(&mb_tree, &mb_nodes[n].node);
    end = nxt_rdtsc();

    nxt_log_error(NXT_LOG_NOTICE, thr->log,
                  "rbtree mb delete: %L cycles", end - start);

    nxt_free(mb_nodes);
}

#endif