Mercurial > hg > nginx-vendor-1-0
comparison src/core/ngx_rbtree.c @ 258:6ae1357b7b7c NGINX_0_4_14
nginx 0.4.14
*) Feature: the "proxy_pass_error_message" directive in IMAP/POP3 proxy.
*) Feature: now configure detects system PCRE library on FreeBSD,
Linux, and NetBSD.
*) Bugfix: ngx_http_perl_module did not work with perl built with the
threads support; bug appeared in 0.3.38.
*) Bugfix: ngx_http_perl_module did not work if perl was called
recursively.
*) Bugfix: nginx ignored a host name in an request line.
*) Bugfix: a worker process may got caught in an endless loop, if a
FastCGI server sent too many data to the stderr.
*) Bugfix: the $upstream_response_time variable may be negative if the
system time was changed backward.
*) Bugfix: the "Auth-Login-Attempt" parameter was not sent to IMAP/POP3
proxy authentication server when POP3 was used.
*) Bugfix: a segmentation fault might occur if connect to IMAP/POP3
proxy authentication server failed.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Mon, 27 Nov 2006 00:00:00 +0300 |
parents | cf3d6edb3ad6 |
children | 052a7b1d40e5 |
comparison
equal
deleted
inserted
replaced
257:0e566ee1bcd5 | 258:6ae1357b7b7c |
---|---|
45 *root = node; | 45 *root = node; |
46 | 46 |
47 return; | 47 return; |
48 } | 48 } |
49 | 49 |
50 /* | 50 tree->insert(*root, node, sentinel); |
51 * The rbtree is currently used by event timers only. Timer values | |
52 * 1) are spread in small range, usually several minutes, | |
53 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. | |
54 * The below comparison takes into account that overflow. | |
55 * | |
56 * If there will be a necessity to use the rbtree for values with | |
57 * other comparison rules, then a whole "for ( ;; )" loop should | |
58 * be made as tree->insert() function. | |
59 */ | |
60 | |
61 temp = *root; | |
62 | |
63 for ( ;; ) { | |
64 | |
65 /* node->key < temp->key */ | |
66 | |
67 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key | |
68 < 0) | |
69 { | |
70 if (temp->left == sentinel) { | |
71 temp->left = node; | |
72 break; | |
73 } | |
74 | |
75 temp = temp->left; | |
76 continue; | |
77 } | |
78 | |
79 if (temp->right == sentinel) { | |
80 temp->right = node; | |
81 break; | |
82 } | |
83 | |
84 temp = temp->right; | |
85 continue; | |
86 } | |
87 | |
88 node->parent = temp; | |
89 node->left = sentinel; | |
90 node->right = sentinel; | |
91 | |
92 | 51 |
93 /* re-balance tree */ | 52 /* re-balance tree */ |
94 | |
95 ngx_rbt_red(node); | |
96 | 53 |
97 while (node != *root && ngx_rbt_is_red(node->parent)) { | 54 while (node != *root && ngx_rbt_is_red(node->parent)) { |
98 | 55 |
99 if (node->parent == node->parent->parent->left) { | 56 if (node->parent == node->parent->parent->left) { |
100 temp = node->parent->parent->right; | 57 temp = node->parent->parent->right; |
134 ngx_rbt_black(node->parent); | 91 ngx_rbt_black(node->parent); |
135 ngx_rbt_red(node->parent->parent); | 92 ngx_rbt_red(node->parent->parent); |
136 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); | 93 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); |
137 } | 94 } |
138 } | 95 } |
139 | |
140 } | 96 } |
141 | 97 |
142 ngx_rbt_black(*root); | 98 ngx_rbt_black(*root); |
99 } | |
100 | |
101 | |
102 void | |
103 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, | |
104 ngx_rbtree_node_t *sentinel) | |
105 { | |
106 for ( ;; ) { | |
107 | |
108 if (node->key < temp->key) { | |
109 | |
110 if (temp->left == sentinel) { | |
111 temp->left = node; | |
112 break; | |
113 } | |
114 | |
115 temp = temp->left; | |
116 | |
117 } else { | |
118 | |
119 if (temp->right == sentinel) { | |
120 temp->right = node; | |
121 break; | |
122 } | |
123 | |
124 temp = temp->right; | |
125 } | |
126 } | |
127 | |
128 node->parent = temp; | |
129 node->left = sentinel; | |
130 node->right = sentinel; | |
131 ngx_rbt_red(node); | |
132 } | |
133 | |
134 | |
135 void | |
136 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, | |
137 ngx_rbtree_node_t *sentinel) | |
138 { | |
139 for ( ;; ) { | |
140 | |
141 /* | |
142 * Timer values | |
143 * 1) are spread in small range, usually several minutes, | |
144 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. | |
145 * The comparison takes into account that overflow. | |
146 */ | |
147 | |
148 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key | |
149 < 0) | |
150 { | |
151 /* node->key < temp->key */ | |
152 | |
153 if (temp->left == sentinel) { | |
154 temp->left = node; | |
155 break; | |
156 } | |
157 | |
158 temp = temp->left; | |
159 | |
160 } else { | |
161 | |
162 if (temp->right == sentinel) { | |
163 temp->right = node; | |
164 break; | |
165 } | |
166 | |
167 temp = temp->right; | |
168 } | |
169 } | |
170 | |
171 node->parent = temp; | |
172 node->left = sentinel; | |
173 node->right = sentinel; | |
174 ngx_rbt_red(node); | |
143 } | 175 } |
144 | 176 |
145 | 177 |
146 void | 178 void |
147 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, | 179 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, |
148 ngx_rbtree_node_t *node) | 180 ngx_rbtree_node_t *node) |
149 { | 181 { |
150 ngx_int_t is_red; | 182 ngx_uint_t red; |
151 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; | 183 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; |
152 | 184 |
153 /* a binary tree delete */ | 185 /* a binary tree delete */ |
154 | 186 |
155 root = (ngx_rbtree_node_t **) &tree->root; | 187 root = (ngx_rbtree_node_t **) &tree->root; |
184 node->key = 0; | 216 node->key = 0; |
185 | 217 |
186 return; | 218 return; |
187 } | 219 } |
188 | 220 |
189 is_red = ngx_rbt_is_red(subst); | 221 red = ngx_rbt_is_red(subst); |
190 | 222 |
191 if (subst == subst->parent->left) { | 223 if (subst == subst->parent->left) { |
192 subst->parent->left = temp; | 224 subst->parent->left = temp; |
193 | 225 |
194 } else { | 226 } else { |
237 node->right = NULL; | 269 node->right = NULL; |
238 node->parent = NULL; | 270 node->parent = NULL; |
239 node->key = 0; | 271 node->key = 0; |
240 } | 272 } |
241 | 273 |
242 if (is_red) { | 274 if (red) { |
243 return; | 275 return; |
244 } | 276 } |
245 | 277 |
246 /* a delete fixup */ | 278 /* a delete fixup */ |
247 | 279 |