1384Szelenkov@nginx.com 2384Szelenkov@nginx.com /* 3384Szelenkov@nginx.com * Copyright (C) Igor Sysoev 4384Szelenkov@nginx.com * Copyright (C) NGINX, Inc. 5384Szelenkov@nginx.com */ 6384Szelenkov@nginx.com 7384Szelenkov@nginx.com #include <nxt_main.h> 8384Szelenkov@nginx.com #include "nxt_tests.h" 9384Szelenkov@nginx.com #include "nxt_rbtree1.h" 10384Szelenkov@nginx.com 11384Szelenkov@nginx.com 12*2084Salx.manpages@gmail.com #define nxt_rbtree1_is_empty(tree) \ 13384Szelenkov@nginx.com (((tree)->root) == (tree)->sentinel) 14384Szelenkov@nginx.com 15384Szelenkov@nginx.com 16*2084Salx.manpages@gmail.com #define nxt_rbtree1_is_there_successor(tree, node) \ 17384Szelenkov@nginx.com ((node) != (tree)->sentinel) 18384Szelenkov@nginx.com 19384Szelenkov@nginx.com 20384Szelenkov@nginx.com nxt_inline nxt_rbtree1_node_t * 21384Szelenkov@nginx.com nxt_rbtree1_node_successor(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node) 22384Szelenkov@nginx.com { 23384Szelenkov@nginx.com nxt_rbtree1_node_t *parent; 24384Szelenkov@nginx.com 25384Szelenkov@nginx.com if (node->right != tree->sentinel) { 26384Szelenkov@nginx.com return nxt_rbtree1_min(node->right, tree->sentinel); 27384Szelenkov@nginx.com } 28384Szelenkov@nginx.com 29384Szelenkov@nginx.com for ( ;; ) { 30384Szelenkov@nginx.com parent = node->parent; 31384Szelenkov@nginx.com 32384Szelenkov@nginx.com if (parent == NULL) { 33384Szelenkov@nginx.com return tree->sentinel; 34384Szelenkov@nginx.com } 35384Szelenkov@nginx.com 36384Szelenkov@nginx.com if (node == parent->left) { 37384Szelenkov@nginx.com return parent; 38384Szelenkov@nginx.com } 39384Szelenkov@nginx.com 40384Szelenkov@nginx.com node = parent; 41384Szelenkov@nginx.com } 42384Szelenkov@nginx.com } 43384Szelenkov@nginx.com 44384Szelenkov@nginx.com 45384Szelenkov@nginx.com static void nxt_rbtree1_test_insert_value(nxt_rbtree1_node_t *temp, 46384Szelenkov@nginx.com nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel); 47384Szelenkov@nginx.com static nxt_int_t nxt_rbtree1_test_compare(nxt_rbtree1_node_t *node1, 48384Szelenkov@nginx.com nxt_rbtree1_node_t *node2); 49384Szelenkov@nginx.com static int nxt_cdecl nxt_rbtree1_test_sort_cmp(const void *one, 50384Szelenkov@nginx.com const void *two); 51384Szelenkov@nginx.com static nxt_rbtree1_node_t *nxt_rbtree1_test_find(nxt_rbtree1_t *tree, 52384Szelenkov@nginx.com nxt_rbtree1_node_t *node); 53384Szelenkov@nginx.com 54384Szelenkov@nginx.com 55384Szelenkov@nginx.com nxt_int_t 56384Szelenkov@nginx.com nxt_rbtree1_test(nxt_thread_t *thr, nxt_uint_t n) 57384Szelenkov@nginx.com { 58384Szelenkov@nginx.com uint32_t key, *keys; 59384Szelenkov@nginx.com nxt_uint_t i; 60384Szelenkov@nginx.com nxt_nsec_t start, end; 61384Szelenkov@nginx.com nxt_rbtree1_t tree; 62384Szelenkov@nginx.com nxt_rbtree1_node_t *node, *nodes, sentinel; 63384Szelenkov@nginx.com 64384Szelenkov@nginx.com nxt_thread_time_update(thr); 65384Szelenkov@nginx.com 66384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree1 test started: %ui", n); 67384Szelenkov@nginx.com 68384Szelenkov@nginx.com nxt_rbtree1_init(&tree, &sentinel, nxt_rbtree1_test_insert_value); 69384Szelenkov@nginx.com 70384Szelenkov@nginx.com nodes = nxt_malloc(n * sizeof(nxt_rbtree1_node_t)); 71384Szelenkov@nginx.com if (nodes == NULL) { 72384Szelenkov@nginx.com return NXT_ERROR; 73384Szelenkov@nginx.com } 74384Szelenkov@nginx.com 75384Szelenkov@nginx.com keys = nxt_malloc(n * sizeof(uint32_t)); 76384Szelenkov@nginx.com if (keys == NULL) { 77384Szelenkov@nginx.com nxt_free(keys); 78384Szelenkov@nginx.com return NXT_ERROR; 79384Szelenkov@nginx.com } 80384Szelenkov@nginx.com 81384Szelenkov@nginx.com key = 0; 82384Szelenkov@nginx.com 83384Szelenkov@nginx.com for (i = 0; i < n; i++) { 84384Szelenkov@nginx.com key = nxt_murmur_hash2(&key, sizeof(uint32_t)); 85384Szelenkov@nginx.com 86384Szelenkov@nginx.com keys[i] = key; 87384Szelenkov@nginx.com nodes[i].key = key; 88384Szelenkov@nginx.com } 89384Szelenkov@nginx.com 90384Szelenkov@nginx.com nxt_qsort(keys, n, sizeof(uint32_t), nxt_rbtree1_test_sort_cmp); 91384Szelenkov@nginx.com 92384Szelenkov@nginx.com nxt_thread_time_update(thr); 93384Szelenkov@nginx.com start = nxt_thread_monotonic_time(thr); 94384Szelenkov@nginx.com 95384Szelenkov@nginx.com for (i = 0; i < n; i++) { 96384Szelenkov@nginx.com nxt_rbtree1_insert(&tree, &nodes[i]); 97384Szelenkov@nginx.com } 98384Szelenkov@nginx.com 99384Szelenkov@nginx.com for (i = 0; i < n; i++) { 100384Szelenkov@nginx.com if (nxt_rbtree1_test_find(&tree, &nodes[i]) != &nodes[i]) { 101384Szelenkov@nginx.com nxt_log_alert(thr->log, "rbtree1 test failed: %08XD not found", 102384Szelenkov@nginx.com nodes[i].key); 103384Szelenkov@nginx.com goto fail; 104384Szelenkov@nginx.com } 105384Szelenkov@nginx.com } 106384Szelenkov@nginx.com 107384Szelenkov@nginx.com i = 0; 108384Szelenkov@nginx.com node = nxt_rbtree1_min(tree.root, tree.sentinel); 109384Szelenkov@nginx.com 110384Szelenkov@nginx.com while (nxt_rbtree1_is_there_successor(&tree, node)) { 111384Szelenkov@nginx.com 112384Szelenkov@nginx.com if (keys[i] != node->key) { 113384Szelenkov@nginx.com nxt_log_alert(thr->log, "rbtree1 test failed: %i: %08XD %08XD", 114384Szelenkov@nginx.com i, keys[i], node->key); 115384Szelenkov@nginx.com goto fail; 116384Szelenkov@nginx.com } 117384Szelenkov@nginx.com 118384Szelenkov@nginx.com i++; 119384Szelenkov@nginx.com node = nxt_rbtree1_node_successor(&tree, node); 120384Szelenkov@nginx.com } 121384Szelenkov@nginx.com 122384Szelenkov@nginx.com if (i != n) { 123384Szelenkov@nginx.com nxt_log_alert(thr->log, "rbtree1 test failed: %ui", i); 124384Szelenkov@nginx.com goto fail; 125384Szelenkov@nginx.com } 126384Szelenkov@nginx.com 127384Szelenkov@nginx.com for (i = 0; i < n; i++) { 128384Szelenkov@nginx.com nxt_rbtree1_delete(&tree, &nodes[i]); 129384Szelenkov@nginx.com nxt_memset(&nodes[i], 0xA5, sizeof(nxt_rbtree1_node_t)); 130384Szelenkov@nginx.com } 131384Szelenkov@nginx.com 132384Szelenkov@nginx.com nxt_thread_time_update(thr); 133384Szelenkov@nginx.com end = nxt_thread_monotonic_time(thr); 134384Szelenkov@nginx.com 135384Szelenkov@nginx.com if (!nxt_rbtree1_is_empty(&tree)) { 136384Szelenkov@nginx.com nxt_log_alert(thr->log, "rbtree1 test failed: tree is not empty"); 137384Szelenkov@nginx.com goto fail; 138384Szelenkov@nginx.com } 139384Szelenkov@nginx.com 140384Szelenkov@nginx.com nxt_free(keys); 141384Szelenkov@nginx.com nxt_free(nodes); 142384Szelenkov@nginx.com 143384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree1 test passed %0.3fs", 144384Szelenkov@nginx.com (end - start) / 1000000000.0); 145384Szelenkov@nginx.com 146384Szelenkov@nginx.com return NXT_OK; 147384Szelenkov@nginx.com 148384Szelenkov@nginx.com fail: 149384Szelenkov@nginx.com 150384Szelenkov@nginx.com nxt_free(keys); 151384Szelenkov@nginx.com nxt_free(nodes); 152384Szelenkov@nginx.com 153384Szelenkov@nginx.com return NXT_ERROR; 154384Szelenkov@nginx.com } 155384Szelenkov@nginx.com 156384Szelenkov@nginx.com 157384Szelenkov@nginx.com static void 158384Szelenkov@nginx.com nxt_rbtree1_test_insert_value(nxt_rbtree1_node_t *temp, 159384Szelenkov@nginx.com nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel) 160384Szelenkov@nginx.com { 161384Szelenkov@nginx.com nxt_rbtree1_node_t **p; 162384Szelenkov@nginx.com 163384Szelenkov@nginx.com for ( ;; ) { 164384Szelenkov@nginx.com nxt_prefetch(temp->left); 165384Szelenkov@nginx.com nxt_prefetch(temp->right); 166384Szelenkov@nginx.com 167384Szelenkov@nginx.com p = (node->key < temp->key) ? &temp->left : &temp->right; 168384Szelenkov@nginx.com 169384Szelenkov@nginx.com if (*p == sentinel) { 170384Szelenkov@nginx.com break; 171384Szelenkov@nginx.com } 172384Szelenkov@nginx.com 173384Szelenkov@nginx.com temp = *p; 174384Szelenkov@nginx.com } 175384Szelenkov@nginx.com 176384Szelenkov@nginx.com *p = node; 177384Szelenkov@nginx.com node->parent = temp; 178384Szelenkov@nginx.com node->left = sentinel; 179384Szelenkov@nginx.com node->right = sentinel; 180384Szelenkov@nginx.com nxt_rbtree1_red(node); 181384Szelenkov@nginx.com } 182384Szelenkov@nginx.com 183384Szelenkov@nginx.com 184384Szelenkov@nginx.com /* 185384Szelenkov@nginx.com * Subtraction cannot be used in these comparison functions because the key 186384Szelenkov@nginx.com * values are spread uniform in whole 0 .. 2^32 range but are not grouped 187384Szelenkov@nginx.com * around some value as timeout values are. 188384Szelenkov@nginx.com */ 189384Szelenkov@nginx.com 190384Szelenkov@nginx.com nxt_inline nxt_int_t 191384Szelenkov@nginx.com nxt_rbtree1_test_compare(nxt_rbtree1_node_t *node1, nxt_rbtree1_node_t *node2) 192384Szelenkov@nginx.com { 193384Szelenkov@nginx.com if (node1->key < node2->key) { 194384Szelenkov@nginx.com return -1; 195384Szelenkov@nginx.com } 196384Szelenkov@nginx.com 197384Szelenkov@nginx.com if (node1->key == node2->key) { 198384Szelenkov@nginx.com return 0; 199384Szelenkov@nginx.com } 200384Szelenkov@nginx.com 201384Szelenkov@nginx.com return 1; 202384Szelenkov@nginx.com } 203384Szelenkov@nginx.com 204384Szelenkov@nginx.com 205384Szelenkov@nginx.com static int nxt_cdecl 206384Szelenkov@nginx.com nxt_rbtree1_test_sort_cmp(const void *one, const void *two) 207384Szelenkov@nginx.com { 208384Szelenkov@nginx.com const uint32_t *first, *second; 209384Szelenkov@nginx.com 210384Szelenkov@nginx.com first = one; 211384Szelenkov@nginx.com second = two; 212384Szelenkov@nginx.com 213384Szelenkov@nginx.com if (*first < *second) { 214384Szelenkov@nginx.com return -1; 215384Szelenkov@nginx.com } 216384Szelenkov@nginx.com 217384Szelenkov@nginx.com if (*first == *second) { 218384Szelenkov@nginx.com return 0; 219384Szelenkov@nginx.com } 220384Szelenkov@nginx.com 221384Szelenkov@nginx.com return 1; 222384Szelenkov@nginx.com } 223384Szelenkov@nginx.com 224384Szelenkov@nginx.com 225384Szelenkov@nginx.com static nxt_rbtree1_node_t * 226384Szelenkov@nginx.com nxt_rbtree1_test_find(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node) 227384Szelenkov@nginx.com { 228384Szelenkov@nginx.com nxt_int_t n; 229384Szelenkov@nginx.com nxt_rbtree1_node_t *next, *sentinel; 230384Szelenkov@nginx.com 231384Szelenkov@nginx.com next = tree->root; 232384Szelenkov@nginx.com sentinel = tree->sentinel; 233384Szelenkov@nginx.com 234384Szelenkov@nginx.com while (next != sentinel) { 235384Szelenkov@nginx.com nxt_prefetch(next->left); 236384Szelenkov@nginx.com nxt_prefetch(next->right); 237384Szelenkov@nginx.com 238384Szelenkov@nginx.com n = nxt_rbtree1_test_compare(node, next); 239384Szelenkov@nginx.com 240384Szelenkov@nginx.com if (n < 0) { 241384Szelenkov@nginx.com next = next->left; 242384Szelenkov@nginx.com 243384Szelenkov@nginx.com } else if (n > 0) { 244384Szelenkov@nginx.com next = next->right; 245384Szelenkov@nginx.com 246384Szelenkov@nginx.com } else { 247384Szelenkov@nginx.com return next; 248384Szelenkov@nginx.com } 249384Szelenkov@nginx.com } 250384Szelenkov@nginx.com 251384Szelenkov@nginx.com return NULL; 252384Szelenkov@nginx.com } 253384Szelenkov@nginx.com 254384Szelenkov@nginx.com 255384Szelenkov@nginx.com #if (NXT_TEST_RTDTSC) 256384Szelenkov@nginx.com 257384Szelenkov@nginx.com #define NXT_RBT_STEP (21 * nxt_pagesize / 10 / sizeof(nxt_rbtree1_node_t)) 258384Szelenkov@nginx.com 259384Szelenkov@nginx.com static nxt_rbtree1_t mb_tree; 260384Szelenkov@nginx.com static nxt_rbtree1_node_t mb_sentinel; 261384Szelenkov@nginx.com static nxt_rbtree1_node_t *mb_nodes; 262384Szelenkov@nginx.com 263384Szelenkov@nginx.com 264384Szelenkov@nginx.com nxt_int_t 265384Szelenkov@nginx.com nxt_rbtree1_mb_start(nxt_thread_t *thr) 266384Szelenkov@nginx.com { 267384Szelenkov@nginx.com uint32_t key; 268384Szelenkov@nginx.com uint64_t start, end; 269384Szelenkov@nginx.com nxt_uint_t i, n; 270384Szelenkov@nginx.com 271384Szelenkov@nginx.com n = NXT_RBT_STEP; 272384Szelenkov@nginx.com 273384Szelenkov@nginx.com mb_nodes = nxt_malloc(NXT_RBT_NODES * n * sizeof(nxt_rbtree1_node_t)); 274384Szelenkov@nginx.com if (mb_nodes == NULL) { 275384Szelenkov@nginx.com return NXT_ERROR; 276384Szelenkov@nginx.com } 277384Szelenkov@nginx.com 278384Szelenkov@nginx.com nxt_rbtree1_init(&mb_tree, &mb_sentinel, nxt_rbtree1_test_insert_value); 279384Szelenkov@nginx.com 280384Szelenkov@nginx.com key = 0; 281384Szelenkov@nginx.com 282384Szelenkov@nginx.com for (i = 0; i < NXT_RBT_NODES; i++) { 283384Szelenkov@nginx.com key = nxt_murmur_hash2(&key, sizeof(uint32_t)); 284384Szelenkov@nginx.com mb_nodes[n * i].key = key; 285384Szelenkov@nginx.com } 286384Szelenkov@nginx.com 287384Szelenkov@nginx.com for (i = 0; i < NXT_RBT_NODES - 2; i++) { 288384Szelenkov@nginx.com nxt_rbtree1_insert(&mb_tree, &mb_nodes[n * i]); 289384Szelenkov@nginx.com } 290384Szelenkov@nginx.com 291384Szelenkov@nginx.com n *= (NXT_RBT_NODES - 2); 292384Szelenkov@nginx.com 293384Szelenkov@nginx.com start = nxt_rdtsc(); 294384Szelenkov@nginx.com nxt_rbtree1_insert(&mb_tree, &mb_nodes[n]); 295384Szelenkov@nginx.com end = nxt_rdtsc(); 296384Szelenkov@nginx.com 297384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, 298384Szelenkov@nginx.com "rbtree1 mb cached insert: %L cycles", end - start); 299384Szelenkov@nginx.com 300384Szelenkov@nginx.com return NXT_OK; 301384Szelenkov@nginx.com } 302384Szelenkov@nginx.com 303384Szelenkov@nginx.com 304384Szelenkov@nginx.com void 305384Szelenkov@nginx.com nxt_rbtree1_mb_insert(nxt_thread_t *thr) 306384Szelenkov@nginx.com { 307384Szelenkov@nginx.com uint64_t start, end; 308384Szelenkov@nginx.com nxt_uint_t n; 309384Szelenkov@nginx.com 310384Szelenkov@nginx.com n = NXT_RBT_STEP; 311384Szelenkov@nginx.com n *= (NXT_RBT_NODES - 1); 312384Szelenkov@nginx.com 313384Szelenkov@nginx.com start = nxt_rdtsc(); 314384Szelenkov@nginx.com nxt_rbtree1_insert(&mb_tree, &mb_nodes[n]); 315384Szelenkov@nginx.com end = nxt_rdtsc(); 316384Szelenkov@nginx.com 317384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, 318384Szelenkov@nginx.com "rbtree1 mb insert: %L cycles", end - start); 319384Szelenkov@nginx.com } 320384Szelenkov@nginx.com 321384Szelenkov@nginx.com 322384Szelenkov@nginx.com void 323384Szelenkov@nginx.com nxt_rbtree1_mb_delete(nxt_thread_t *thr) 324384Szelenkov@nginx.com { 325384Szelenkov@nginx.com uint64_t start, end; 326384Szelenkov@nginx.com nxt_uint_t n; 327384Szelenkov@nginx.com 328384Szelenkov@nginx.com n = NXT_RBT_STEP; 329384Szelenkov@nginx.com n *= (NXT_RBT_NODES / 4 + 1); 330384Szelenkov@nginx.com 331384Szelenkov@nginx.com start = nxt_rdtsc(); 332384Szelenkov@nginx.com nxt_rbtree1_delete(&mb_tree, &mb_nodes[n]); 333384Szelenkov@nginx.com end = nxt_rdtsc(); 334384Szelenkov@nginx.com 335384Szelenkov@nginx.com nxt_log_error(NXT_LOG_NOTICE, thr->log, 336384Szelenkov@nginx.com "rbtree1 mb delete: %L cycles", end - start); 337384Szelenkov@nginx.com 338384Szelenkov@nginx.com nxt_free(mb_nodes); 339384Szelenkov@nginx.com } 340384Szelenkov@nginx.com 341384Szelenkov@nginx.com #endif 342