3 * Copyright (C) Igor Sysoev
7 #include <ngx_config.h>
12 * The red-black tree code is based on the algorithm described in
13 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
17 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
18 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
19 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
20 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
24 ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
25 ngx_rbtree_node_t *node)
27 ngx_rbtree_node_t **root, *temp, *sentinel;
29 /* a binary tree insert */
31 root = (ngx_rbtree_node_t **) &tree->root;
32 sentinel = tree->sentinel;
34 if (*root == sentinel) {
36 node->left = sentinel;
37 node->right = sentinel;
44 tree->insert(*root, node, sentinel);
48 while (node != *root && ngx_rbt_is_red(node->parent)) {
50 if (node->parent == node->parent->parent->left) {
51 temp = node->parent->parent->right;
53 if (ngx_rbt_is_red(temp)) {
54 ngx_rbt_black(node->parent);
56 ngx_rbt_red(node->parent->parent);
57 node = node->parent->parent;
60 if (node == node->parent->right) {
62 ngx_rbtree_left_rotate(root, sentinel, node);
65 ngx_rbt_black(node->parent);
66 ngx_rbt_red(node->parent->parent);
67 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
71 temp = node->parent->parent->left;
73 if (ngx_rbt_is_red(temp)) {
74 ngx_rbt_black(node->parent);
76 ngx_rbt_red(node->parent->parent);
77 node = node->parent->parent;
80 if (node == node->parent->left) {
82 ngx_rbtree_right_rotate(root, sentinel, node);
85 ngx_rbt_black(node->parent);
86 ngx_rbt_red(node->parent->parent);
87 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
97 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
98 ngx_rbtree_node_t *sentinel)
100 ngx_rbtree_node_t **p;
104 p = (node->key < temp->key) ? &temp->left : &temp->right;
106 if (*p == sentinel) {
115 node->left = sentinel;
116 node->right = sentinel;
122 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
123 ngx_rbtree_node_t *sentinel)
125 ngx_rbtree_node_t **p;
131 * 1) are spread in small range, usually several minutes,
132 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
133 * The comparison takes into account that overflow.
136 /* node->key < temp->key */
138 p = ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key
140 ? &temp->left : &temp->right;
142 if (*p == sentinel) {
151 node->left = sentinel;
152 node->right = sentinel;
158 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree,
159 ngx_rbtree_node_t *node)
162 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;
164 /* a binary tree delete */
166 root = (ngx_rbtree_node_t **) &tree->root;
167 sentinel = tree->sentinel;
169 if (node->left == sentinel) {
173 } else if (node->right == sentinel) {
178 subst = ngx_rbtree_min(node->right, sentinel);
180 if (subst->left != sentinel) {
187 if (subst == *root) {
200 red = ngx_rbt_is_red(subst);
202 if (subst == subst->parent->left) {
203 subst->parent->left = temp;
206 subst->parent->right = temp;
211 temp->parent = subst->parent;
215 if (subst->parent == node) {
216 temp->parent = subst;
219 temp->parent = subst->parent;
222 subst->left = node->left;
223 subst->right = node->right;
224 subst->parent = node->parent;
225 ngx_rbt_copy_color(subst, node);
231 if (node == node->parent->left) {
232 node->parent->left = subst;
234 node->parent->right = subst;
238 if (subst->left != sentinel) {
239 subst->left->parent = subst;
242 if (subst->right != sentinel) {
243 subst->right->parent = subst;
259 while (temp != *root && ngx_rbt_is_black(temp)) {
261 if (temp == temp->parent->left) {
262 w = temp->parent->right;
264 if (ngx_rbt_is_red(w)) {
266 ngx_rbt_red(temp->parent);
267 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
268 w = temp->parent->right;
271 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
276 if (ngx_rbt_is_black(w->right)) {
277 ngx_rbt_black(w->left);
279 ngx_rbtree_right_rotate(root, sentinel, w);
280 w = temp->parent->right;
283 ngx_rbt_copy_color(w, temp->parent);
284 ngx_rbt_black(temp->parent);
285 ngx_rbt_black(w->right);
286 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
291 w = temp->parent->left;
293 if (ngx_rbt_is_red(w)) {
295 ngx_rbt_red(temp->parent);
296 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
297 w = temp->parent->left;
300 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
305 if (ngx_rbt_is_black(w->left)) {
306 ngx_rbt_black(w->right);
308 ngx_rbtree_left_rotate(root, sentinel, w);
309 w = temp->parent->left;
312 ngx_rbt_copy_color(w, temp->parent);
313 ngx_rbt_black(temp->parent);
314 ngx_rbt_black(w->left);
315 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
325 static ngx_inline void
326 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
327 ngx_rbtree_node_t *node)
329 ngx_rbtree_node_t *temp;
332 node->right = temp->left;
334 if (temp->left != sentinel) {
335 temp->left->parent = node;
338 temp->parent = node->parent;
343 } else if (node == node->parent->left) {
344 node->parent->left = temp;
347 node->parent->right = temp;
355 static ngx_inline void
356 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
357 ngx_rbtree_node_t *node)
359 ngx_rbtree_node_t *temp;
362 node->left = temp->right;
364 if (temp->right != sentinel) {
365 temp->right->parent = node;
368 temp->parent = node->parent;
373 } else if (node == node->parent->right) {
374 node->parent->right = temp;
377 node->parent->left = temp;