xref: /unit/src/test/nxt_rbtree1_test.c (revision 2084)
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