Mercurial > hg > nginx
comparison src/core/ngx_rbtree.c @ 559:c1f965ef9718 release-0.3.1
nginx-0.3.1-RELEASE import
*) Bugfix: the segmentation fault occurred when the signal queue
overflowed if the "rtsig" method was used; the bug had appeared in
0.2.0.
*) Change: correct handling of the "\\", "\"", "\'", and "\$" pairs in
SSI.
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Mon, 10 Oct 2005 12:59:41 +0000 |
parents | ecd9c160f25b |
children | f9b9b84a8e18 |
comparison
equal
deleted
inserted
replaced
558:96a964d17328 | 559:c1f965ef9718 |
---|---|
7 #include <ngx_config.h> | 7 #include <ngx_config.h> |
8 #include <ngx_core.h> | 8 #include <ngx_core.h> |
9 | 9 |
10 | 10 |
11 /* | 11 /* |
12 * The code is based on the algorithm described in the "Introduction | 12 * The red-black tree code is based on the algorithm described in |
13 * to Algorithms" by Cormen, Leiserson and Rivest. | 13 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest. |
14 */ | 14 */ |
15 | 15 |
16 #define ngx_rbt_red(node) ((node)->color = 1) | 16 #define ngx_rbt_red(node) ((node)->color = 1) |
17 #define ngx_rbt_black(node) ((node)->color = 0) | 17 #define ngx_rbt_black(node) ((node)->color = 0) |
18 #define ngx_rbt_is_red(node) ((node)->color) | 18 #define ngx_rbt_is_red(node) ((node)->color) |
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_node_t **root, |
24 ngx_rbtree_t *sentinel, ngx_rbtree_t *node); | 24 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); |
25 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_t **root, | 25 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, |
26 ngx_rbtree_t *sentinel, ngx_rbtree_t *node); | 26 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); |
27 | 27 |
28 | 28 |
29 void | 29 void |
30 ngx_rbtree_insert(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, | 30 ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, |
31 ngx_rbtree_t *node) | 31 ngx_rbtree_node_t *node) |
32 { | 32 { |
33 ngx_rbtree_t *temp; | 33 ngx_rbtree_node_t **root, *temp, *sentinel; |
34 | 34 |
35 /* a binary tree insert */ | 35 /* a binary tree insert */ |
36 | |
37 root = (ngx_rbtree_node_t **) &tree->root; | |
38 sentinel = tree->sentinel; | |
36 | 39 |
37 if (*root == sentinel) { | 40 if (*root == sentinel) { |
38 node->parent = NULL; | 41 node->parent = NULL; |
39 node->left = sentinel; | 42 node->left = sentinel; |
40 node->right = sentinel; | 43 node->right = sentinel; |
42 *root = node; | 45 *root = node; |
43 | 46 |
44 return; | 47 return; |
45 } | 48 } |
46 | 49 |
50 /* | |
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 | |
47 temp = *root; | 61 temp = *root; |
48 | 62 |
49 for ( ;; ) { | 63 for ( ;; ) { |
50 | 64 |
51 /* node->key < temp->key */ | 65 /* node->key < temp->key */ |
128 ngx_rbt_black(*root); | 142 ngx_rbt_black(*root); |
129 } | 143 } |
130 | 144 |
131 | 145 |
132 void | 146 void |
133 ngx_rbtree_delete(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, | 147 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, |
134 ngx_rbtree_t *node) | 148 ngx_rbtree_node_t *node) |
135 { | 149 { |
136 ngx_int_t is_red; | 150 ngx_int_t is_red; |
137 ngx_rbtree_t *subst, *temp, *w; | 151 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; |
138 | 152 |
139 /* a binary tree delete */ | 153 /* a binary tree delete */ |
154 | |
155 root = (ngx_rbtree_node_t **) &tree->root; | |
156 sentinel = tree->sentinel; | |
140 | 157 |
141 if (node->left == sentinel) { | 158 if (node->left == sentinel) { |
142 temp = node->right; | 159 temp = node->right; |
143 subst = node; | 160 subst = node; |
144 | 161 |
293 ngx_rbt_black(temp); | 310 ngx_rbt_black(temp); |
294 } | 311 } |
295 | 312 |
296 | 313 |
297 static ngx_inline void | 314 static ngx_inline void |
298 ngx_rbtree_left_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, | 315 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
299 ngx_rbtree_t *node) | 316 ngx_rbtree_node_t *node) |
300 { | 317 { |
301 ngx_rbtree_t *temp; | 318 ngx_rbtree_node_t *temp; |
302 | 319 |
303 temp = node->right; | 320 temp = node->right; |
304 node->right = temp->left; | 321 node->right = temp->left; |
305 | 322 |
306 if (temp->left != sentinel) { | 323 if (temp->left != sentinel) { |
323 node->parent = temp; | 340 node->parent = temp; |
324 } | 341 } |
325 | 342 |
326 | 343 |
327 static ngx_inline void | 344 static ngx_inline void |
328 ngx_rbtree_right_rotate(ngx_rbtree_t **root, ngx_rbtree_t *sentinel, | 345 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
329 ngx_rbtree_t *node) | 346 ngx_rbtree_node_t *node) |
330 { | 347 { |
331 ngx_rbtree_t *temp; | 348 ngx_rbtree_node_t *temp; |
332 | 349 |
333 temp = node->left; | 350 temp = node->left; |
334 node->left = temp->right; | 351 node->left = temp->right; |
335 | 352 |
336 if (temp->right != sentinel) { | 353 if (temp->right != sentinel) { |