Mercurial > hg > nginx-quic
annotate src/core/ngx_rbtree.c @ 836:2ac233efc052
bump version
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Tue, 31 Oct 2006 15:41:41 +0000 |
parents | 4390fcad6628 |
children | 629b5e4f8931 |
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 |
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
|
4 */ |
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 |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
6 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
7 #include <ngx_config.h> |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
8 #include <ngx_core.h> |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
9 |
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 /* |
559 | 12 * The red-black tree code is based on the algorithm described in |
13 * 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
|
14 */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
15 |
206
9aa426375256
nginx-0.0.1-2003-12-05-10:11:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
205
diff
changeset
|
16 #define ngx_rbt_red(node) ((node)->color = 1) |
9aa426375256
nginx-0.0.1-2003-12-05-10:11:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
205
diff
changeset
|
17 #define ngx_rbt_black(node) ((node)->color = 0) |
9aa426375256
nginx-0.0.1-2003-12-05-10:11:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
205
diff
changeset
|
18 #define ngx_rbt_is_red(node) ((node)->color) |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
19 #define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node)) |
206
9aa426375256
nginx-0.0.1-2003-12-05-10:11:46 import
Igor Sysoev <igor@sysoev.ru>
parents:
205
diff
changeset
|
20 #define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color) |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
21 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
22 |
559 | 23 static ngx_inline void ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, |
24 ngx_rbtree_node_t *sentinel, ngx_rbtree_node_t *node); | |
25 static ngx_inline void ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, | |
26 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
|
27 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
28 |
493 | 29 void |
559 | 30 ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree, |
31 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
|
32 { |
559 | 33 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
|
34 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
35 /* a binary tree insert */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
36 |
559 | 37 root = (ngx_rbtree_node_t **) &tree->root; |
38 sentinel = tree->sentinel; | |
39 | |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
40 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
|
41 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
|
42 node->left = sentinel; |
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
43 node->right = sentinel; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
44 ngx_rbt_black(node); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
45 *root = node; |
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 return; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
48 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
49 |
826
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
50 /* |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
51 * The rbtree is currently used by event timers only. Timer values |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
52 * 1) are spread in small range, usually several minutes, |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
53 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
54 * The below comparison takes into account that overflow. |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
55 * |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
56 * If there will be a necessity to use the rbtree for values with |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
57 * other comparison rules, then a whole "for ( ;; )" loop should |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
58 * be made as tree->insert() function. |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
59 */ |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
60 |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
61 temp = *root; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
62 |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
63 for ( ;; ) { |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
64 |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
65 /* node->key < temp->key */ |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
66 |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
67 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
68 < 0) |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
69 { |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
70 if (temp->left == sentinel) { |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
71 temp->left = node; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
72 break; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
73 } |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
74 |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
75 temp = temp->left; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
76 continue; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
77 } |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
78 |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
79 if (temp->right == sentinel) { |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
80 temp->right = node; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
81 break; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
82 } |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
83 |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
84 temp = temp->right; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
85 continue; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
86 } |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
87 |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
88 node->parent = temp; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
89 node->left = sentinel; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
90 node->right = sentinel; |
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
91 |
205
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 /* re-balance tree */ |
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 ngx_rbt_red(node); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
96 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
97 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
|
98 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
99 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
|
100 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
|
101 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
102 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
|
103 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
|
104 ngx_rbt_black(temp); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
105 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
|
106 node = node->parent->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
107 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
108 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
109 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
|
110 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
|
111 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
|
112 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
113 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
114 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
|
115 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
|
116 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
|
117 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
118 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
119 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
120 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
|
121 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
122 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
|
123 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
|
124 ngx_rbt_black(temp); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
125 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
|
126 node = node->parent->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
127 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
128 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
129 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
|
130 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
|
131 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
|
132 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
133 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
134 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
|
135 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
|
136 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
|
137 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
138 } |
826
4390fcad6628
undo the previous wrong commit
Igor Sysoev <igor@sysoev.ru>
parents:
825
diff
changeset
|
139 |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
140 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
141 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
142 ngx_rbt_black(*root); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
143 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
144 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
145 |
493 | 146 void |
559 | 147 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, |
148 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
|
149 { |
559 | 150 ngx_int_t is_red; |
151 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
|
152 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
153 /* a binary tree delete */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
154 |
559 | 155 root = (ngx_rbtree_node_t **) &tree->root; |
156 sentinel = tree->sentinel; | |
157 | |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
158 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
|
159 temp = node->right; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
160 subst = node; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
161 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
162 } 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
|
163 temp = node->left; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
164 subst = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
165 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
166 } else { |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
167 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
|
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 (subst->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 = subst->left; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
171 } else { |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
172 temp = subst->right; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
173 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
174 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
175 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
176 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
|
177 *root = temp; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
178 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
|
179 |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
180 /* DEBUG stuff */ |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
181 node->left = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
182 node->right = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
183 node->parent = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
184 node->key = 0; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
185 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
186 return; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
187 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
188 |
213
f536f91e8e99
nginx-0.0.1-2003-12-19-15:45:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
212
diff
changeset
|
189 is_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
|
190 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
191 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
|
192 subst->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
193 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
194 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
195 subst->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
196 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
197 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
198 if (subst == node) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
199 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
200 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
|
201 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
202 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
203 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
204 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
|
205 temp->parent = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
206 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
207 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
208 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
|
209 } |
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 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
|
212 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
|
213 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
|
214 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
|
215 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
216 if (node == *root) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
217 *root = subst; |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
218 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
219 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
220 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
|
221 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
|
222 } else { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
223 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
|
224 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
225 } |
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 (subst->left != sentinel) { |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
228 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
|
229 } |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
230 |
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
231 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
|
232 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
|
233 } |
229
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
234 |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
235 /* DEBUG stuff */ |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
236 node->left = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
237 node->right = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
238 node->parent = NULL; |
ce6b72fe33fe
nginx-0.0.1-2004-01-15-20:51:49 import
Igor Sysoev <igor@sysoev.ru>
parents:
213
diff
changeset
|
239 node->key = 0; |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
240 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
241 |
213
f536f91e8e99
nginx-0.0.1-2003-12-19-15:45:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
212
diff
changeset
|
242 if (is_red) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
243 return; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
244 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
245 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
246 /* a delete fixup */ |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
247 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
248 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
|
249 |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
250 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
|
251 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
252 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
253 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
|
254 ngx_rbt_black(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
255 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
|
256 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
|
257 w = temp->parent->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
258 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
259 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
260 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
|
261 ngx_rbt_red(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
262 temp = temp->parent; |
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 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
265 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
|
266 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
|
267 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
|
268 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
|
269 w = temp->parent->right; |
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 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
272 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
|
273 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
|
274 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
|
275 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
|
276 temp = *root; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
277 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
278 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
279 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
280 w = temp->parent->left; |
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 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
|
283 ngx_rbt_black(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
284 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
|
285 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
|
286 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
287 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
288 |
213
f536f91e8e99
nginx-0.0.1-2003-12-19-15:45:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
212
diff
changeset
|
289 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
|
290 ngx_rbt_red(w); |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
291 temp = temp->parent; |
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 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
294 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
|
295 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
|
296 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
|
297 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
|
298 w = temp->parent->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
299 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
300 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
301 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
|
302 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
|
303 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
|
304 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
|
305 temp = *root; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
306 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
307 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
308 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
309 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
310 ngx_rbt_black(temp); |
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 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
313 |
493 | 314 static ngx_inline void |
559 | 315 ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
316 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
|
317 { |
559 | 318 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
|
319 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
320 temp = node->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
321 node->right = temp->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
322 |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
323 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
|
324 temp->left->parent = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
325 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
326 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
327 temp->parent = node->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
328 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
329 if (node == *root) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
330 *root = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
331 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
332 } 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
|
333 node->parent->left = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
334 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
335 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
336 node->parent->right = temp; |
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 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
339 temp->left = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
340 node->parent = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
341 } |
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 |
493 | 344 static ngx_inline void |
559 | 345 ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel, |
346 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
|
347 { |
559 | 348 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
|
349 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
350 temp = node->left; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
351 node->left = temp->right; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
352 |
207
6e0fef527732
nginx-0.0.1-2003-12-05-20:07:27 import
Igor Sysoev <igor@sysoev.ru>
parents:
206
diff
changeset
|
353 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
|
354 temp->right->parent = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
355 } |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
356 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
357 temp->parent = node->parent; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
358 |
212
679f60139863
nginx-0.0.1-2003-12-19-11:15:11 import
Igor Sysoev <igor@sysoev.ru>
parents:
207
diff
changeset
|
359 if (node == *root) { |
205
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
360 *root = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
361 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
362 } 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
|
363 node->parent->right = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
364 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
365 } else { |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
366 node->parent->left = temp; |
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 |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
369 temp->right = node; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
370 node->parent = temp; |
4a9a2b1dd6fa
nginx-0.0.1-2003-12-04-17:53:00 import
Igor Sysoev <igor@sysoev.ru>
parents:
diff
changeset
|
371 } |