blob: 4b527631dd22cd7df6f9c16042c2d9a690f04583 [file] [log] [blame]
/*
* 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);
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;
}
qsort(keys, n, sizeof(uint32_t), rbtree_unit_test_sort_cmp);
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)
{
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);
}