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
nxt_rbtree_init(nxt_rbtree_t * tree,nxt_rbtree_compare_t compare)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
nxt_rbtree_insert(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)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
nxt_rbtree_insert_fixup(nxt_rbtree_node_t * node)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 /*
130 * nxt_rbtree_left_rotate() swaps parent and
131 * child whilst keeps grandparent the same.
132 */
133 parent = node->parent;
134
135 parent->color = NXT_RBTREE_BLACK;
136 grandparent->color = NXT_RBTREE_RED;
137
138 nxt_rbtree_right_rotate(grandparent);
139 /*
140 * nxt_rbtree_right_rotate() does not change node->parent
141 * color which is now black, so testing color is not required
142 * to return from function.
143 */
144 return;
145 }
146
147 } else {
148 uncle = grandparent->left;
149
150 if (uncle->color == NXT_RBTREE_BLACK) {
151
152 if (node == parent->left) {
153 node = parent;
154 nxt_rbtree_right_rotate(node);
155 }
156
157 /* See the comment in the symmetric branch above. */
158 parent = node->parent;
159
160 parent->color = NXT_RBTREE_BLACK;
161 grandparent->color = NXT_RBTREE_RED;
162
163 nxt_rbtree_left_rotate(grandparent);
164
165 /* See the comment in the symmetric branch above. */
166 return;
167 }
168 }
169
170 uncle->color = NXT_RBTREE_BLACK;
171 parent->color = NXT_RBTREE_BLACK;
172 grandparent->color = NXT_RBTREE_RED;
173
174 node = grandparent;
175 }
176 }
177
178
179 nxt_rbtree_node_t *
nxt_rbtree_find(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)180 nxt_rbtree_find(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
181 {
182 intptr_t n;
183 nxt_rbtree_node_t *node, *next, *sentinel;
184 nxt_rbtree_compare_t compare;
185
186 node = (nxt_rbtree_node_t *) part;
187
188 next = nxt_rbtree_root(tree);
189 sentinel = nxt_rbtree_sentinel(tree);
190 compare = nxt_rbtree_comparison_callback(tree);
191
192 while (next != sentinel) {
193 nxt_prefetch(next->left);
194 nxt_prefetch(next->right);
195
196 n = compare(node, next);
197
198 if (n < 0) {
199 next = next->left;
200
201 } else if (n > 0) {
202 next = next->right;
203
204 } else {
205 return next;
206 }
207 }
208
209 return NULL;
210 }
211
212
213 nxt_rbtree_node_t *
nxt_rbtree_find_less_or_equal(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)214 nxt_rbtree_find_less_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
215 {
216 intptr_t n;
217 nxt_rbtree_node_t *node, *retval, *next, *sentinel;
218 nxt_rbtree_compare_t compare;
219
220 node = (nxt_rbtree_node_t *) part;
221
222 retval = NULL;
223 next = nxt_rbtree_root(tree);
224 sentinel = nxt_rbtree_sentinel(tree);
225 compare = nxt_rbtree_comparison_callback(tree);
226
227 while (next != sentinel) {
228 nxt_prefetch(next->left);
229 nxt_prefetch(next->right);
230
231 n = compare(node, next);
232
233 if (n < 0) {
234 next = next->left;
235
236 } else if (n > 0) {
237 retval = next;
238 next = next->right;
239
240 } else {
241 /* Exact match. */
242 return next;
243 }
244 }
245
246 return retval;
247 }
248
249
250 nxt_rbtree_node_t *
nxt_rbtree_find_greater_or_equal(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)251 nxt_rbtree_find_greater_or_equal(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
252 {
253 intptr_t n;
254 nxt_rbtree_node_t *node, *retval, *next, *sentinel;
255 nxt_rbtree_compare_t compare;
256
257 node = (nxt_rbtree_node_t *) part;
258
259 retval = NULL;
260 next = nxt_rbtree_root(tree);
261 sentinel = nxt_rbtree_sentinel(tree);
262 compare = nxt_rbtree_comparison_callback(tree);
263
264 while (next != sentinel) {
265 nxt_prefetch(next->left);
266 nxt_prefetch(next->right);
267
268 n = compare(node, next);
269
270 if (n < 0) {
271 retval = next;
272 next = next->left;
273
274 } else if (n > 0) {
275 next = next->right;
276
277 } else {
278 /* Exact match. */
279 return next;
280 }
281 }
282
283 return retval;
284 }
285
286
287 void
nxt_rbtree_delete(nxt_rbtree_t * tree,nxt_rbtree_part_t * part)288 nxt_rbtree_delete(nxt_rbtree_t *tree, nxt_rbtree_part_t *part)
289 {
290 uint8_t color;
291 nxt_rbtree_node_t *node, *sentinel, *subst, *child;
292
293 node = (nxt_rbtree_node_t *) part;
294
295 subst = node;
296 sentinel = nxt_rbtree_sentinel(tree);
297
298 if (node->left == sentinel) {
299 child = node->right;
300
301 } else if (node->right == sentinel) {
302 child = node->left;
303
304 } else {
305 subst = nxt_rbtree_branch_min(tree, node->right);
306 child = subst->right;
307 }
308
309 nxt_rbtree_parent_relink(child, subst);
310
311 color = subst->color;
312
313 if (subst != node) {
314 /* Move the subst node to the deleted node position in the tree. */
315
316 subst->color = node->color;
317
318 subst->left = node->left;
319 subst->left->parent = subst;
320
321 subst->right = node->right;
322 subst->right->parent = subst;
323
324 nxt_rbtree_parent_relink(subst, node);
325 }
326
327 #if (NXT_DEBUG)
328 node->left = NULL;
329 node->right = NULL;
330 node->parent = NULL;
331 #endif
332
333 if (color == NXT_RBTREE_BLACK) {
334 nxt_rbtree_delete_fixup(tree, child);
335 }
336 }
337
338
339 static void
nxt_rbtree_delete_fixup(nxt_rbtree_t * tree,nxt_rbtree_node_t * node)340 nxt_rbtree_delete_fixup(nxt_rbtree_t *tree, nxt_rbtree_node_t *node)
341 {
342 nxt_rbtree_node_t *parent, *sibling;
343
344 while (node != nxt_rbtree_root(tree) && node->color == NXT_RBTREE_BLACK) {
345 /*
346 * Prefetching parent nodes does not help here according
347 * to microbenchmarks.
348 */
349
350 parent = node->parent;
351
352 if (node == parent->left) {
353 sibling = parent->right;
354
355 if (sibling->color != NXT_RBTREE_BLACK) {
356
357 sibling->color = NXT_RBTREE_BLACK;
358 parent->color = NXT_RBTREE_RED;
359
360 nxt_rbtree_left_rotate(parent);
361
362 sibling = parent->right;
363 }
364
365 if (sibling->right->color == NXT_RBTREE_BLACK) {
366
367 sibling->color = NXT_RBTREE_RED;
368
369 if (sibling->left->color == NXT_RBTREE_BLACK) {
370 node = parent;
371 continue;
372 }
373
374 sibling->left->color = NXT_RBTREE_BLACK;
375
376 nxt_rbtree_right_rotate(sibling);
377 /*
378 * If the node is the leaf sentinel then the right
379 * rotate above changes its parent so a sibling below
380 * becames the leaf sentinel as well and this causes
381 * segmentation fault. This is the reason why usual
382 * red-black tree implementations with a leaf sentinel
383 * which does not require to test leaf nodes at all
384 * nevertheless test the leaf sentinel in the left and
385 * right rotate procedures. Since according to the
386 * algorithm node->parent must not be changed by both
387 * the left and right rotates above, it can be cached
388 * in a local variable. This not only eliminates the
389 * sentinel test in nxt_rbtree_parent_relink() but also
390 * decreases the code size because C forces to reload
391 * non-restrict pointers.
392 */
393 sibling = parent->right;
394 }
395
396 sibling->color = parent->color;
397 parent->color = NXT_RBTREE_BLACK;
398 sibling->right->color = NXT_RBTREE_BLACK;
399
400 nxt_rbtree_left_rotate(parent);
401
402 return;
403
404 } else {
405 sibling = parent->left;
406
407 if (sibling->color != NXT_RBTREE_BLACK) {
408
409 sibling->color = NXT_RBTREE_BLACK;
410 parent->color = NXT_RBTREE_RED;
411
412 nxt_rbtree_right_rotate(parent);
413
414 sibling = parent->left;
415 }
416
417 if (sibling->left->color == NXT_RBTREE_BLACK) {
418
419 sibling->color = NXT_RBTREE_RED;
420
421 if (sibling->right->color == NXT_RBTREE_BLACK) {
422 node = parent;
423 continue;
424 }
425
426 sibling->right->color = NXT_RBTREE_BLACK;
427
428 nxt_rbtree_left_rotate(sibling);
429
430 /* See the comment in the symmetric branch above. */
431 sibling = parent->left;
432 }
433
434 sibling->color = parent->color;
435 parent->color = NXT_RBTREE_BLACK;
436 sibling->left->color = NXT_RBTREE_BLACK;
437
438 nxt_rbtree_right_rotate(parent);
439
440 return;
441 }
442 }
443
444 node->color = NXT_RBTREE_BLACK;
445 }
446
447
448 nxt_inline void
nxt_rbtree_left_rotate(nxt_rbtree_node_t * node)449 nxt_rbtree_left_rotate(nxt_rbtree_node_t *node)
450 {
451 nxt_rbtree_node_t *child;
452
453 child = node->right;
454 node->right = child->left;
455 child->left->parent = node;
456 child->left = node;
457
458 nxt_rbtree_parent_relink(child, node);
459
460 node->parent = child;
461 }
462
463
464 nxt_inline void
nxt_rbtree_right_rotate(nxt_rbtree_node_t * node)465 nxt_rbtree_right_rotate(nxt_rbtree_node_t *node)
466 {
467 nxt_rbtree_node_t *child;
468
469 child = node->left;
470 node->left = child->right;
471 child->right->parent = node;
472 child->right = node;
473
474 nxt_rbtree_parent_relink(child, node);
475
476 node->parent = child;
477 }
478
479
480 /* Relink a parent from the node to the subst node. */
481
482 nxt_inline void
nxt_rbtree_parent_relink(nxt_rbtree_node_t * subst,nxt_rbtree_node_t * node)483 nxt_rbtree_parent_relink(nxt_rbtree_node_t *subst, nxt_rbtree_node_t *node)
484 {
485 nxt_rbtree_node_t *parent, **link;
486
487 parent = node->parent;
488 /*
489 * The leaf sentinel's parent can be safely changed here.
490 * See the comment in nxt_rbtree_delete_fixup() for details.
491 */
492 subst->parent = parent;
493 /*
494 * If the node's parent is the root sentinel it is safely changed
495 * because the root sentinel's left child is the tree root.
496 */
497 link = (node == parent->left) ? &parent->left : &parent->right;
498 *link = subst;
499 }
500
501
502 nxt_rbtree_node_t *
nxt_rbtree_destroy_next(nxt_rbtree_t * tree,nxt_rbtree_node_t ** next)503 nxt_rbtree_destroy_next(nxt_rbtree_t *tree, nxt_rbtree_node_t **next)
504 {
505 nxt_rbtree_node_t *node, *subst, *parent, *sentinel;
506
507 sentinel = nxt_rbtree_sentinel(tree);
508
509 /* Find the leftmost node. */
510 for (node = *next; node->left != sentinel; node = node->left);
511
512 /* Replace the leftmost node with its right child. */
513 subst = node->right;
514 parent = node->parent;
515
516 parent->left = subst;
517 subst->parent = parent;
518
519 /*
520 * The right child is used as the next start node. If the right child
521 * is the sentinel then parent of the leftmost node is used as the next
522 * start node. The parent of the root node is the sentinel so after
523 * the single root node will be replaced with the sentinel, the next
524 * start node will be equal to the sentinel and iteration will stop.
525 */
526 if (subst == sentinel) {
527 subst = parent;
528 }
529
530 *next = subst;
531
532 return node;
533 }
534