Mercurial > hg > nginx-quic
comparison src/http/modules/ngx_http_limit_zone_module.c @ 1743:4fc402c3ec73
optimize rbtree initialization and insert
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Mon, 17 Dec 2007 08:52:00 +0000 |
parents | 03341711f9a2 |
children | 7148efbdd798 |
comparison
equal
deleted
inserted
replaced
1742:268b81386fe4 | 1743:4fc402c3ec73 |
---|---|
237 | 237 |
238 static void | 238 static void |
239 ngx_http_limit_zone_rbtree_insert_value(ngx_rbtree_node_t *temp, | 239 ngx_http_limit_zone_rbtree_insert_value(ngx_rbtree_node_t *temp, |
240 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) | 240 ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel) |
241 { | 241 { |
242 ngx_http_limit_zone_node_t *lzn, *lznt; | 242 ngx_rbtree_node_t **p; |
243 ngx_http_limit_zone_node_t *lzn, *lznt; | |
243 | 244 |
244 for ( ;; ) { | 245 for ( ;; ) { |
245 | 246 |
246 if (node->key < temp->key) { | 247 if (node->key < temp->key) { |
247 | 248 |
248 if (temp->left == sentinel) { | 249 p = &temp->left; |
249 temp->left = node; | |
250 break; | |
251 } | |
252 | |
253 temp = temp->left; | |
254 | 250 |
255 } else if (node->key > temp->key) { | 251 } else if (node->key > temp->key) { |
256 | 252 |
257 if (temp->right == sentinel) { | 253 p = &temp->right; |
258 temp->right = node; | |
259 break; | |
260 } | |
261 | |
262 temp = temp->right; | |
263 | 254 |
264 } else { /* node->key == temp->key */ | 255 } else { /* node->key == temp->key */ |
265 | 256 |
266 lzn = (ngx_http_limit_zone_node_t *) &node->color; | 257 lzn = (ngx_http_limit_zone_node_t *) &node->color; |
267 lznt = (ngx_http_limit_zone_node_t *) &temp->color; | 258 lznt = (ngx_http_limit_zone_node_t *) &temp->color; |
268 | 259 |
269 if (ngx_memn2cmp(lzn->data, lznt->data, lzn->len, lznt->len) < 0) { | 260 p = (ngx_memn2cmp(lzn->data, lznt->data, lzn->len, lznt->len) < 0) |
270 | 261 ? &temp->left : &temp->right; |
271 if (temp->left == sentinel) { | |
272 temp->left = node; | |
273 break; | |
274 } | |
275 | |
276 temp = temp->left; | |
277 | |
278 } else { | |
279 | |
280 if (temp->right == sentinel) { | |
281 temp->right = node; | |
282 break; | |
283 } | |
284 | |
285 temp = temp->right; | |
286 } | |
287 } | 262 } |
288 } | 263 |
289 | 264 if (*p == sentinel) { |
265 break; | |
266 } | |
267 | |
268 temp = *p; | |
269 } | |
270 | |
271 *p = node; | |
290 node->parent = temp; | 272 node->parent = temp; |
291 node->left = sentinel; | 273 node->left = sentinel; |
292 node->right = sentinel; | 274 node->right = sentinel; |
293 ngx_rbt_red(node); | 275 ngx_rbt_red(node); |
294 } | 276 } |
360 sentinel = ngx_slab_alloc(shpool, sizeof(ngx_rbtree_node_t)); | 342 sentinel = ngx_slab_alloc(shpool, sizeof(ngx_rbtree_node_t)); |
361 if (sentinel == NULL) { | 343 if (sentinel == NULL) { |
362 return NGX_ERROR; | 344 return NGX_ERROR; |
363 } | 345 } |
364 | 346 |
365 ngx_rbtree_sentinel_init(sentinel); | 347 ngx_rbtree_init(ctx->rbtree, sentinel, |
366 | 348 ngx_http_limit_zone_rbtree_insert_value); |
367 ctx->rbtree->root = sentinel; | |
368 ctx->rbtree->sentinel = sentinel; | |
369 ctx->rbtree->insert = ngx_http_limit_zone_rbtree_insert_value; | |
370 | 349 |
371 return NGX_OK; | 350 return NGX_OK; |
372 } | 351 } |
373 | 352 |
374 | 353 |