Mercurial > hg > nginx-ranges
comparison src/core/ngx_rbtree.c @ 42:41ccba1aba45 NGINX_0_1_21
nginx 0.1.21
*) Bugfix: the ngx_http_stub_status_module showed incorrect statistics
if "rtsig" method was used or if several worker process ran on SMP.
*) Bugfix: nginx could not be built by the icc compiler on Linux or if
the zlib-1.2.x library was building from sources.
*) Bugfix: nginx could not be built on NetBSD 2.0.
author | Igor Sysoev <http://sysoev.ru> |
---|---|
date | Tue, 22 Feb 2005 00:00:00 +0300 |
parents | 74b1868dd3cd |
children | 45f7329b4bd0 |
comparison
equal
deleted
inserted
replaced
41:4d8e7a81b3a0 | 42:41ccba1aba45 |
---|---|
19 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node)) | 19 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node)) |
20 #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color) | 20 #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color) |
21 | 21 |
22 | 22 |
23 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, | 23 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, |
24 ngx_rbtree_t *sentinel, | 24 ngx_rbtree_t *sentinel, ngx_rbtree_t *node); |
25 ngx_rbtree_t *node); | |
26 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, | 25 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, |
27 ngx_rbtree_t *sentinel, | 26 ngx_rbtree_t *sentinel, ngx_rbtree_t *node); |
28 ngx_rbtree_t *node); | 27 |
29 | 28 |
30 | 29 void |
31 void ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, | 30 ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, |
32 ngx_rbtree_t *node) | 31 ngx_rbtree_t *node) |
33 { | 32 { |
34 ngx_rbtree_t *temp; | 33 ngx_rbtree_t *temp; |
35 | 34 |
36 /* a binary tree insert */ | 35 /* a binary tree insert */ |
37 | 36 |
123 | 122 |
124 ngx_rbt_black(*root); | 123 ngx_rbt_black(*root); |
125 } | 124 } |
126 | 125 |
127 | 126 |
128 void ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, | 127 void |
129 ngx_rbtree_t *node) | 128 ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, |
129 ngx_rbtree_t *node) | |
130 { | 130 { |
131 ngx_int_t is_red; | 131 ngx_int_t is_red; |
132 ngx_rbtree_t *subst, *temp, *w; | 132 ngx_rbtree_t *subst, *temp, *w; |
133 | 133 |
134 /* a binary tree delete */ | 134 /* a binary tree delete */ |
287 | 287 |
288 ngx_rbt_black(temp); | 288 ngx_rbt_black(temp); |
289 } | 289 } |
290 | 290 |
291 | 291 |
292 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_t **root, | 292 static ngx_inline void |
293 ngx_rbtree_t *sentinel, | 293 ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, |
294 ngx_rbtree_t *node) | 294 ngx_rbtree_t *node) |
295 { | 295 { |
296 ngx_rbtree_t *temp; | 296 ngx_rbtree_t *temp; |
297 | 297 |
298 temp = node->right; | 298 temp = node->right; |
299 node->right = temp->left; | 299 node->right = temp->left; |
317 temp->left = node; | 317 temp->left = node; |
318 node->parent = temp; | 318 node->parent = temp; |
319 } | 319 } |
320 | 320 |
321 | 321 |
322 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, | 322 static ngx_inline void |
323 ngx_rbtree_t *sentinel, | 323 ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, |
324 ngx_rbtree_t *node) | 324 ngx_rbtree_t *node) |
325 { | 325 { |
326 ngx_rbtree_t *temp; | 326 ngx_rbtree_t *temp; |
327 | 327 |
328 temp = node->left; | 328 temp = node->left; |
329 node->left = temp->right; | 329 node->left = temp->right; |