Mercurial > hg > nginx

annotate src/core/ngx_rbtree.c @ 7360:8f25a44d9add

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
SSL: logging level of "no suitable key share". The "no suitable key share" errors are reported by OpenSSL 1.1.1 when using TLSv1.3 if there are no shared groups (that is, elliptic curves). In particular, it is easy enough to trigger by using only a single curve in ssl_ecdh_curve: ssl_ecdh_curve secp384r1; and using a different curve in the client: openssl s_client -connect 127.0.0.1:443 -curves prime256v1 On the client side it is seen as "sslv3 alert handshake failure", "SSL alert number 40": 0:error:14094410:SSL routines:ssl3_read_bytes:sslv3 alert handshake failure:ssl/record/rec_layer_s3.c:1528:SSL alert number 40 It can be also triggered with default ssl_ecdh_curve by using a curve which is not in the default list (X25519, prime256v1, X448, secp521r1, secp384r1): openssl s_client -connect 127.0.0.1:8443 -curves brainpoolP512r1 Given that many clients hardcode prime256v1, these errors might become a common problem with TLSv1.3 if ssl_ecdh_curve is redefined. Previously this resulted in not using ECDH with such clients, but with TLSv1.3 it is no longer possible and will result in a handshake failure. The SSL_R_NO_SHARED_GROUP error is what BoringSSL returns in the same situation. Seen at: https://serverfault.com/questions/932102/nginx-ssl-handshake-error-no-suitable-key-share
author Maxim Dounin <mdounin@mdounin.ru>
date Tue, 25 Sep 2018 13:59:53 +0300
parents e0cc454aafe4
children 7fdcf308e0f0
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
441
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 229
diff changeset
1
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 229
diff changeset
2 /*
444
42d11f017717 nginx-0.1.0-2004-09-29-20:00:49 import; remove years from copyright
Igor Sysoev <igor@sysoev.ru>
parents: 441
diff changeset
3 * Copyright (C) Igor Sysoev
4412
d620f497c50f Copyright updated.
Maxim Konovalov <maxim@nginx.com>
parents: 1764
diff changeset
4 * Copyright (C) Nginx, Inc.
441
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 229
diff changeset
5 */
da8c5707af39 nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents: 229
diff changeset
6
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
7
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
8 #include <ngx_config.h>
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
9 #include <ngx_core.h>
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
10
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
11
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
12 /*
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
13 * The red-black tree code is based on the algorithm described in
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
14 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
15 */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
16
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
17
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
18 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
19 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
20 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
21 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
22
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
23
493
975f62e77f02 nginx-0.1.21-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 467
diff changeset
24 void
5894
1f513d7f1b45 Events: removed broken thread support from event timers.
Valentin Bartenev <vbart@nginx.com>
parents: 4576
diff changeset
25 ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
26 {
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
27 ngx_rbtree_node_t **root, *temp, *sentinel;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
28
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
29 /* a binary tree insert */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
30
6925
b3c5b4312667 Removed casts not needed after 1f513d7f1b45.
Ruslan Ermilov <ru@nginx.com>
parents: 5894
diff changeset
31 root = &tree->root;
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
32 sentinel = tree->sentinel;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
33
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
34 if (*root == sentinel) {
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
35 node->parent = NULL;
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
36 node->left = sentinel;
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
37 node->right = sentinel;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
38 ngx_rbt_black(node);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
39 *root = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
40
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
41 return;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
42 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
43
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
44 tree->insert(*root, node, sentinel);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
45
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
46 /* re-balance tree */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
47
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
48 while (node != *root && ngx_rbt_is_red(node->parent)) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
49
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
50 if (node->parent == node->parent->parent->left) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
51 temp = node->parent->parent->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
52
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
53 if (ngx_rbt_is_red(temp)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
54 ngx_rbt_black(node->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
55 ngx_rbt_black(temp);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
56 ngx_rbt_red(node->parent->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
57 node = node->parent->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
58
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
59 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
60 if (node == node->parent->right) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
61 node = node->parent;
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
62 ngx_rbtree_left_rotate(root, sentinel, node);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
63 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
64
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
65 ngx_rbt_black(node->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
66 ngx_rbt_red(node->parent->parent);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
67 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
68 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
69
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
70 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
71 temp = node->parent->parent->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
72
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
73 if (ngx_rbt_is_red(temp)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
74 ngx_rbt_black(node->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
75 ngx_rbt_black(temp);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
76 ngx_rbt_red(node->parent->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
77 node = node->parent->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
78
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
79 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
80 if (node == node->parent->left) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
81 node = node->parent;
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
82 ngx_rbtree_right_rotate(root, sentinel, node);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
83 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
84
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
85 ngx_rbt_black(node->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
86 ngx_rbt_red(node->parent->parent);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
87 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
88 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
89 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
90 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
91
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
92 ngx_rbt_black(*root);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
93 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
94
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
95
493
975f62e77f02 nginx-0.1.21-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 467
diff changeset
96 void
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
97 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
98 ngx_rbtree_node_t *sentinel)
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
99 {
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
100 ngx_rbtree_node_t **p;
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
101
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
102 for ( ;; ) {
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
103
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
104 p = (node->key < temp->key) ? &temp->left : &temp->right;
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
105
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
106 if (*p == sentinel) {
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
107 break;
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
108 }
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
109
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
110 temp = *p;
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
111 }
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
112
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
113 *p = node;
861
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
114 node->parent = temp;
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
115 node->left = sentinel;
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
116 node->right = sentinel;
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
117 ngx_rbt_red(node);
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
118 }
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
119
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
120
4924b71d77f6 ngx_rbtree_insert_value()
Igor Sysoev <igor@sysoev.ru>
parents: 853
diff changeset
121 void
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
122 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
123 ngx_rbtree_node_t *sentinel)
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
124 {
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
125 ngx_rbtree_node_t **p;
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
126
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
127 for ( ;; ) {
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
128
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
129 /*
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
130 * Timer values
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
131 * 1) are spread in small range, usually several minutes,
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
132 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
133 * The comparison takes into account that overflow.
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
134 */
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
135
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
136 /* node->key < temp->key */
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
137
4576
876e6b0814a5 Fixed signed integer overflows in timer code (ticket #145).
Maxim Dounin <mdounin@mdounin.ru>
parents: 4412
diff changeset
138 p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
139 ? &temp->left : &temp->right;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
140
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
141 if (*p == sentinel) {
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
142 break;
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
143 }
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
144
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
145 temp = *p;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
146 }
1746
3c0b44825071 style fix: remove trailing spaces
Igor Sysoev <igor@sysoev.ru>
parents: 1743
diff changeset
147
1743
4fc402c3ec73 optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents: 1023
diff changeset
148 *p = node;
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
149 node->parent = temp;
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
150 node->left = sentinel;
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
151 node->right = sentinel;
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
152 ngx_rbt_red(node);
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
153 }
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
154
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
155
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
156 void
5894
1f513d7f1b45 Events: removed broken thread support from event timers.
Valentin Bartenev <vbart@nginx.com>
parents: 4576
diff changeset
157 ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
158 {
853
a7c8cbb4c55f rbtree insert procedure
Igor Sysoev <igor@sysoev.ru>
parents: 852
diff changeset
159 ngx_uint_t red;
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
160 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
161
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
162 /* a binary tree delete */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
163
6925
b3c5b4312667 Removed casts not needed after 1f513d7f1b45.
Ruslan Ermilov <ru@nginx.com>
parents: 5894
diff changeset
164 root = &tree->root;
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
165 sentinel = tree->sentinel;
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
166
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
167 if (node->left == sentinel) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
168 temp = node->right;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
169 subst = node;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
170
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
171 } else if (node->right == sentinel) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
172 temp = node->left;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
173 subst = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
174
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
175 } else {
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
176 subst = ngx_rbtree_min(node->right, sentinel);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
177
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
178 if (subst->left != sentinel) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
179 temp = subst->left;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
180 } else {
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
181 temp = subst->right;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
182 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
183 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
184
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
185 if (subst == *root) {
229
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
186 *root = temp;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
187 ngx_rbt_black(temp);
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
188
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
189 /* DEBUG stuff */
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
190 node->left = NULL;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
191 node->right = NULL;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
192 node->parent = NULL;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
193 node->key = 0;
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
194
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
195 return;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
196 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
197
852
629b5e4f8931 change variable name
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
198 red = ngx_rbt_is_red(subst);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
199
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
200 if (subst == subst->parent->left) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
201 subst->parent->left = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
202
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
203 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
204 subst->parent->right = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
205 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
206
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
207 if (subst == node) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
208
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
209 temp->parent = subst->parent;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
210
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
211 } else {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
213 if (subst->parent == node) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
214 temp->parent = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
215
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
216 } else {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
217 temp->parent = subst->parent;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
218 }
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
219
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
220 subst->left = node->left;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
221 subst->right = node->right;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
222 subst->parent = node->parent;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
223 ngx_rbt_copy_color(subst, node);
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
224
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
225 if (node == *root) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
226 *root = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
227
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
228 } else {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
229 if (node == node->parent->left) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
230 node->parent->left = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
231 } else {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
232 node->parent->right = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
233 }
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
234 }
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
235
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
236 if (subst->left != sentinel) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
237 subst->left->parent = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
238 }
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
239
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
240 if (subst->right != sentinel) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
241 subst->right->parent = subst;
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
242 }
1764
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
243 }
229
ce6b72fe33fe nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents: 213
diff changeset
244
1764
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
245 /* DEBUG stuff */
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
246 node->left = NULL;
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
247 node->right = NULL;
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
248 node->parent = NULL;
bead8ca82404 clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents: 1746
diff changeset
249 node->key = 0;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
250
852
629b5e4f8931 change variable name
Igor Sysoev <igor@sysoev.ru>
parents: 826
diff changeset
251 if (red) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
252 return;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
253 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
254
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
255 /* a delete fixup */
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
256
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
257 while (temp != *root && ngx_rbt_is_black(temp)) {
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
258
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
259 if (temp == temp->parent->left) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
260 w = temp->parent->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
261
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
262 if (ngx_rbt_is_red(w)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
263 ngx_rbt_black(w);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
264 ngx_rbt_red(temp->parent);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
265 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
266 w = temp->parent->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
267 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
268
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
269 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
270 ngx_rbt_red(w);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
271 temp = temp->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
272
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
273 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
274 if (ngx_rbt_is_black(w->right)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
275 ngx_rbt_black(w->left);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
276 ngx_rbt_red(w);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
277 ngx_rbtree_right_rotate(root, sentinel, w);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
278 w = temp->parent->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
279 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
280
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
281 ngx_rbt_copy_color(w, temp->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
282 ngx_rbt_black(temp->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
283 ngx_rbt_black(w->right);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
284 ngx_rbtree_left_rotate(root, sentinel, temp->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
285 temp = *root;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
286 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
287
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
288 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
289 w = temp->parent->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
290
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
291 if (ngx_rbt_is_red(w)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
292 ngx_rbt_black(w);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
293 ngx_rbt_red(temp->parent);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
294 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
295 w = temp->parent->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
296 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
297
213
f536f91e8e99 nginx-0.0.1-2003-12-19-15:45:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 212
diff changeset
298 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
299 ngx_rbt_red(w);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
300 temp = temp->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
301
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
302 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
303 if (ngx_rbt_is_black(w->left)) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
304 ngx_rbt_black(w->right);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
305 ngx_rbt_red(w);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
306 ngx_rbtree_left_rotate(root, sentinel, w);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
307 w = temp->parent->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
308 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
309
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
310 ngx_rbt_copy_color(w, temp->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
311 ngx_rbt_black(temp->parent);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
312 ngx_rbt_black(w->left);
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
313 ngx_rbtree_right_rotate(root, sentinel, temp->parent);
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
314 temp = *root;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
315 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
316 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
317 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
318
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
319 ngx_rbt_black(temp);
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
320 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
321
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
322
493
975f62e77f02 nginx-0.1.21-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 467
diff changeset
323 static ngx_inline void
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
324 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
325 ngx_rbtree_node_t *node)
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
326 {
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
327 ngx_rbtree_node_t *temp;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
328
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
329 temp = node->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
330 node->right = temp->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
331
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
332 if (temp->left != sentinel) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
333 temp->left->parent = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
334 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
335
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
336 temp->parent = node->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
337
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
338 if (node == *root) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
339 *root = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
340
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
341 } else if (node == node->parent->left) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
342 node->parent->left = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
343
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
344 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
345 node->parent->right = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
346 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
347
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
348 temp->left = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
349 node->parent = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
350 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
351
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
352
493
975f62e77f02 nginx-0.1.21-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 467
diff changeset
353 static ngx_inline void
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
354 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
355 ngx_rbtree_node_t *node)
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
356 {
559
c1f965ef9718 nginx-0.3.1-RELEASE import
Igor Sysoev <igor@sysoev.ru>
parents: 557
diff changeset
357 ngx_rbtree_node_t *temp;
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
358
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
359 temp = node->left;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
360 node->left = temp->right;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
361
207
6e0fef527732 nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents: 206
diff changeset
362 if (temp->right != sentinel) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
363 temp->right->parent = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
364 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
365
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
366 temp->parent = node->parent;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
367
212
679f60139863 nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents: 207
diff changeset
368 if (node == *root) {
205
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
369 *root = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
370
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
371 } else if (node == node->parent->right) {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
372 node->parent->right = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
373
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
374 } else {
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
375 node->parent->left = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
376 }
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
377
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
378 temp->right = node;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
379 node->parent = temp;
4a9a2b1dd6fa nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff changeset
380 }
6928
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
381
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
382
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
383 ngx_rbtree_node_t *
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
384 ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
385 {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
386 ngx_rbtree_node_t *root, *sentinel, *parent;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
387
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
388 sentinel = tree->sentinel;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
389
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
390 if (node->right != sentinel) {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
391 return ngx_rbtree_min(node->right, sentinel);
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
392 }
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
393
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
394 root = tree->root;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
395
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
396 for ( ;; ) {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
397 parent = node->parent;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
398
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
399 if (node == root) {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
400 return NULL;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
401 }
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
402
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
403 if (node == parent->left) {
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
404 return parent;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
405 }
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
406
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
407 node = parent;
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
408 }
e0cc454aafe4 Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents: 6925
diff changeset
409 }