1e18a033bSKonstantin Ananyev
2e18a033bSKonstantin Ananyev/*
3e18a033bSKonstantin Ananyev * Copyright (C) Igor Sysoev
4e18a033bSKonstantin Ananyev * Copyright (C) Nginx, Inc.
5e18a033bSKonstantin Ananyev */
6e18a033bSKonstantin Ananyev
7e18a033bSKonstantin Ananyev
8e18a033bSKonstantin Ananyev#include <ngx_config.h>
9e18a033bSKonstantin Ananyev#include <ngx_core.h>
10e18a033bSKonstantin Ananyev
11e18a033bSKonstantin Ananyev
12e18a033bSKonstantin Ananyev/*
13e18a033bSKonstantin Ananyev * The red-black tree code is based on the algorithm described in
14e18a033bSKonstantin Ananyev * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
15e18a033bSKonstantin Ananyev */
16e18a033bSKonstantin Ananyev
17e18a033bSKonstantin Ananyev
18e18a033bSKonstantin Ananyevstatic ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
19e18a033bSKonstantin Ananyev    ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
20e18a033bSKonstantin Ananyevstatic ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
21e18a033bSKonstantin Ananyev    ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
22e18a033bSKonstantin Ananyev
23e18a033bSKonstantin Ananyev
24e18a033bSKonstantin Ananyevvoid
25e18a033bSKonstantin Ananyevngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
26e18a033bSKonstantin Ananyev{
27e18a033bSKonstantin Ananyev    ngx_rbtree_node_t  **root, *temp, *sentinel;
28e18a033bSKonstantin Ananyev
29e18a033bSKonstantin Ananyev    /* a binary tree insert */
30e18a033bSKonstantin Ananyev
31e18a033bSKonstantin Ananyev    root = &tree->root;
32e18a033bSKonstantin Ananyev    sentinel = tree->sentinel;
33e18a033bSKonstantin Ananyev
34e18a033bSKonstantin Ananyev    if (*root == sentinel) {
35e18a033bSKonstantin Ananyev        node->parent = NULL;
36e18a033bSKonstantin Ananyev        node->left = sentinel;
37e18a033bSKonstantin Ananyev        node->right = sentinel;
38e18a033bSKonstantin Ananyev        ngx_rbt_black(node);
39e18a033bSKonstantin Ananyev        *root = node;
40e18a033bSKonstantin Ananyev
41e18a033bSKonstantin Ananyev        return;
42e18a033bSKonstantin Ananyev    }
43e18a033bSKonstantin Ananyev
44e18a033bSKonstantin Ananyev    tree->insert(*root, node, sentinel);
45e18a033bSKonstantin Ananyev
46e18a033bSKonstantin Ananyev    /* re-balance tree */
47e18a033bSKonstantin Ananyev
48e18a033bSKonstantin Ananyev    while (node != *root && ngx_rbt_is_red(node->parent)) {
49e18a033bSKonstantin Ananyev
50e18a033bSKonstantin Ananyev        if (node->parent == node->parent->parent->left) {
51e18a033bSKonstantin Ananyev            temp = node->parent->parent->right;
52e18a033bSKonstantin Ananyev
53e18a033bSKonstantin Ananyev            if (ngx_rbt_is_red(temp)) {
54e18a033bSKonstantin Ananyev                ngx_rbt_black(node->parent);
55e18a033bSKonstantin Ananyev                ngx_rbt_black(temp);
56e18a033bSKonstantin Ananyev                ngx_rbt_red(node->parent->parent);
57e18a033bSKonstantin Ananyev                node = node->parent->parent;
58e18a033bSKonstantin Ananyev
59e18a033bSKonstantin Ananyev            } else {
60e18a033bSKonstantin Ananyev                if (node == node->parent->right) {
61e18a033bSKonstantin Ananyev                    node = node->parent;
62e18a033bSKonstantin Ananyev                    ngx_rbtree_left_rotate(root, sentinel, node);
63e18a033bSKonstantin Ananyev                }
64e18a033bSKonstantin Ananyev
65e18a033bSKonstantin Ananyev                ngx_rbt_black(node->parent);
66e18a033bSKonstantin Ananyev                ngx_rbt_red(node->parent->parent);
67e18a033bSKonstantin Ananyev                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
68e18a033bSKonstantin Ananyev            }
69e18a033bSKonstantin Ananyev
70e18a033bSKonstantin Ananyev        } else {
71e18a033bSKonstantin Ananyev            temp = node->parent->parent->left;
72e18a033bSKonstantin Ananyev
73e18a033bSKonstantin Ananyev            if (ngx_rbt_is_red(temp)) {
74e18a033bSKonstantin Ananyev                ngx_rbt_black(node->parent);
75e18a033bSKonstantin Ananyev                ngx_rbt_black(temp);
76e18a033bSKonstantin Ananyev                ngx_rbt_red(node->parent->parent);
77e18a033bSKonstantin Ananyev                node = node->parent->parent;
78e18a033bSKonstantin Ananyev
79e18a033bSKonstantin Ananyev            } else {
80e18a033bSKonstantin Ananyev                if (node == node->parent->left) {
81e18a033bSKonstantin Ananyev                    node = node->parent;
82e18a033bSKonstantin Ananyev                    ngx_rbtree_right_rotate(root, sentinel, node);
83e18a033bSKonstantin Ananyev                }
84e18a033bSKonstantin Ananyev
85e18a033bSKonstantin Ananyev                ngx_rbt_black(node->parent);
86e18a033bSKonstantin Ananyev                ngx_rbt_red(node->parent->parent);
87e18a033bSKonstantin Ananyev                ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
88e18a033bSKonstantin Ananyev            }
89e18a033bSKonstantin Ananyev        }
90e18a033bSKonstantin Ananyev    }
91e18a033bSKonstantin Ananyev
92e18a033bSKonstantin Ananyev    ngx_rbt_black(*root);
93e18a033bSKonstantin Ananyev}
94e18a033bSKonstantin Ananyev
95e18a033bSKonstantin Ananyev
96e18a033bSKonstantin Ananyevvoid
97e18a033bSKonstantin Ananyevngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
98e18a033bSKonstantin Ananyev    ngx_rbtree_node_t *sentinel)
99e18a033bSKonstantin Ananyev{
100e18a033bSKonstantin Ananyev    ngx_rbtree_node_t  **p;
101e18a033bSKonstantin Ananyev
102e18a033bSKonstantin Ananyev    for ( ;; ) {
103e18a033bSKonstantin Ananyev
104e18a033bSKonstantin Ananyev        p = (node->key < temp->key) ? &temp->left : &temp->right;
105e18a033bSKonstantin Ananyev
106e18a033bSKonstantin Ananyev        if (*p == sentinel) {
107e18a033bSKonstantin Ananyev            break;
108e18a033bSKonstantin Ananyev        }
109e18a033bSKonstantin Ananyev
110e18a033bSKonstantin Ananyev        temp = *p;
111e18a033bSKonstantin Ananyev    }
112e18a033bSKonstantin Ananyev
113e18a033bSKonstantin Ananyev    *p = node;
114e18a033bSKonstantin Ananyev    node->parent = temp;
115e18a033bSKonstantin Ananyev    node->left = sentinel;
116e18a033bSKonstantin Ananyev    node->right = sentinel;
117e18a033bSKonstantin Ananyev    ngx_rbt_red(node);
118e18a033bSKonstantin Ananyev}
119e18a033bSKonstantin Ananyev
120e18a033bSKonstantin Ananyev
121e18a033bSKonstantin Ananyevvoid
122e18a033bSKonstantin Ananyevngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
123e18a033bSKonstantin Ananyev    ngx_rbtree_node_t *sentinel)
124e18a033bSKonstantin Ananyev{
125e18a033bSKonstantin Ananyev    ngx_rbtree_node_t  **p;
126e18a033bSKonstantin Ananyev
127e18a033bSKonstantin Ananyev    for ( ;; ) {
128e18a033bSKonstantin Ananyev
129e18a033bSKonstantin Ananyev        /*
130e18a033bSKonstantin Ananyev         * Timer values
131e18a033bSKonstantin Ananyev         * 1) are spread in small range, usually several minutes,
132e18a033bSKonstantin Ananyev         * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
133e18a033bSKonstantin Ananyev         * The comparison takes into account that overflow.
134e18a033bSKonstantin Ananyev         */
135e18a033bSKonstantin Ananyev
136e18a033bSKonstantin Ananyev        /*  node->key < temp->key */
137e18a033bSKonstantin Ananyev
138e18a033bSKonstantin Ananyev        p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
139e18a033bSKonstantin Ananyev            ? &temp->left : &temp->right;
140e18a033bSKonstantin Ananyev
141e18a033bSKonstantin Ananyev        if (*p == sentinel) {
142e18a033bSKonstantin Ananyev            break;
143e18a033bSKonstantin Ananyev        }
144e18a033bSKonstantin Ananyev
145e18a033bSKonstantin Ananyev        temp = *p;
146e18a033bSKonstantin Ananyev    }
147e18a033bSKonstantin Ananyev
148e18a033bSKonstantin Ananyev    *p = node;
149e18a033bSKonstantin Ananyev    node->parent = temp;
150e18a033bSKonstantin Ananyev    node->left = sentinel;
151e18a033bSKonstantin Ananyev    node->right = sentinel;
152e18a033bSKonstantin Ananyev    ngx_rbt_red(node);
153e18a033bSKonstantin Ananyev}
154e18a033bSKonstantin Ananyev
155e18a033bSKonstantin Ananyev
156e18a033bSKonstantin Ananyevvoid
157e18a033bSKonstantin Ananyevngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
158e18a033bSKonstantin Ananyev{
159e18a033bSKonstantin Ananyev    ngx_uint_t           red;
160e18a033bSKonstantin Ananyev    ngx_rbtree_node_t  **root, *sentinel, *subst, *temp, *w;
161e18a033bSKonstantin Ananyev
162e18a033bSKonstantin Ananyev    /* a binary tree delete */
163e18a033bSKonstantin Ananyev
164e18a033bSKonstantin Ananyev    root = &tree->root;
165e18a033bSKonstantin Ananyev    sentinel = tree->sentinel;
166e18a033bSKonstantin Ananyev
167e18a033bSKonstantin Ananyev    if (node->left == sentinel) {
168e18a033bSKonstantin Ananyev        temp = node->right;
169e18a033bSKonstantin Ananyev        subst = node;
170e18a033bSKonstantin Ananyev
171e18a033bSKonstantin Ananyev    } else if (node->right == sentinel) {
172e18a033bSKonstantin Ananyev        temp = node->left;
173e18a033bSKonstantin Ananyev        subst = node;
174e18a033bSKonstantin Ananyev
175e18a033bSKonstantin Ananyev    } else {
176e18a033bSKonstantin Ananyev        subst = ngx_rbtree_min(node->right, sentinel);
177e18a033bSKonstantin Ananyev
178e18a033bSKonstantin Ananyev        if (subst->left != sentinel) {
179e18a033bSKonstantin Ananyev            temp = subst->left;
180e18a033bSKonstantin Ananyev        } else {
181e18a033bSKonstantin Ananyev            temp = subst->right;
182e18a033bSKonstantin Ananyev        }
183e18a033bSKonstantin Ananyev    }
184e18a033bSKonstantin Ananyev
185e18a033bSKonstantin Ananyev    if (subst == *root) {
186e18a033bSKonstantin Ananyev        *root = temp;
187e18a033bSKonstantin Ananyev        ngx_rbt_black(temp);
188e18a033bSKonstantin Ananyev
189e18a033bSKonstantin Ananyev        /* DEBUG stuff */
190e18a033bSKonstantin Ananyev        node->left = NULL;
191e18a033bSKonstantin Ananyev        node->right = NULL;
192e18a033bSKonstantin Ananyev        node->parent = NULL;
193e18a033bSKonstantin Ananyev        node->key = 0;
194e18a033bSKonstantin Ananyev
195e18a033bSKonstantin Ananyev        return;
196e18a033bSKonstantin Ananyev    }
197e18a033bSKonstantin Ananyev
198e18a033bSKonstantin Ananyev    red = ngx_rbt_is_red(subst);
199e18a033bSKonstantin Ananyev
200e18a033bSKonstantin Ananyev    if (subst == subst->parent->left) {
201e18a033bSKonstantin Ananyev        subst->parent->left = temp;
202e18a033bSKonstantin Ananyev
203e18a033bSKonstantin Ananyev    } else {
204e18a033bSKonstantin Ananyev        subst->parent->right = temp;
205e18a033bSKonstantin Ananyev    }
206e18a033bSKonstantin Ananyev
207e18a033bSKonstantin Ananyev    if (subst == node) {
208e18a033bSKonstantin Ananyev
209e18a033bSKonstantin Ananyev        temp->parent = subst->parent;
210e18a033bSKonstantin Ananyev
211e18a033bSKonstantin Ananyev    } else {
212e18a033bSKonstantin Ananyev
213e18a033bSKonstantin Ananyev        if (subst->parent == node) {
214e18a033bSKonstantin Ananyev            temp->parent = subst;
215e18a033bSKonstantin Ananyev
216e18a033bSKonstantin Ananyev        } else {
217e18a033bSKonstantin Ananyev            temp->parent = subst->parent;
218e18a033bSKonstantin Ananyev        }
219e18a033bSKonstantin Ananyev
220e18a033bSKonstantin Ananyev        subst->left = node->left;
221e18a033bSKonstantin Ananyev        subst->right = node->right;
222e18a033bSKonstantin Ananyev        subst->parent = node->parent;
223e18a033bSKonstantin Ananyev        ngx_rbt_copy_color(subst, node);
224e18a033bSKonstantin Ananyev
225e18a033bSKonstantin Ananyev        if (node == *root) {
226e18a033bSKonstantin Ananyev            *root = subst;
227e18a033bSKonstantin Ananyev
228e18a033bSKonstantin Ananyev        } else {
229e18a033bSKonstantin Ananyev            if (node == node->parent->left) {
230e18a033bSKonstantin Ananyev                node->parent->left = subst;
231e18a033bSKonstantin Ananyev            } else {
232e18a033bSKonstantin Ananyev                node->parent->right = subst;
233e18a033bSKonstantin Ananyev            }
234e18a033bSKonstantin Ananyev        }
235e18a033bSKonstantin Ananyev
236e18a033bSKonstantin Ananyev        if (subst->left != sentinel) {
237e18a033bSKonstantin Ananyev            subst->left->parent = subst;
238e18a033bSKonstantin Ananyev        }
239e18a033bSKonstantin Ananyev
240e18a033bSKonstantin Ananyev        if (subst->right != sentinel) {
241e18a033bSKonstantin Ananyev            subst->right->parent = subst;
242e18a033bSKonstantin Ananyev        }
243e18a033bSKonstantin Ananyev    }
244e18a033bSKonstantin Ananyev
245e18a033bSKonstantin Ananyev    /* DEBUG stuff */
246e18a033bSKonstantin Ananyev    node->left = NULL;
247e18a033bSKonstantin Ananyev    node->right = NULL;
248e18a033bSKonstantin Ananyev    node->parent = NULL;
249e18a033bSKonstantin Ananyev    node->key = 0;
250e18a033bSKonstantin Ananyev
251e18a033bSKonstantin Ananyev    if (red) {
252e18a033bSKonstantin Ananyev        return;
253e18a033bSKonstantin Ananyev    }
254e18a033bSKonstantin Ananyev
255e18a033bSKonstantin Ananyev    /* a delete fixup */
256e18a033bSKonstantin Ananyev
257e18a033bSKonstantin Ananyev    while (temp != *root && ngx_rbt_is_black(temp)) {
258e18a033bSKonstantin Ananyev
259e18a033bSKonstantin Ananyev        if (temp == temp->parent->left) {
260e18a033bSKonstantin Ananyev            w = temp->parent->right;
261e18a033bSKonstantin Ananyev
262e18a033bSKonstantin Ananyev            if (ngx_rbt_is_red(w)) {
263e18a033bSKonstantin Ananyev                ngx_rbt_black(w);
264e18a033bSKonstantin Ananyev                ngx_rbt_red(temp->parent);
265e18a033bSKonstantin Ananyev                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
266e18a033bSKonstantin Ananyev                w = temp->parent->right;
267e18a033bSKonstantin Ananyev            }
268e18a033bSKonstantin Ananyev
269e18a033bSKonstantin Ananyev            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
270e18a033bSKonstantin Ananyev                ngx_rbt_red(w);
271e18a033bSKonstantin Ananyev                temp = temp->parent;
272e18a033bSKonstantin Ananyev
273e18a033bSKonstantin Ananyev            } else {
274e18a033bSKonstantin Ananyev                if (ngx_rbt_is_black(w->right)) {
275e18a033bSKonstantin Ananyev                    ngx_rbt_black(w->left);
276e18a033bSKonstantin Ananyev                    ngx_rbt_red(w);
277e18a033bSKonstantin Ananyev                    ngx_rbtree_right_rotate(root, sentinel, w);
278e18a033bSKonstantin Ananyev                    w = temp->parent->right;
279e18a033bSKonstantin Ananyev                }
280e18a033bSKonstantin Ananyev
281e18a033bSKonstantin Ananyev                ngx_rbt_copy_color(w, temp->parent);
282e18a033bSKonstantin Ananyev                ngx_rbt_black(temp->parent);
283e18a033bSKonstantin Ananyev                ngx_rbt_black(w->right);
284e18a033bSKonstantin Ananyev                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
285e18a033bSKonstantin Ananyev                temp = *root;
286e18a033bSKonstantin Ananyev            }
287e18a033bSKonstantin Ananyev
288e18a033bSKonstantin Ananyev        } else {
289e18a033bSKonstantin Ananyev            w = temp->parent->left;
290e18a033bSKonstantin Ananyev
291e18a033bSKonstantin Ananyev            if (ngx_rbt_is_red(w)) {
292e18a033bSKonstantin Ananyev                ngx_rbt_black(w);
293e18a033bSKonstantin Ananyev                ngx_rbt_red(temp->parent);
294e18a033bSKonstantin Ananyev                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
295e18a033bSKonstantin Ananyev                w = temp->parent->left;
296e18a033bSKonstantin Ananyev            }
297e18a033bSKonstantin Ananyev
298e18a033bSKonstantin Ananyev            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
299e18a033bSKonstantin Ananyev                ngx_rbt_red(w);
300e18a033bSKonstantin Ananyev                temp = temp->parent;
301e18a033bSKonstantin Ananyev
302e18a033bSKonstantin Ananyev            } else {
303e18a033bSKonstantin Ananyev                if (ngx_rbt_is_black(w->left)) {
304e18a033bSKonstantin Ananyev                    ngx_rbt_black(w->right);
305e18a033bSKonstantin Ananyev                    ngx_rbt_red(w);
306e18a033bSKonstantin Ananyev                    ngx_rbtree_left_rotate(root, sentinel, w);
307e18a033bSKonstantin Ananyev                    w = temp->parent->left;
308e18a033bSKonstantin Ananyev                }
309e18a033bSKonstantin Ananyev
310e18a033bSKonstantin Ananyev                ngx_rbt_copy_color(w, temp->parent);
311e18a033bSKonstantin Ananyev                ngx_rbt_black(temp->parent);
312e18a033bSKonstantin Ananyev                ngx_rbt_black(w->left);
313e18a033bSKonstantin Ananyev                ngx_rbtree_right_rotate(root, sentinel, temp->parent);
314e18a033bSKonstantin Ananyev                temp = *root;
315e18a033bSKonstantin Ananyev            }
316e18a033bSKonstantin Ananyev        }
317e18a033bSKonstantin Ananyev    }
318e18a033bSKonstantin Ananyev
319e18a033bSKonstantin Ananyev    ngx_rbt_black(temp);
320e18a033bSKonstantin Ananyev}
321e18a033bSKonstantin Ananyev
322e18a033bSKonstantin Ananyev
323e18a033bSKonstantin Ananyevstatic ngx_inline void
324e18a033bSKonstantin Ananyevngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
325e18a033bSKonstantin Ananyev    ngx_rbtree_node_t *node)
326e18a033bSKonstantin Ananyev{
327e18a033bSKonstantin Ananyev    ngx_rbtree_node_t  *temp;
328e18a033bSKonstantin Ananyev
329e18a033bSKonstantin Ananyev    temp = node->right;
330e18a033bSKonstantin Ananyev    node->right = temp->left;
331e18a033bSKonstantin Ananyev
332e18a033bSKonstantin Ananyev    if (temp->left != sentinel) {
333e18a033bSKonstantin Ananyev        temp->left->parent = node;
334e18a033bSKonstantin Ananyev    }
335e18a033bSKonstantin Ananyev
336e18a033bSKonstantin Ananyev    temp->parent = node->parent;
337e18a033bSKonstantin Ananyev
338e18a033bSKonstantin Ananyev    if (node == *root) {
339e18a033bSKonstantin Ananyev        *root = temp;
340e18a033bSKonstantin Ananyev
341e18a033bSKonstantin Ananyev    } else if (node == node->parent->left) {
342e18a033bSKonstantin Ananyev        node->parent->left = temp;
343e18a033bSKonstantin Ananyev
344e18a033bSKonstantin Ananyev    } else {
345e18a033bSKonstantin Ananyev        node->parent->right = temp;
346e18a033bSKonstantin Ananyev    }
347e18a033bSKonstantin Ananyev
348e18a033bSKonstantin Ananyev    temp->left = node;
349e18a033bSKonstantin Ananyev    node->parent = temp;
350e18a033bSKonstantin Ananyev}
351e18a033bSKonstantin Ananyev
352e18a033bSKonstantin Ananyev
353e18a033bSKonstantin Ananyevstatic ngx_inline void
354e18a033bSKonstantin Ananyevngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
355e18a033bSKonstantin Ananyev    ngx_rbtree_node_t *node)
356e18a033bSKonstantin Ananyev{
357e18a033bSKonstantin Ananyev    ngx_rbtree_node_t  *temp;
358e18a033bSKonstantin Ananyev
359e18a033bSKonstantin Ananyev    temp = node->left;
360e18a033bSKonstantin Ananyev    node->left = temp->right;
361e18a033bSKonstantin Ananyev
362e18a033bSKonstantin Ananyev    if (temp->right != sentinel) {
363e18a033bSKonstantin Ananyev        temp->right->parent = node;
364e18a033bSKonstantin Ananyev    }
365e18a033bSKonstantin Ananyev
366e18a033bSKonstantin Ananyev    temp->parent = node->parent;
367e18a033bSKonstantin Ananyev
368e18a033bSKonstantin Ananyev    if (node == *root) {
369e18a033bSKonstantin Ananyev        *root = temp;
370e18a033bSKonstantin Ananyev
371e18a033bSKonstantin Ananyev    } else if (node == node->parent->right) {
372e18a033bSKonstantin Ananyev        node->parent->right = temp;
373e18a033bSKonstantin Ananyev
374e18a033bSKonstantin Ananyev    } else {
375e18a033bSKonstantin Ananyev        node->parent->left = temp;
376e18a033bSKonstantin Ananyev    }
377e18a033bSKonstantin Ananyev
378e18a033bSKonstantin Ananyev    temp->right = node;
379e18a033bSKonstantin Ananyev    node->parent = temp;
380e18a033bSKonstantin Ananyev}
381e18a033bSKonstantin Ananyev
382e18a033bSKonstantin Ananyev
383e18a033bSKonstantin Ananyevngx_rbtree_node_t *
384e18a033bSKonstantin Ananyevngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
385e18a033bSKonstantin Ananyev{
386e18a033bSKonstantin Ananyev    ngx_rbtree_node_t  *root, *sentinel, *parent;
387e18a033bSKonstantin Ananyev
388e18a033bSKonstantin Ananyev    sentinel = tree->sentinel;
389e18a033bSKonstantin Ananyev
390e18a033bSKonstantin Ananyev    if (node->right != sentinel) {
391e18a033bSKonstantin Ananyev        return ngx_rbtree_min(node->right, sentinel);
392e18a033bSKonstantin Ananyev    }
393e18a033bSKonstantin Ananyev
394e18a033bSKonstantin Ananyev    root = tree->root;
395e18a033bSKonstantin Ananyev
396e18a033bSKonstantin Ananyev    for ( ;; ) {
397e18a033bSKonstantin Ananyev        parent = node->parent;
398e18a033bSKonstantin Ananyev
399e18a033bSKonstantin Ananyev        if (node == root) {
400e18a033bSKonstantin Ananyev            return NULL;
401e18a033bSKonstantin Ananyev        }
402e18a033bSKonstantin Ananyev
403e18a033bSKonstantin Ananyev        if (node == parent->left) {
404e18a033bSKonstantin Ananyev            return parent;
405e18a033bSKonstantin Ananyev        }
406e18a033bSKonstantin Ananyev
407e18a033bSKonstantin Ananyev        node = parent;
408e18a033bSKonstantin Ananyev    }
409e18a033bSKonstantin Ananyev}
410