xref: /unit/src/test/nxt_rbtree_test.c (revision 384:8f86d3ff3e29)
1*384Szelenkov@nginx.com 
2*384Szelenkov@nginx.com /*
3*384Szelenkov@nginx.com  * Copyright (C) Igor Sysoev
4*384Szelenkov@nginx.com  * Copyright (C) NGINX, Inc.
5*384Szelenkov@nginx.com  */
6*384Szelenkov@nginx.com 
7*384Szelenkov@nginx.com #include <nxt_main.h>
8*384Szelenkov@nginx.com #include "nxt_tests.h"
9*384Szelenkov@nginx.com 
10*384Szelenkov@nginx.com 
11*384Szelenkov@nginx.com typedef struct {
12*384Szelenkov@nginx.com     NXT_RBTREE_NODE  (node);
13*384Szelenkov@nginx.com     uint32_t         key;
14*384Szelenkov@nginx.com } nxt_rbtree_test_t;
15*384Szelenkov@nginx.com 
16*384Szelenkov@nginx.com 
17*384Szelenkov@nginx.com static intptr_t nxt_rbtree_test_comparison(nxt_rbtree_node_t *node1,
18*384Szelenkov@nginx.com     nxt_rbtree_node_t *node2);
19*384Szelenkov@nginx.com static nxt_int_t nxt_rbtree_test_compare(uint32_t key1, uint32_t key2);
20*384Szelenkov@nginx.com static int nxt_cdecl nxt_rbtree_test_sort_cmp(const void *one, const void *two);
21*384Szelenkov@nginx.com 
22*384Szelenkov@nginx.com 
23*384Szelenkov@nginx.com nxt_int_t
nxt_rbtree_test(nxt_thread_t * thr,nxt_uint_t n)24*384Szelenkov@nginx.com nxt_rbtree_test(nxt_thread_t *thr, nxt_uint_t n)
25*384Szelenkov@nginx.com {
26*384Szelenkov@nginx.com     void               *mark;
27*384Szelenkov@nginx.com     uint32_t           key, *keys;
28*384Szelenkov@nginx.com     nxt_uint_t         i;
29*384Szelenkov@nginx.com     nxt_nsec_t         start, end;
30*384Szelenkov@nginx.com     nxt_rbtree_t       tree;
31*384Szelenkov@nginx.com     nxt_rbtree_node_t  *node;
32*384Szelenkov@nginx.com     nxt_rbtree_test_t  *items, *item;
33*384Szelenkov@nginx.com 
34*384Szelenkov@nginx.com     nxt_thread_time_update(thr);
35*384Szelenkov@nginx.com 
36*384Szelenkov@nginx.com     nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree test started: %ui", n);
37*384Szelenkov@nginx.com 
38*384Szelenkov@nginx.com     nxt_rbtree_init(&tree, nxt_rbtree_test_comparison);
39*384Szelenkov@nginx.com 
40*384Szelenkov@nginx.com     mark = tree.sentinel.right;
41*384Szelenkov@nginx.com 
42*384Szelenkov@nginx.com     items = nxt_malloc(n * sizeof(nxt_rbtree_test_t));
43*384Szelenkov@nginx.com     if (items == NULL) {
44*384Szelenkov@nginx.com         return NXT_ERROR;
45*384Szelenkov@nginx.com     }
46*384Szelenkov@nginx.com 
47*384Szelenkov@nginx.com     keys = nxt_malloc(n * sizeof(uint32_t));
48*384Szelenkov@nginx.com     if (keys == NULL) {
49*384Szelenkov@nginx.com         nxt_free(keys);
50*384Szelenkov@nginx.com         return NXT_ERROR;
51*384Szelenkov@nginx.com     }
52*384Szelenkov@nginx.com 
53*384Szelenkov@nginx.com     key = 0;
54*384Szelenkov@nginx.com 
55*384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
56*384Szelenkov@nginx.com         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
57*384Szelenkov@nginx.com 
58*384Szelenkov@nginx.com         keys[i] = key;
59*384Szelenkov@nginx.com         items[i].key = key;
60*384Szelenkov@nginx.com     }
61*384Szelenkov@nginx.com 
62*384Szelenkov@nginx.com     nxt_qsort(keys, n, sizeof(uint32_t), nxt_rbtree_test_sort_cmp);
63*384Szelenkov@nginx.com 
64*384Szelenkov@nginx.com     nxt_thread_time_update(thr);
65*384Szelenkov@nginx.com     start = nxt_thread_monotonic_time(thr);
66*384Szelenkov@nginx.com 
67*384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
68*384Szelenkov@nginx.com         nxt_rbtree_insert(&tree, &items[i].node);
69*384Szelenkov@nginx.com     }
70*384Szelenkov@nginx.com 
71*384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
72*384Szelenkov@nginx.com         node = nxt_rbtree_find(&tree, &items[i].node);
73*384Szelenkov@nginx.com 
74*384Szelenkov@nginx.com         if (node != (nxt_rbtree_node_t *) &items[i].node) {
75*384Szelenkov@nginx.com             nxt_log_alert(thr->log, "rbtree test failed: %08XD not found",
76*384Szelenkov@nginx.com                           items[i].key);
77*384Szelenkov@nginx.com             goto fail;
78*384Szelenkov@nginx.com         }
79*384Szelenkov@nginx.com     }
80*384Szelenkov@nginx.com 
81*384Szelenkov@nginx.com     i = 0;
82*384Szelenkov@nginx.com     node = nxt_rbtree_min(&tree);
83*384Szelenkov@nginx.com 
84*384Szelenkov@nginx.com     while (nxt_rbtree_is_there_successor(&tree, node)) {
85*384Szelenkov@nginx.com 
86*384Szelenkov@nginx.com         item = (nxt_rbtree_test_t *) node;
87*384Szelenkov@nginx.com 
88*384Szelenkov@nginx.com         if (keys[i] != item->key) {
89*384Szelenkov@nginx.com             nxt_log_alert(thr->log, "rbtree test failed: %i: %08XD %08XD",
90*384Szelenkov@nginx.com                           i, keys[i], item->key);
91*384Szelenkov@nginx.com             goto fail;
92*384Szelenkov@nginx.com         }
93*384Szelenkov@nginx.com 
94*384Szelenkov@nginx.com         i++;
95*384Szelenkov@nginx.com         node = nxt_rbtree_node_successor(&tree, node);
96*384Szelenkov@nginx.com     }
97*384Szelenkov@nginx.com 
98*384Szelenkov@nginx.com     if (i != n) {
99*384Szelenkov@nginx.com         nxt_log_alert(thr->log, "rbtree test failed: %ui", i);
100*384Szelenkov@nginx.com         goto fail;
101*384Szelenkov@nginx.com     }
102*384Szelenkov@nginx.com 
103*384Szelenkov@nginx.com     for (i = 0; i < n; i++) {
104*384Szelenkov@nginx.com         nxt_rbtree_delete(&tree, &items[i].node);
105*384Szelenkov@nginx.com         nxt_memset(&items[i], 0xA5, sizeof(nxt_rbtree_test_t));
106*384Szelenkov@nginx.com     }
107*384Szelenkov@nginx.com 
108*384Szelenkov@nginx.com     nxt_thread_time_update(thr);
109*384Szelenkov@nginx.com     end = nxt_thread_monotonic_time(thr);
110*384Szelenkov@nginx.com 
111*384Szelenkov@nginx.com     if (!nxt_rbtree_is_empty(&tree)) {
112*384Szelenkov@nginx.com         nxt_log_alert(thr->log, "rbtree test failed: tree is not empty");
113*384Szelenkov@nginx.com         goto fail;
114*384Szelenkov@nginx.com     }
115*384Szelenkov@nginx.com 
116*384Szelenkov@nginx.com     /* Check that the sentinel callback was not modified. */
117*384Szelenkov@nginx.com 
118*384Szelenkov@nginx.com     if (mark != tree.sentinel.right) {
119*384Szelenkov@nginx.com         nxt_log_alert(thr->log, "rbtree sentinel test failed");
120*384Szelenkov@nginx.com         goto fail;
121*384Szelenkov@nginx.com     }
122*384Szelenkov@nginx.com 
123*384Szelenkov@nginx.com     nxt_free(keys);
124*384Szelenkov@nginx.com     nxt_free(items);
125*384Szelenkov@nginx.com 
126*384Szelenkov@nginx.com     nxt_log_error(NXT_LOG_NOTICE, thr->log, "rbtree test passed %0.3fs",
127*384Szelenkov@nginx.com                   (end - start) / 1000000000.0);
128*384Szelenkov@nginx.com 
129*384Szelenkov@nginx.com     return NXT_OK;
130*384Szelenkov@nginx.com 
131*384Szelenkov@nginx.com fail:
132*384Szelenkov@nginx.com 
133*384Szelenkov@nginx.com     nxt_free(keys);
134*384Szelenkov@nginx.com     nxt_free(items);
135*384Szelenkov@nginx.com 
136*384Szelenkov@nginx.com     return NXT_ERROR;
137*384Szelenkov@nginx.com }
138*384Szelenkov@nginx.com 
139*384Szelenkov@nginx.com 
140*384Szelenkov@nginx.com static intptr_t
nxt_rbtree_test_comparison(nxt_rbtree_node_t * node1,nxt_rbtree_node_t * node2)141*384Szelenkov@nginx.com nxt_rbtree_test_comparison(nxt_rbtree_node_t *node1,
142*384Szelenkov@nginx.com     nxt_rbtree_node_t *node2)
143*384Szelenkov@nginx.com {
144*384Szelenkov@nginx.com     nxt_rbtree_test_t  *item1, *item2;
145*384Szelenkov@nginx.com 
146*384Szelenkov@nginx.com     item1 = (nxt_rbtree_test_t *) node1;
147*384Szelenkov@nginx.com     item2 = (nxt_rbtree_test_t *) node2;
148*384Szelenkov@nginx.com 
149*384Szelenkov@nginx.com     return nxt_rbtree_test_compare(item1->key, item2->key);
150*384Szelenkov@nginx.com }
151*384Szelenkov@nginx.com 
152*384Szelenkov@nginx.com 
153*384Szelenkov@nginx.com /*
154*384Szelenkov@nginx.com  * Subtraction cannot be used in these comparison functions because
155*384Szelenkov@nginx.com  * the key values are spread uniform in whole 0 .. 2^32 range but are
156*384Szelenkov@nginx.com  * not grouped around some value as timeout values are.
157*384Szelenkov@nginx.com  */
158*384Szelenkov@nginx.com 
159*384Szelenkov@nginx.com static nxt_int_t
nxt_rbtree_test_compare(uint32_t key1,uint32_t key2)160*384Szelenkov@nginx.com nxt_rbtree_test_compare(uint32_t key1, uint32_t key2)
161*384Szelenkov@nginx.com {
162*384Szelenkov@nginx.com     if (key1 < key2) {
163*384Szelenkov@nginx.com         return -1;
164*384Szelenkov@nginx.com     }
165*384Szelenkov@nginx.com 
166*384Szelenkov@nginx.com     if (key1 == key2) {
167*384Szelenkov@nginx.com         return 0;
168*384Szelenkov@nginx.com     }
169*384Szelenkov@nginx.com 
170*384Szelenkov@nginx.com     return 1;
171*384Szelenkov@nginx.com }
172*384Szelenkov@nginx.com 
173*384Szelenkov@nginx.com 
174*384Szelenkov@nginx.com static int nxt_cdecl
nxt_rbtree_test_sort_cmp(const void * one,const void * two)175*384Szelenkov@nginx.com nxt_rbtree_test_sort_cmp(const void *one, const void *two)
176*384Szelenkov@nginx.com {
177*384Szelenkov@nginx.com     const uint32_t  *first, *second;
178*384Szelenkov@nginx.com 
179*384Szelenkov@nginx.com     first = one;
180*384Szelenkov@nginx.com     second = two;
181*384Szelenkov@nginx.com 
182*384Szelenkov@nginx.com     if (*first < *second) {
183*384Szelenkov@nginx.com         return -1;
184*384Szelenkov@nginx.com     }
185*384Szelenkov@nginx.com 
186*384Szelenkov@nginx.com     if (*first == *second) {
187*384Szelenkov@nginx.com         return 0;
188*384Szelenkov@nginx.com     }
189*384Szelenkov@nginx.com 
190*384Szelenkov@nginx.com     return 1;
191*384Szelenkov@nginx.com }
192*384Szelenkov@nginx.com 
193*384Szelenkov@nginx.com 
194*384Szelenkov@nginx.com #if (NXT_TEST_RTDTSC)
195*384Szelenkov@nginx.com 
196*384Szelenkov@nginx.com #define NXT_RBT_STEP      (21 * nxt_pagesize / 10 / sizeof(nxt_rbtree_test_t))
197*384Szelenkov@nginx.com 
198*384Szelenkov@nginx.com static nxt_rbtree_t       mb_tree;
199*384Szelenkov@nginx.com static nxt_rbtree_test_t  *mb_nodes;
200*384Szelenkov@nginx.com 
201*384Szelenkov@nginx.com 
202*384Szelenkov@nginx.com nxt_int_t
nxt_rbtree_mb_start(nxt_thread_t * thr)203*384Szelenkov@nginx.com nxt_rbtree_mb_start(nxt_thread_t *thr)
204*384Szelenkov@nginx.com {
205*384Szelenkov@nginx.com     uint32_t    key;
206*384Szelenkov@nginx.com     uint64_t    start, end;
207*384Szelenkov@nginx.com     nxt_uint_t  i, n;
208*384Szelenkov@nginx.com 
209*384Szelenkov@nginx.com     n = NXT_RBT_STEP;
210*384Szelenkov@nginx.com 
211*384Szelenkov@nginx.com     mb_nodes = nxt_malloc(NXT_RBT_NODES * n * sizeof(nxt_rbtree_test_t));
212*384Szelenkov@nginx.com     if (mb_nodes == NULL) {
213*384Szelenkov@nginx.com         return NXT_ERROR;
214*384Szelenkov@nginx.com     }
215*384Szelenkov@nginx.com 
216*384Szelenkov@nginx.com     nxt_rbtree_init(&mb_tree, nxt_rbtree_test_comparison);
217*384Szelenkov@nginx.com 
218*384Szelenkov@nginx.com     key = 0;
219*384Szelenkov@nginx.com 
220*384Szelenkov@nginx.com     for (i = 0; i < NXT_RBT_NODES; i++) {
221*384Szelenkov@nginx.com         key = nxt_murmur_hash2(&key, sizeof(uint32_t));
222*384Szelenkov@nginx.com         mb_nodes[n * i].key = key;
223*384Szelenkov@nginx.com     }
224*384Szelenkov@nginx.com 
225*384Szelenkov@nginx.com     for (i = 0; i < NXT_RBT_NODES - 2; i++) {
226*384Szelenkov@nginx.com         nxt_rbtree_insert(&mb_tree, &mb_nodes[n * i].node);
227*384Szelenkov@nginx.com     }
228*384Szelenkov@nginx.com 
229*384Szelenkov@nginx.com     n *= (NXT_RBT_NODES - 2);
230*384Szelenkov@nginx.com 
231*384Szelenkov@nginx.com     start = nxt_rdtsc();
232*384Szelenkov@nginx.com     nxt_rbtree_insert(&mb_tree, &mb_nodes[n].node);
233*384Szelenkov@nginx.com     end = nxt_rdtsc();
234*384Szelenkov@nginx.com 
235*384Szelenkov@nginx.com     nxt_log_error(NXT_LOG_NOTICE, thr->log,
236*384Szelenkov@nginx.com                   "rbtree mb cached insert: %L cycles", end - start);
237*384Szelenkov@nginx.com 
238*384Szelenkov@nginx.com     return NXT_OK;
239*384Szelenkov@nginx.com }
240*384Szelenkov@nginx.com 
241*384Szelenkov@nginx.com 
242*384Szelenkov@nginx.com void
nxt_rbtree_mb_insert(nxt_thread_t * thr)243*384Szelenkov@nginx.com nxt_rbtree_mb_insert(nxt_thread_t *thr)
244*384Szelenkov@nginx.com {
245*384Szelenkov@nginx.com     uint64_t    start, end;
246*384Szelenkov@nginx.com     nxt_uint_t  n;
247*384Szelenkov@nginx.com 
248*384Szelenkov@nginx.com     n = NXT_RBT_STEP;
249*384Szelenkov@nginx.com     n *= (NXT_RBT_NODES - 1);
250*384Szelenkov@nginx.com 
251*384Szelenkov@nginx.com     start = nxt_rdtsc();
252*384Szelenkov@nginx.com     nxt_rbtree_insert(&mb_tree, &mb_nodes[n].node);
253*384Szelenkov@nginx.com     end = nxt_rdtsc();
254*384Szelenkov@nginx.com 
255*384Szelenkov@nginx.com     nxt_log_error(NXT_LOG_NOTICE, thr->log,
256*384Szelenkov@nginx.com                   "rbtree mb insert: %L cycles", end - start);
257*384Szelenkov@nginx.com }
258*384Szelenkov@nginx.com 
259*384Szelenkov@nginx.com 
260*384Szelenkov@nginx.com void
nxt_rbtree_mb_delete(nxt_thread_t * thr)261*384Szelenkov@nginx.com nxt_rbtree_mb_delete(nxt_thread_t *thr)
262*384Szelenkov@nginx.com {
263*384Szelenkov@nginx.com     uint64_t    start, end;
264*384Szelenkov@nginx.com     nxt_uint_t  n;
265*384Szelenkov@nginx.com 
266*384Szelenkov@nginx.com     n = NXT_RBT_STEP;
267*384Szelenkov@nginx.com     n *= (NXT_RBT_NODES / 4 + 1);
268*384Szelenkov@nginx.com 
269*384Szelenkov@nginx.com     start = nxt_rdtsc();
270*384Szelenkov@nginx.com     nxt_rbtree_delete(&mb_tree, &mb_nodes[n].node);
271*384Szelenkov@nginx.com     end = nxt_rdtsc();
272*384Szelenkov@nginx.com 
273*384Szelenkov@nginx.com     nxt_log_error(NXT_LOG_NOTICE, thr->log,
274*384Szelenkov@nginx.com                   "rbtree mb delete: %L cycles", end - start);
275*384Szelenkov@nginx.com 
276*384Szelenkov@nginx.com     nxt_free(mb_nodes);
277*384Szelenkov@nginx.com }
278*384Szelenkov@nginx.com 
279*384Szelenkov@nginx.com #endif
280