Mercurial > hg > nginx-quic
annotate src/core/ngx_rbtree.c @ 1177:ff0195dfbe0c
bump version
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Thu, 19 Apr 2007 18:23:54 +0000 |
parents | 68cc5e2e1a5d |
children | 4fc402c3ec73 |
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 |
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
|
4 */ |
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 |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
6 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
7 #include <ngx_config.h> |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
8 #include <ngx_core.h> |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
9 |
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 /* |
559 | 12 * The red-black tree code is based on the algorithm described in |
13 * 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
|
14 */ |
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 |
559 | 17 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, |
18 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); | |
19 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, | |
20 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); | |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
21 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
22 |
493 | 23 void |
559 | 24 ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, |
25 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 |
559 | 31 root = (ngx_rbtree_node_t **) &tree->root; |
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 { | |
100 for ( ;; ) { | |
101 | |
102 if (node->key < temp->key) { | |
103 | |
104 if (temp->left == sentinel) { | |
105 temp->left = node; | |
106 break; | |
107 } | |
108 | |
109 temp = temp->left; | |
110 | |
111 } else { | |
112 | |
113 if (temp->right == sentinel) { | |
114 temp->right = node; | |
115 break; | |
116 } | |
117 | |
118 temp = temp->right; | |
119 } | |
120 } | |
121 | |
122 node->parent = temp; | |
123 node->left = sentinel; | |
124 node->right = sentinel; | |
125 ngx_rbt_red(node); | |
126 } | |
127 | |
128 | |
129 void | |
853 | 130 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, |
131 ngx_rbtree_node_t *sentinel) | |
132 { | |
133 for ( ;; ) { | |
134 | |
135 /* | |
136 * Timer values | |
137 * 1) are spread in small range, usually several minutes, | |
138 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. | |
139 * The comparison takes into account that overflow. | |
140 */ | |
141 | |
142 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key | |
143 < 0) | |
144 { | |
145 /* node->key < temp->key */ | |
146 | |
147 if (temp->left == sentinel) { | |
148 temp->left = node; | |
149 break; | |
150 } | |
151 | |
152 temp = temp->left; | |
153 | |
154 } else { | |
155 | |
156 if (temp->right == sentinel) { | |
157 temp->right = node; | |
158 break; | |
159 } | |
160 | |
161 temp = temp->right; | |
162 } | |
163 } | |
164 | |
165 node->parent = temp; | |
166 node->left = sentinel; | |
167 node->right = sentinel; | |
168 ngx_rbt_red(node); | |
169 } | |
170 | |
171 | |
172 void | |
559 | 173 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, |
174 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
|
175 { |
853 | 176 ngx_uint_t red; |
559 | 177 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
|
178 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
179 /* a binary tree delete */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
180 |
559 | 181 root = (ngx_rbtree_node_t **) &tree->root; |
182 sentinel = tree->sentinel; | |
183 | |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
184 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
|
185 temp = node->right; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
186 subst = node; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
187 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
188 } 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
|
189 temp = node->left; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
190 subst = node; |
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 } else { |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
193 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
|
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->left != sentinel) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
196 temp = subst->left; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
197 } else { |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
198 temp = subst->right; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
199 } |
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 == *root) { |
229
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
203 *root = temp; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
204 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
|
205 |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
206 /* DEBUG stuff */ |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
207 node->left = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
208 node->right = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
209 node->parent = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
210 node->key = 0; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
211 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
212 return; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
213 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
214 |
852 | 215 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
|
216 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
217 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
|
218 subst->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
219 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
220 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
221 subst->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
222 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
223 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
224 if (subst == node) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
225 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
226 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
|
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 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
230 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
|
231 temp->parent = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
232 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
233 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
234 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
|
235 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
236 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
237 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
|
238 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
|
239 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
|
240 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
|
241 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
242 if (node == *root) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
243 *root = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
244 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
245 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
246 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
|
247 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
|
248 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
249 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
|
250 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
251 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
252 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
253 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
|
254 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
|
255 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
256 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
257 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
|
258 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
|
259 } |
229
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
260 |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
261 /* DEBUG stuff */ |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
262 node->left = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
263 node->right = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
264 node->parent = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
265 node->key = 0; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
266 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
267 |
852 | 268 if (red) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
269 return; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
270 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
271 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
272 /* a delete fixup */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
273 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
274 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
|
275 |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
276 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
|
277 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
278 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
279 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
|
280 ngx_rbt_black(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
281 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
|
282 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
|
283 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
284 } |
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_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
|
287 ngx_rbt_red(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
288 temp = temp->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
289 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
290 } else { |
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_black(w->right)) { |
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->left); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
293 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
|
294 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
|
295 w = temp->parent->right; |
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 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
298 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
|
299 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
|
300 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
|
301 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
|
302 temp = *root; |
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 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
306 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
307 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
308 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
|
309 ngx_rbt_black(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
310 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
|
311 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
|
312 w = temp->parent->left; |
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 |
213
f536f91e8e99
nginx-0.0.1-2003-12-19-15:45:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
212
diff
changeset
|
315 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
|
316 ngx_rbt_red(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
317 temp = temp->parent; |
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 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
320 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
|
321 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
|
322 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
|
323 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
|
324 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
325 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
326 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
327 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
|
328 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
|
329 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
|
330 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
|
331 temp = *root; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
332 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
333 } |
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 ngx_rbt_black(temp); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
337 } |
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 |
493 | 340 static ngx_inline void |
559 | 341 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
342 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
|
343 { |
559 | 344 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
|
345 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
346 temp = node->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
347 node->right = temp->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
348 |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
349 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
|
350 temp->left->parent = node; |
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 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
353 temp->parent = node->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
354 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
355 if (node == *root) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
356 *root = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
357 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
358 } 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
|
359 node->parent->left = temp; |
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 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
362 node->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
363 } |
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 temp->left = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
366 node->parent = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
367 } |
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 |
493 | 370 static ngx_inline void |
559 | 371 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
372 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
|
373 { |
559 | 374 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
|
375 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
376 temp = node->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
377 node->left = temp->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
378 |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
379 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
|
380 temp->right->parent = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
381 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
382 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
383 temp->parent = node->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
384 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
385 if (node == *root) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
386 *root = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
387 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
388 } 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
|
389 node->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
390 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
391 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
392 node->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
393 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
394 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
395 temp->right = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
396 node->parent = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
397 } |