Mercurial > hg > nginx
annotate src/core/ngx_rbtree.c @ 4576:876e6b0814a5
Fixed signed integer overflows in timer code (ticket #145).
Integer overflow is undefined behaviour in C and this indeed caused
problems on Solaris/SPARC (at least in some cases). Fix is to
subtract unsigned integers instead, and then cast result to a signed
one, which is implementation-defined behaviour and used to work.
Strictly speaking, we should compare (unsigned) result with the maximum
value of the corresponding signed integer type instead, this will be
defined behaviour. This will require much more changes though, and
considered to be overkill for now.
author | Maxim Dounin <mdounin@mdounin.ru> |
---|---|
date | Fri, 06 Apr 2012 23:46:09 +0000 |
parents | d620f497c50f |
children | 1f513d7f1b45 |
rev | line source |
---|---|
441
da8c5707af39
nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents:
229
diff
changeset
|
1 |
da8c5707af39
nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents:
229
diff
changeset
|
2 /* |
444
42d11f017717
nginx-0.1.0-2004-09-29-20:00:49 import; remove years from copyright
Igor Sysoev <igor@sysoev.ru>
parents:
441
diff
changeset
|
3 * Copyright (C) Igor Sysoev |
4412 | 4 * Copyright (C) Nginx, Inc. |
441
da8c5707af39
nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents:
229
diff
changeset
|
5 */ |
da8c5707af39
nginx-0.1.0-2004-09-28-12:34:51 import; set copyright and remove unused files
Igor Sysoev <igor@sysoev.ru>
parents:
229
diff
changeset
|
6 |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
7 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
8 #include <ngx_config.h> |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
9 #include <ngx_core.h> |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
10 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
11 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
12 /* |
559 | 13 * The red-black tree code is based on the algorithm described in |
14 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest. | |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
15 */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
16 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
17 |
559 | 18 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, |
19 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); | |
20 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, | |
21 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); | |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
22 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
23 |
493 | 24 void |
559 | 25 ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, |
26 ngx_rbtree_node_t *node) | |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
27 { |
559 | 28 ngx_rbtree_node_t **root, *temp, *sentinel; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
29 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
30 /* a binary tree insert */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
31 |
559 | 32 root = (ngx_rbtree_node_t **) &tree->root; |
33 sentinel = tree->sentinel; | |
34 | |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
35 if (*root == sentinel) { |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
36 node->parent = NULL; |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
37 node->left = sentinel; |
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
38 node->right = sentinel; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
39 ngx_rbt_black(node); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
40 *root = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
41 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
42 return; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
43 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
44 |
853 | 45 tree->insert(*root, node, sentinel); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
46 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
47 /* re-balance tree */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
48 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
49 while (node != *root && ngx_rbt_is_red(node->parent)) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
50 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
51 if (node->parent == node->parent->parent->left) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
52 temp = node->parent->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
53 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
54 if (ngx_rbt_is_red(temp)) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
55 ngx_rbt_black(node->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
56 ngx_rbt_black(temp); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
57 ngx_rbt_red(node->parent->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
58 node = node->parent->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
59 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
60 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
61 if (node == node->parent->right) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
62 node = node->parent; |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
63 ngx_rbtree_left_rotate(root, sentinel, node); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
64 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
65 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
66 ngx_rbt_black(node->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
67 ngx_rbt_red(node->parent->parent); |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
68 ngx_rbtree_right_rotate(root, sentinel, node->parent->parent); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
69 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
70 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
71 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
72 temp = node->parent->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
73 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
74 if (ngx_rbt_is_red(temp)) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
75 ngx_rbt_black(node->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
76 ngx_rbt_black(temp); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
77 ngx_rbt_red(node->parent->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
78 node = node->parent->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
79 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
80 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
81 if (node == node->parent->left) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
82 node = node->parent; |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
83 ngx_rbtree_right_rotate(root, sentinel, node); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
84 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
85 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
86 ngx_rbt_black(node->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
87 ngx_rbt_red(node->parent->parent); |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
88 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
89 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
90 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
91 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
92 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
93 ngx_rbt_black(*root); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
94 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
95 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
96 |
493 | 97 void |
861 | 98 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, |
99 ngx_rbtree_node_t *sentinel) | |
100 { | |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
101 ngx_rbtree_node_t **p; |
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
102 |
861 | 103 for ( ;; ) { |
104 | |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
105 p = (node->key < temp->key) ? &temp->left : &temp->right; |
861 | 106 |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
107 if (*p == sentinel) { |
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
108 break; |
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
109 } |
861 | 110 |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
111 temp = *p; |
861 | 112 } |
113 | |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
114 *p = node; |
861 | 115 node->parent = temp; |
116 node->left = sentinel; | |
117 node->right = sentinel; | |
118 ngx_rbt_red(node); | |
119 } | |
120 | |
121 | |
122 void | |
853 | 123 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, |
124 ngx_rbtree_node_t *sentinel) | |
125 { | |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
126 ngx_rbtree_node_t **p; |
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
127 |
853 | 128 for ( ;; ) { |
129 | |
130 /* | |
131 * Timer values | |
132 * 1) are spread in small range, usually several minutes, | |
133 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. | |
134 * The comparison takes into account that overflow. | |
135 */ | |
136 | |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
137 /* node->key < temp->key */ |
853 | 138 |
4576
876e6b0814a5
Fixed signed integer overflows in timer code (ticket #145).
Maxim Dounin <mdounin@mdounin.ru>
parents:
4412
diff
changeset
|
139 p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0) |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
140 ? &temp->left : &temp->right; |
853 | 141 |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
142 if (*p == sentinel) { |
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
143 break; |
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
144 } |
853 | 145 |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
146 temp = *p; |
853 | 147 } |
1746
3c0b44825071
style fix: remove trailing spaces
Igor Sysoev <igor@sysoev.ru>
parents:
1743
diff
changeset
|
148 |
1743
4fc402c3ec73
optimize rbtree initialization and insert
Igor Sysoev <igor@sysoev.ru>
parents:
1023
diff
changeset
|
149 *p = node; |
853 | 150 node->parent = temp; |
151 node->left = sentinel; | |
152 node->right = sentinel; | |
153 ngx_rbt_red(node); | |
154 } | |
155 | |
156 | |
157 void | |
559 | 158 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, |
159 ngx_rbtree_node_t *node) | |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
160 { |
853 | 161 ngx_uint_t red; |
559 | 162 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
163 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
164 /* a binary tree delete */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
165 |
559 | 166 root = (ngx_rbtree_node_t **) &tree->root; |
167 sentinel = tree->sentinel; | |
168 | |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
169 if (node->left == sentinel) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
170 temp = node->right; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
171 subst = node; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
172 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
173 } else if (node->right == sentinel) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
174 temp = node->left; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
175 subst = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
176 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
177 } else { |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
178 subst = ngx_rbtree_min(node->right, sentinel); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
179 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
180 if (subst->left != sentinel) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
181 temp = subst->left; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
182 } else { |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
183 temp = subst->right; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
184 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
185 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
186 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
187 if (subst == *root) { |
229
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
188 *root = temp; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
189 ngx_rbt_black(temp); |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
190 |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
191 /* DEBUG stuff */ |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
192 node->left = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
193 node->right = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
194 node->parent = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
195 node->key = 0; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
196 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
197 return; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
198 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
199 |
852 | 200 red = ngx_rbt_is_red(subst); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
201 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
202 if (subst == subst->parent->left) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
203 subst->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
204 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
205 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
206 subst->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
207 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
208 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
209 if (subst == node) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
210 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
211 temp->parent = subst->parent; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
212 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
213 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
214 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
215 if (subst->parent == node) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
216 temp->parent = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
217 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
218 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
219 temp->parent = subst->parent; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
220 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
221 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
222 subst->left = node->left; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
223 subst->right = node->right; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
224 subst->parent = node->parent; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
225 ngx_rbt_copy_color(subst, node); |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
226 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
227 if (node == *root) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
228 *root = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
229 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
230 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
231 if (node == node->parent->left) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
232 node->parent->left = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
233 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
234 node->parent->right = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
235 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
236 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
237 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
238 if (subst->left != sentinel) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
239 subst->left->parent = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
240 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
241 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
242 if (subst->right != sentinel) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
243 subst->right->parent = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
244 } |
1764
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
245 } |
229
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
246 |
1764
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
247 /* DEBUG stuff */ |
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
248 node->left = NULL; |
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
249 node->right = NULL; |
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
250 node->parent = NULL; |
bead8ca82404
clean rbtree node for all removals
Igor Sysoev <igor@sysoev.ru>
parents:
1746
diff
changeset
|
251 node->key = 0; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
252 |
852 | 253 if (red) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
254 return; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
255 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
256 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
257 /* a delete fixup */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
258 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
259 while (temp != *root && ngx_rbt_is_black(temp)) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
260 |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
261 if (temp == temp->parent->left) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
262 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
263 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
264 if (ngx_rbt_is_red(w)) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
265 ngx_rbt_black(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
266 ngx_rbt_red(temp->parent); |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
267 ngx_rbtree_left_rotate(root, sentinel, temp->parent); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
268 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
269 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
270 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
271 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
272 ngx_rbt_red(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
273 temp = temp->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
274 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
275 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
276 if (ngx_rbt_is_black(w->right)) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
277 ngx_rbt_black(w->left); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
278 ngx_rbt_red(w); |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
279 ngx_rbtree_right_rotate(root, sentinel, w); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
280 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
281 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
282 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
283 ngx_rbt_copy_color(w, temp->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
284 ngx_rbt_black(temp->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
285 ngx_rbt_black(w->right); |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
286 ngx_rbtree_left_rotate(root, sentinel, temp->parent); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
287 temp = *root; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
288 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
289 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
290 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
291 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
292 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
293 if (ngx_rbt_is_red(w)) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
294 ngx_rbt_black(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
295 ngx_rbt_red(temp->parent); |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
296 ngx_rbtree_right_rotate(root, sentinel, temp->parent); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
297 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
298 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
299 |
213
f536f91e8e99
nginx-0.0.1-2003-12-19-15:45:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
212
diff
changeset
|
300 if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
301 ngx_rbt_red(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
302 temp = temp->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
303 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
304 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
305 if (ngx_rbt_is_black(w->left)) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
306 ngx_rbt_black(w->right); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
307 ngx_rbt_red(w); |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
308 ngx_rbtree_left_rotate(root, sentinel, w); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
309 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
310 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
311 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
312 ngx_rbt_copy_color(w, temp->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
313 ngx_rbt_black(temp->parent); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
314 ngx_rbt_black(w->left); |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
315 ngx_rbtree_right_rotate(root, sentinel, temp->parent); |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
316 temp = *root; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
317 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
318 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
319 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
320 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
321 ngx_rbt_black(temp); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
322 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
323 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
324 |
493 | 325 static ngx_inline void |
559 | 326 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
327 ngx_rbtree_node_t *node) | |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
328 { |
559 | 329 ngx_rbtree_node_t *temp; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
330 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
331 temp = node->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
332 node->right = temp->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
333 |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
334 if (temp->left != sentinel) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
335 temp->left->parent = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
336 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
337 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
338 temp->parent = node->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
339 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
340 if (node == *root) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
341 *root = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
342 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
343 } else if (node == node->parent->left) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
344 node->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
345 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
346 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
347 node->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
348 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
349 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
350 temp->left = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
351 node->parent = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
352 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
353 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
354 |
493 | 355 static ngx_inline void |
559 | 356 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
357 ngx_rbtree_node_t *node) | |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
358 { |
559 | 359 ngx_rbtree_node_t *temp; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
360 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
361 temp = node->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
362 node->left = temp->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
363 |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
364 if (temp->right != sentinel) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
365 temp->right->parent = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
366 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
367 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
368 temp->parent = node->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
369 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
370 if (node == *root) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
371 *root = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
372 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
373 } else if (node == node->parent->right) { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
374 node->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
375 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
376 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
377 node->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
378 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
379 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
380 temp->right = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
381 node->parent = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
382 } |