xref: /unit/src/nxt_rbtree.c (revision 23:600903c98957)
1 
2 /*
3  * Copyright (C) Igor Sysoev
4  * Copyright (C) NGINX, Inc.
5  */
6 
7 #include <nxt_main.h>
8 
9 
10 /*
11  * The red-black tree code is based on the algorithm described in
12  * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
13  */
14 
15 
16 static void nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node);
17 static void nxt_rbtree_delete_fixup(nxt_rbtree_t *tree,
18     nxt_rbtree_node_t *node);
19 nxt_inline void nxt_rbtree_left_rotate(nxt_rbtree_node_t *node);
20 nxt_inline void nxt_rbtree_right_rotate(nxt_rbtree_node_t *node);
21 nxt_inline void nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst,
22     nxt_rbtree_node_t *node);
23 
24 
25 #define NXT_RBTREE_BLACK  0
26 #define NXT_RBTREE_RED    1
27 
28 
29 #define nxt_rbtree_comparison_callback(tree)                                  \
30     ((nxt_rbtree_compare_t) (tree)->sentinel.right)
31 
32 
33 void
34 nxt_rbtree_init(nxt_rbtree_t *tree, nxt_rbtree_compare_t compare)
35 {
36     /*
37      * The sentinel is used as a leaf node sentinel and as a tree root
38      * sentinel: it is a parent of a root node and the root node is
39      * the left child of the sentinel.  Combining two sentinels in one
40      * entry and the fact that the sentinel's left child is a root node
41      * simplifies nxt_rbtree_node_successor() and eliminates explicit
42      * root node test before or inside nxt_rbtree_min().
43      */
44 
45     /* The root is empty. */
46     tree->sentinel.left = &tree->sentinel;
47 
48     /*
49      * The sentinel's right child is never used so
50      * comparison callback can be safely stored here.
51      */
52     tree->sentinel.right = (void *) compare;
53 
54     /* The root and leaf sentinel must be black. */
55     tree->sentinel.color = NXT_RBTREE_BLACK;
56 }
57 
58 
59 void
60 nxt_rbtree_insert(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
61 {
62     nxt_rbtree_node_t     *node, *new_node, *sentinel, **child;
63     nxt_rbtree_compare_t  compare;
64 
65     new_node = (nxt_rbtree_node_t *) part;
66 
67     node = nxt_rbtree_root(tree);
68     sentinel = nxt_rbtree_sentinel(tree);
69 
70     new_node->left = sentinel;
71     new_node->right = sentinel;
72     new_node->color = NXT_RBTREE_RED;
73 
74     compare = (nxt_rbtree_compare_t) tree->sentinel.right;
75     child = &nxt_rbtree_root(tree);
76 
77     while (*child != sentinel) {
78         node = *child;
79 
80         nxt_prefetch(node->left);
81         nxt_prefetch(node->right);
82 
83         child = (compare(new_node, node) < 0) ? &node->left : &node->right;
84     }
85 
86     *child = new_node;
87     new_node->parent = node;
88 
89     nxt_rbtree_insert_fixup(new_node);
90 
91     node = nxt_rbtree_root(tree);
92     node->color = NXT_RBTREE_BLACK;
93 }
94 
95 
96 static void
97 nxt_rbtree_insert_fixup(nxt_rbtree_node_t *node)
98 {
99     nxt_rbtree_node_t  *parent, *grandparent, *uncle;
100 
101     /*
102      * Prefetching parent nodes does not help here because they are
103      * already traversed during insertion.
104      */
105 
106     for ( ;; ) {
107         parent = node->parent;
108 
109         /*
110          * Testing whether a node is a tree root is not required here since
111          * a root node's parent is the sentinel and it is always black.
112          */
113         if (parent->color == NXT_RBTREE_BLACK) {
114             return;
115         }
116 
117         grandparent = parent->parent;
118 
119         if (parent == grandparent->left) {
120             uncle = grandparent->right;
121 
122             if (uncle->color == NXT_RBTREE_BLACK) {
123 
124                 if (node == parent->right) {
125                     node = parent;
126                     nxt_rbtree_left_rotate(node);
127                 }
128 
129                 parent = node->parent;
130                 parent->color = NXT_RBTREE_BLACK;
131 
132                 grandparent = parent->parent;
133                 grandparent->color = NXT_RBTREE_RED;
134                 nxt_rbtree_right_rotate(grandparent);
135                 /*
136                  * nxt_rbtree_right_rotate() does not change node->parent
137                  * color which is now black, so testing color is not required
138                  * to return from function.
139                  */
140                 return;
141             }
142 
143         } else {
144             uncle = grandparent->left;
145 
146             if (uncle->color == NXT_RBTREE_BLACK) {
147 
148                 if (node == parent->left) {
149                     node = parent;
150                     nxt_rbtree_right_rotate(node);
151                 }
152 
153                 parent = node->parent;
154                 parent->color = NXT_RBTREE_BLACK;
155 
156                 grandparent = parent->parent;
157                 grandparent->color = NXT_RBTREE_RED;
158                 nxt_rbtree_left_rotate(grandparent);
159 
160                 /* See the comment in the symmetric branch above. */
161                 return;
162             }
163         }
164 
165         uncle->color = NXT_RBTREE_BLACK;
166         parent->color = NXT_RBTREE_BLACK;
167         grandparent->color = NXT_RBTREE_RED;
168 
169         node = grandparent;
170     }
171 }
172 
173 
174 nxt_rbtree_node_t *
175 nxt_rbtree_find(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
176 {
177     intptr_t              n;
178     nxt_rbtree_node_t     *node, *next, *sentinel;
179     nxt_rbtree_compare_t  compare;
180 
181     node = (nxt_rbtree_node_t *) part;
182 
183     next = nxt_rbtree_root(tree);
184     sentinel = nxt_rbtree_sentinel(tree);
185     compare = nxt_rbtree_comparison_callback(tree);
186 
187     while (next != sentinel) {
188         nxt_prefetch(next->left);
189         nxt_prefetch(next->right);
190 
191         n = compare(node, next);
192 
193         if (n < 0) {
194             next = next->left;
195 
196         } else if (n > 0) {
197             next = next->right;
198 
199         } else {
200             return next;
201         }
202     }
203 
204     return NULL;
205 }
206 
207 
208 nxt_rbtree_node_t *
209 nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
210 {
211     intptr_t              n;
212     nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
213     nxt_rbtree_compare_t  compare;
214 
215     node = (nxt_rbtree_node_t *) part;
216 
217     retval = NULL;
218     next = nxt_rbtree_root(tree);
219     sentinel = nxt_rbtree_sentinel(tree);
220     compare = nxt_rbtree_comparison_callback(tree);
221 
222     while (next != sentinel) {
223         nxt_prefetch(next->left);
224         nxt_prefetch(next->right);
225 
226         n = compare(node, next);
227 
228         if (n < 0) {
229             next = next->left;
230 
231         } else if (n > 0) {
232             retval = next;
233             next = next->right;
234 
235         } else {
236             /* Exact match. */
237             return next;
238         }
239     }
240 
241     return retval;
242 }
243 
244 
245 nxt_rbtree_node_t *
246 nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
247 {
248     intptr_t              n;
249     nxt_rbtree_node_t     *node, *retval, *next, *sentinel;
250     nxt_rbtree_compare_t  compare;
251 
252     node = (nxt_rbtree_node_t *) part;
253 
254     retval = NULL;
255     next = nxt_rbtree_root(tree);
256     sentinel = nxt_rbtree_sentinel(tree);
257     compare = nxt_rbtree_comparison_callback(tree);
258 
259     while (next != sentinel) {
260         nxt_prefetch(next->left);
261         nxt_prefetch(next->right);
262 
263         n = compare(node, next);
264 
265         if (n < 0) {
266             retval = next;
267             next = next->left;
268 
269         } else if (n > 0) {
270             next = next->right;
271 
272         } else {
273             /* Exact match. */
274             return next;
275         }
276     }
277 
278     return retval;
279 }
280 
281 
282 void
283 nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
284 {
285     uint8_t            color;
286     nxt_rbtree_node_t  *node, *sentinel, *subst, *child;
287 
288     node = (nxt_rbtree_node_t *) part;
289 
290     subst = node;
291     sentinel = nxt_rbtree_sentinel(tree);
292 
293     if (node->left == sentinel) {
294         child = node->right;
295 
296     } else if (node->right == sentinel) {
297         child = node->left;
298 
299     } else {
300         subst = nxt_rbtree_branch_min(tree, node->right);
301         child = subst->right;
302     }
303 
304     nxt_rbtree_parent_relink(child, subst);
305 
306     color = subst->color;
307 
308     if (subst != node) {
309         /* Move the subst node to the deleted node position in the tree. */
310 
311         subst->color = node->color;
312 
313         subst->left = node->left;
314         subst->left->parent = subst;
315 
316         subst->right = node->right;
317         subst->right->parent = subst;
318 
319         nxt_rbtree_parent_relink(subst, node);
320     }
321 
322 #if (NXT_DEBUG)
323     node->left = NULL;
324     node->right = NULL;
325     node->parent = NULL;
326 #endif
327 
328     if (color == NXT_RBTREE_BLACK) {
329         nxt_rbtree_delete_fixup(tree, child);
330     }
331 }
332 
333 
334 static void
335 nxt_rbtree_delete_fixup(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
336 {
337     nxt_rbtree_node_t  *parent, *sibling;
338 
339     while (node != nxt_rbtree_root(tree) && node->color == NXT_RBTREE_BLACK) {
340         /*
341          * Prefetching parent nodes does not help here according
342          * to microbenchmarks.
343          */
344 
345         parent = node->parent;
346 
347         if (node == parent->left) {
348             sibling = parent->right;
349 
350             if (sibling->color != NXT_RBTREE_BLACK) {
351 
352                 sibling->color = NXT_RBTREE_BLACK;
353                 parent->color = NXT_RBTREE_RED;
354 
355                 nxt_rbtree_left_rotate(parent);
356 
357                 sibling = parent->right;
358             }
359 
360             if (sibling->right->color == NXT_RBTREE_BLACK) {
361 
362                 sibling->color = NXT_RBTREE_RED;
363 
364                 if (sibling->left->color == NXT_RBTREE_BLACK) {
365                     node = parent;
366                     continue;
367                 }
368 
369                 sibling->left->color = NXT_RBTREE_BLACK;
370 
371                 nxt_rbtree_right_rotate(sibling);
372                 /*
373                  * If the node is the leaf sentinel then the right
374                  * rotate above changes its parent so a sibling below
375                  * becames the leaf sentinel as well and this causes
376                  * segmentation fault.  This is the reason why usual
377                  * red-black tree implementations with a leaf sentinel
378                  * which does not require to test leaf nodes at all
379                  * nevertheless test the leaf sentinel in the left and
380                  * right rotate procedures.  Since according to the
381                  * algorithm node->parent must not be changed by both
382                  * the left and right rotates above, it can be cached
383                  * in a local variable.  This not only eliminates the
384                  * sentinel test in nxt_rbtree_parent_relink() but also
385                  * decreases the code size because C forces to reload
386                  * non-restrict pointers.
387                  */
388                 sibling = parent->right;
389             }
390 
391             sibling->color = parent->color;
392             parent->color = NXT_RBTREE_BLACK;
393             sibling->right->color = NXT_RBTREE_BLACK;
394 
395             nxt_rbtree_left_rotate(parent);
396 
397             break;
398 
399         } else {
400             sibling = parent->left;
401 
402             if (sibling->color != NXT_RBTREE_BLACK) {
403 
404                 sibling->color = NXT_RBTREE_BLACK;
405                 parent->color = NXT_RBTREE_RED;
406 
407                 nxt_rbtree_right_rotate(parent);
408 
409                 sibling = parent->left;
410             }
411 
412             if (sibling->left->color == NXT_RBTREE_BLACK) {
413 
414                 sibling->color = NXT_RBTREE_RED;
415 
416                 if (sibling->right->color == NXT_RBTREE_BLACK) {
417                     node = parent;
418                     continue;
419                 }
420 
421                 sibling->right->color = NXT_RBTREE_BLACK;
422 
423                 nxt_rbtree_left_rotate(sibling);
424 
425                 /* See the comment in the symmetric branch above. */
426                 sibling = parent->left;
427             }
428 
429             sibling->color = parent->color;
430             parent->color = NXT_RBTREE_BLACK;
431             sibling->left->color = NXT_RBTREE_BLACK;
432 
433             nxt_rbtree_right_rotate(parent);
434 
435             break;
436         }
437     }
438 
439     node->color = NXT_RBTREE_BLACK;
440 }
441 
442 
443 nxt_inline void
444 nxt_rbtree_left_rotate(nxt_rbtree_node_t *node)
445 {
446     nxt_rbtree_node_t  *child;
447 
448     child = node->right;
449     node->right = child->left;
450     child->left->parent = node;
451     child->left = node;
452 
453     nxt_rbtree_parent_relink(child, node);
454 
455     node->parent = child;
456 }
457 
458 
459 nxt_inline void
460 nxt_rbtree_right_rotate(nxt_rbtree_node_t *node)
461 {
462     nxt_rbtree_node_t  *child;
463 
464     child = node->left;
465     node->left = child->right;
466     child->right->parent = node;
467     child->right = node;
468 
469     nxt_rbtree_parent_relink(child, node);
470 
471     node->parent = child;
472 }
473 
474 
475 /* Relink a parent from the node to the subst node. */
476 
477 nxt_inline void
478 nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst, nxt_rbtree_node_t *node)
479 {
480     nxt_rbtree_node_t  *parent, **link;
481 
482     parent = node->parent;
483     /*
484      * The leaf sentinel's parent can be safely changed here.
485      * See the comment in nxt_rbtree_delete_fixup() for details.
486      */
487     subst->parent = parent;
488     /*
489      * If the node's parent is the root sentinel it is safely changed
490      * because the root sentinel's left child is the tree root.
491      */
492     link = (node == parent->left) ? &parent->left : &parent->right;
493     *link = subst;
494 }
495 
496 
497 nxt_rbtree_node_t *
498 nxt_rbtree_destroy_next(nxt_rbtree_t *tree, nxt_rbtree_node_t **next)
499 {
500     nxt_rbtree_node_t  *node, *subst, *parent, *sentinel;
501 
502     sentinel = nxt_rbtree_sentinel(tree);
503 
504     /* Find the leftmost node. */
505     for (node = *next; node->left != sentinel; node = node->left);
506 
507     /* Replace the leftmost node with its right child. */
508     subst = node->right;
509     parent = node->parent;
510 
511     parent->left = subst;
512     subst->parent = parent;
513 
514     /*
515      * The right child is used as the next start node.  If the right child
516      * is the sentinel then parent of the leftmost node is used as the next
517      * start node.  The parent of the root node is the sentinel so after
518      * the single root node will be replaced with the sentinel, the next
519      * start node will be equal to the sentinel and iteration will stop.
520      */
521     if (subst == sentinel) {
522         subst = parent;
523     }
524 
525     *next = subst;
526 
527     return node;
528 }
529