Mercurial > hg > nginx
annotate src/core/ngx_rbtree.c @ 8801:2029a30863e2 quic
QUIC: using compile time block/iv length for tokens.
Reference values can be found in RFC 3602, 2.1, 2.4.
author | Sergey Kandaurov <pluknet@nginx.com> |
---|---|
date | Wed, 16 Jun 2021 18:03:33 +0300 |
parents | 7fdcf308e0f0 |
children |
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 | 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 | 13 * The red-black tree code is based on the algorithm described in |
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 | 18 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, |
19 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); | |
20 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, | |
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 | 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 | 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 | 32 sentinel = tree->sentinel; |
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 | 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 | 96 void |
861 | 97 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, |
98 ngx_rbtree_node_t *sentinel) | |
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 | 102 for ( ;; ) { |
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 | 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 | 109 |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
110 temp = *p; |
861 | 111 } |
112 | |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
113 *p = node; |
861 | 114 node->parent = temp; |
115 node->left = sentinel; | |
116 node->right = sentinel; | |
117 ngx_rbt_red(node); | |
118 } | |
119 | |
120 | |
121 void | |
853 | 122 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, |
123 ngx_rbtree_node_t *sentinel) | |
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 | 127 for ( ;; ) { |
128 | |
129 /* | |
130 * Timer values | |
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. | |
134 */ | |
135 | |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
136 /* node->key < temp->key */ |
853 | 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 | 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 | 144 |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
145 temp = *p; |
853 | 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 | 149 node->parent = temp; |
150 node->left = sentinel; | |
151 node->right = sentinel; | |
152 ngx_rbt_red(node); | |
153 } | |
154 | |
155 | |
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 | 159 ngx_uint_t red; |
559 | 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 | 165 sentinel = tree->sentinel; |
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); |
7576
7fdcf308e0f0
Core: removed dead code in ngx_rbtree_delete().
Vladimir Homutov <vl@nginx.com>
parents:
6928
diff
changeset
|
177 temp = subst->right; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
178 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
179 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
180 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
|
181 *root = temp; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
182 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
|
183 |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
184 /* DEBUG stuff */ |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
185 node->left = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
186 node->right = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
187 node->parent = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
188 node->key = 0; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
189 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
190 return; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
191 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
192 |
852 | 193 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
|
194 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
195 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
|
196 subst->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
197 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
198 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
199 subst->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
200 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
201 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
202 if (subst == node) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
203 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
204 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
|
205 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
206 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
207 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
208 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
|
209 temp->parent = subst; |
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 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
|
213 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
214 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
215 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
|
216 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
|
217 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
|
218 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
|
219 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
220 if (node == *root) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
221 *root = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
222 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
223 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
224 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
|
225 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
|
226 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
227 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
|
228 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
229 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
230 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
231 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
|
232 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
|
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 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
|
236 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
|
237 } |
1764
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
238 } |
229
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
239 |
1764
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
240 /* DEBUG stuff */ |
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
241 node->left = NULL; |
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
242 node->right = NULL; |
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
243 node->parent = NULL; |
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
244 node->key = 0; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
245 |
852 | 246 if (red) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
247 return; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
248 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
249 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
250 /* a delete fixup */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
251 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
252 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
|
253 |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
254 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
|
255 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
256 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
257 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
|
258 ngx_rbt_black(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
259 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
|
260 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
|
261 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
262 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
263 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
264 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
|
265 ngx_rbt_red(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
266 temp = temp->parent; |
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 } else { |
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->right)) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
270 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
|
271 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
|
272 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
|
273 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
274 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
275 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
276 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
|
277 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
|
278 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
|
279 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
|
280 temp = *root; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
281 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
282 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
283 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
284 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
285 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
286 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
|
287 ngx_rbt_black(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
288 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
|
289 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
|
290 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
291 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
292 |
213
f536f91e8e99
nginx-0.0.1-2003-12-19-15:45:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
212
diff
changeset
|
293 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
|
294 ngx_rbt_red(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
295 temp = temp->parent; |
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 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
298 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
|
299 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
|
300 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
|
301 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
|
302 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
303 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
304 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
305 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
|
306 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
|
307 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
|
308 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
|
309 temp = *root; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
310 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
311 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
312 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
313 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
314 ngx_rbt_black(temp); |
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 |
493 | 318 static ngx_inline void |
559 | 319 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
320 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
|
321 { |
559 | 322 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
|
323 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
324 temp = node->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
325 node->right = temp->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
326 |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
327 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
|
328 temp->left->parent = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
329 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
330 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
331 temp->parent = node->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
332 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
333 if (node == *root) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
334 *root = temp; |
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 } 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
|
337 node->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
338 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
339 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
340 node->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
341 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
342 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
343 temp->left = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
344 node->parent = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
345 } |
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 |
493 | 348 static ngx_inline void |
559 | 349 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
350 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
|
351 { |
559 | 352 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
|
353 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
354 temp = node->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
355 node->left = temp->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
356 |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
357 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
|
358 temp->right->parent = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
359 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
360 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
361 temp->parent = node->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
362 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
363 if (node == *root) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
364 *root = temp; |
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 } 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
|
367 node->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
368 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
369 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
370 node->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
371 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
372 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
373 temp->right = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
374 node->parent = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
375 } |
6928
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
376 |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
377 |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
378 ngx_rbtree_node_t * |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
379 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
|
380 { |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
381 ngx_rbtree_node_t *root, *sentinel, *parent; |
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 sentinel = tree->sentinel; |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
384 |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
385 if (node->right != sentinel) { |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
386 return ngx_rbtree_min(node->right, sentinel); |
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 |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
389 root = tree->root; |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
390 |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
391 for ( ;; ) { |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
392 parent = node->parent; |
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 if (node == root) { |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
395 return NULL; |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
396 } |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
397 |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
398 if (node == parent->left) { |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
399 return parent; |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
400 } |
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 node = parent; |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
403 } |
e0cc454aafe4
Core: introduced ngx_rbtree_next().
Maxim Dounin <mdounin@mdounin.ru>
parents:
6925
diff
changeset
|
404 } |