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