1 2 /* 3 * Copyright (C) Igor Sysoev 4 * Copyright (C) NGINX, Inc. 5 */ 6 7 #include <nxt_main.h> 8 #include "nxt_tests.h" 9 #include "nxt_rbtree1.h" 10 11 12 #define \ 13 nxt_rbtree1_is_empty(tree) \ 14 (((tree)->root) == (tree)->sentinel) 15 16 17 #define \ 18 nxt_rbtree1_is_there_successor(tree, node) \ 19 ((node) != (tree)->sentinel) 20 21 22 nxt_inline nxt_rbtree1_node_t * 23 nxt_rbtree1_node_successor(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node) 24 { 25 nxt_rbtree1_node_t *parent; 26 27 if (node->right != tree->sentinel) { 28 return nxt_rbtree1_min(node->right, tree->sentinel); 29 } 30 31 for ( ;; ) { 32 parent = node->parent; 33 34 if (parent == NULL) { 35 return tree->sentinel; 36 } 37 38 if (node == parent->left) { 39 return parent; 40 } 41 42 node = parent; 43 } 44 } 45 46 47 static void nxt_rbtree1_test_insert_value(nxt_rbtree1_node_t *temp, 48 nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel); 49 static nxt_int_t nxt_rbtree1_test_compare(nxt_rbtree1_node_t *node1, 50 nxt_rbtree1_node_t *node2); 51 static int nxt_cdecl nxt_rbtree1_test_sort_cmp(const void *one, 52 const void *two); 53 static nxt_rbtree1_node_t *nxt_rbtree1_test_find(nxt_rbtree1_t *tree, 54 nxt_rbtree1_node_t *node); 55 56 57 nxt_int_t 58 nxt_rbtree1_test(nxt_thread_t *thr, nxt_uint_t n) 59 { 60 uint32_t key, *keys; 61 nxt_uint_t i; 62 nxt_nsec_t start, end; 63 nxt_rbtree1_t tree; 64 nxt_rbtree1_node_t *node, *nodes, sentinel; 65 66 nxt_thread_time_update(thr); 67 68 nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree1 test started: %ui", n); 69 70 nxt_rbtree1_init(&tree, &sentinel, nxt_rbtree1_test_insert_value); 71 72 nodes = nxt_malloc(n * sizeof(nxt_rbtree1_node_t)); 73 if (nodes == NULL) { 74 return NXT_ERROR; 75 } 76 77 keys = nxt_malloc(n * sizeof(uint32_t)); 78 if (keys == NULL) { 79 nxt_free(keys); 80 return NXT_ERROR; 81 } 82 83 key = 0; 84 85 for (i = 0; i < n; i++) { 86 key = nxt_murmur_hash2(&key, sizeof(uint32_t)); 87 88 keys[i] = key; 89 nodes[i].key = key; 90 } 91 92 nxt_qsort(keys, n, sizeof(uint32_t), nxt_rbtree1_test_sort_cmp); 93 94 nxt_thread_time_update(thr); 95 start = nxt_thread_monotonic_time(thr); 96 97 for (i = 0; i < n; i++) { 98 nxt_rbtree1_insert(&tree, &nodes[i]); 99 } 100 101 for (i = 0; i < n; i++) { 102 if (nxt_rbtree1_test_find(&tree, &nodes[i]) != &nodes[i]) { 103 nxt_log_alert(thr->log, "rbtree1 test failed: %08XD not found", 104 nodes[i].key); 105 goto fail; 106 } 107 } 108 109 i = 0; 110 node = nxt_rbtree1_min(tree.root, tree.sentinel); 111 112 while (nxt_rbtree1_is_there_successor(&tree, node)) { 113 114 if (keys[i] != node->key) { 115 nxt_log_alert(thr->log, "rbtree1 test failed: %i: %08XD %08XD", 116 i, keys[i], node->key); 117 goto fail; 118 } 119 120 i++; 121 node = nxt_rbtree1_node_successor(&tree, node); 122 } 123 124 if (i != n) { 125 nxt_log_alert(thr->log, "rbtree1 test failed: %ui", i); 126 goto fail; 127 } 128 129 for (i = 0; i < n; i++) { 130 nxt_rbtree1_delete(&tree, &nodes[i]); 131 nxt_memset(&nodes[i], 0xA5, sizeof(nxt_rbtree1_node_t)); 132 } 133 134 nxt_thread_time_update(thr); 135 end = nxt_thread_monotonic_time(thr); 136 137 if (!nxt_rbtree1_is_empty(&tree)) { 138 nxt_log_alert(thr->log, "rbtree1 test failed: tree is not empty"); 139 goto fail; 140 } 141 142 nxt_free(keys); 143 nxt_free(nodes); 144 145 nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree1 test passed %0.3fs", 146 (end - start) / 1000000000.0); 147 148 return NXT_OK; 149 150 fail: 151 152 nxt_free(keys); 153 nxt_free(nodes); 154 155 return NXT_ERROR; 156 } 157 158 159 static void 160 nxt_rbtree1_test_insert_value(nxt_rbtree1_node_t *temp, 161 nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel) 162 { 163 nxt_rbtree1_node_t **p; 164 165 for ( ;; ) { 166 nxt_prefetch(temp->left); 167 nxt_prefetch(temp->right); 168 169 p = (node->key < temp->key) ? &temp->left : &temp->right; 170 171 if (*p == sentinel) { 172 break; 173 } 174 175 temp = *p; 176 } 177 178 *p = node; 179 node->parent = temp; 180 node->left = sentinel; 181 node->right = sentinel; 182 nxt_rbtree1_red(node); 183 } 184 185 186 /* 187 * Subtraction cannot be used in these comparison functions because the key 188 * values are spread uniform in whole 0 .. 2^32 range but are not grouped 189 * around some value as timeout values are. 190 */ 191 192 nxt_inline nxt_int_t 193 nxt_rbtree1_test_compare(nxt_rbtree1_node_t *node1, nxt_rbtree1_node_t *node2) 194 { 195 if (node1->key < node2->key) { 196 return -1; 197 } 198 199 if (node1->key == node2->key) { 200 return 0; 201 } 202 203 return 1; 204 } 205 206 207 static int nxt_cdecl 208 nxt_rbtree1_test_sort_cmp(const void *one, const void *two) 209 { 210 const uint32_t *first, *second; 211 212 first = one; 213 second = two; 214 215 if (*first < *second) { 216 return -1; 217 } 218 219 if (*first == *second) { 220 return 0; 221 } 222 223 return 1; 224 } 225 226 227 static nxt_rbtree1_node_t * 228 nxt_rbtree1_test_find(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node) 229 { 230 nxt_int_t n; 231 nxt_rbtree1_node_t *next, *sentinel; 232 233 next = tree->root; 234 sentinel = tree->sentinel; 235 236 while (next != sentinel) { 237 nxt_prefetch(next->left); 238 nxt_prefetch(next->right); 239 240 n = nxt_rbtree1_test_compare(node, next); 241 242 if (n < 0) { 243 next = next->left; 244 245 } else if (n > 0) { 246 next = next->right; 247 248 } else { 249 return next; 250 } 251 } 252 253 return NULL; 254 } 255 256 257 #if (NXT_TEST_RTDTSC) 258 259 #define NXT_RBT_STEP (21 * nxt_pagesize / 10 / sizeof(nxt_rbtree1_node_t)) 260 261 static nxt_rbtree1_t mb_tree; 262 static nxt_rbtree1_node_t mb_sentinel; 263 static nxt_rbtree1_node_t *mb_nodes; 264 265 266 nxt_int_t 267 nxt_rbtree1_mb_start(nxt_thread_t *thr) 268 { 269 uint32_t key; 270 uint64_t start, end; 271 nxt_uint_t i, n; 272 273 n = NXT_RBT_STEP; 274 275 mb_nodes = nxt_malloc(NXT_RBT_NODES * n * sizeof(nxt_rbtree1_node_t)); 276 if (mb_nodes == NULL) { 277 return NXT_ERROR; 278 } 279 280 nxt_rbtree1_init(&mb_tree, &mb_sentinel, nxt_rbtree1_test_insert_value); 281 282 key = 0; 283 284 for (i = 0; i < NXT_RBT_NODES; i++) { 285 key = nxt_murmur_hash2(&key, sizeof(uint32_t)); 286 mb_nodes[n * i].key = key; 287 } 288 289 for (i = 0; i < NXT_RBT_NODES - 2; i++) { 290 nxt_rbtree1_insert(&mb_tree, &mb_nodes[n * i]); 291 } 292 293 n *= (NXT_RBT_NODES - 2); 294 295 start = nxt_rdtsc(); 296 nxt_rbtree1_insert(&mb_tree, &mb_nodes[n]); 297 end = nxt_rdtsc(); 298 299 nxt_log_error(NXT_LOG_NOTICE, thr->log, 300 "rbtree1 mb cached insert: %L cycles", end - start); 301 302 return NXT_OK; 303 } 304 305 306 void 307 nxt_rbtree1_mb_insert(nxt_thread_t *thr) 308 { 309 uint64_t start, end; 310 nxt_uint_t n; 311 312 n = NXT_RBT_STEP; 313 n *= (NXT_RBT_NODES - 1); 314 315 start = nxt_rdtsc(); 316 nxt_rbtree1_insert(&mb_tree, &mb_nodes[n]); 317 end = nxt_rdtsc(); 318 319 nxt_log_error(NXT_LOG_NOTICE, thr->log, 320 "rbtree1 mb insert: %L cycles", end - start); 321 } 322 323 324 void 325 nxt_rbtree1_mb_delete(nxt_thread_t *thr) 326 { 327 uint64_t start, end; 328 nxt_uint_t n; 329 330 n = NXT_RBT_STEP; 331 n *= (NXT_RBT_NODES / 4 + 1); 332 333 start = nxt_rdtsc(); 334 nxt_rbtree1_delete(&mb_tree, &mb_nodes[n]); 335 end = nxt_rdtsc(); 336 337 nxt_log_error(NXT_LOG_NOTICE, thr->log, 338 "rbtree1 mb delete: %L cycles", end - start); 339 340 nxt_free(mb_nodes); 341 } 342 343 #endif 344