Mercurial > hg > nginx-vendor-current

comparison src/core/ngx_rbtree.c @ 42:41ccba1aba45 NGINX_0_1_21

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