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