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 *
nxt_rbtree1_node_successor(nxt_rbtree1_t * tree,nxt_rbtree1_node_t * node)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
nxt_rbtree1_test(nxt_thread_t * thr,nxt_uint_t n)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
nxt_rbtree1_test_insert_value(nxt_rbtree1_node_t * temp,nxt_rbtree1_node_t * node,nxt_rbtree1_node_t * sentinel)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
nxt_rbtree1_test_compare(nxt_rbtree1_node_t * node1,nxt_rbtree1_node_t * node2)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
nxt_rbtree1_test_sort_cmp(const void * one,const void * two)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 *
nxt_rbtree1_test_find(nxt_rbtree1_t * tree,nxt_rbtree1_node_t * node)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
nxt_rbtree1_mb_start(nxt_thread_t * thr)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
nxt_rbtree1_mb_insert(nxt_thread_t * thr)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
nxt_rbtree1_mb_delete(nxt_thread_t * thr)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