Mercurial > hg > nginx-ranges

comparison src/core/ngx_rbtree.c @ 108:cf3d6edb3ad6 NGINX_0_3_1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
nginx 0.3.1 *) Bugfix: the segmentation fault occurred when the signal queue overflowed if the "rtsig" method was used; bug appeared in 0.2.0. *) Change: correct handling of the "\\", "\"", "\'", and "\$" pairs in SSI.
author Igor Sysoev <http://sysoev.ru>
date Mon, 10 Oct 2005 00:00:00 +0400
parents 45f7329b4bd0
children 6ae1357b7b7c
comparison
equal deleted inserted replaced
107:495d867e35e8 108:cf3d6edb3ad6
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) {