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