Mercurial > hg > nginx-vendor-current

comparison src/core/ngx_rbtree.c @ 258:6ae1357b7b7c NGINX_0_4_14

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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