Mercurial > hg > nginx
comparison src/core/ngx_rbtree.c @ 1743:4fc402c3ec73
optimize rbtree initialization and insert
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Mon, 17 Dec 2007 08:52:00 +0000 |
parents | 68cc5e2e1a5d |
children | 3c0b44825071 |
comparison
equal
deleted
inserted
replaced
1742:268b81386fe4 | 1743:4fc402c3ec73 |
---|---|
95 | 95 |
96 void | 96 void |
97 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, | 97 ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, |
98 ngx_rbtree_node_t *sentinel) | 98 ngx_rbtree_node_t *sentinel) |
99 { | 99 { |
100 ngx_rbtree_node_t **p; | |
101 | |
100 for ( ;; ) { | 102 for ( ;; ) { |
101 | 103 |
102 if (node->key < temp->key) { | 104 p = (node->key < temp->key) ? &temp->left : &temp->right; |
103 | 105 |
104 if (temp->left == sentinel) { | 106 if (*p == sentinel) { |
105 temp->left = node; | 107 break; |
106 break; | 108 } |
107 } | 109 |
108 | 110 temp = *p; |
109 temp = temp->left; | 111 } |
110 | 112 |
111 } else { | 113 *p = node; |
112 | |
113 if (temp->right == sentinel) { | |
114 temp->right = node; | |
115 break; | |
116 } | |
117 | |
118 temp = temp->right; | |
119 } | |
120 } | |
121 | |
122 node->parent = temp; | 114 node->parent = temp; |
123 node->left = sentinel; | 115 node->left = sentinel; |
124 node->right = sentinel; | 116 node->right = sentinel; |
125 ngx_rbt_red(node); | 117 ngx_rbt_red(node); |
126 } | 118 } |
128 | 120 |
129 void | 121 void |
130 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, | 122 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, |
131 ngx_rbtree_node_t *sentinel) | 123 ngx_rbtree_node_t *sentinel) |
132 { | 124 { |
125 ngx_rbtree_node_t **p; | |
126 | |
133 for ( ;; ) { | 127 for ( ;; ) { |
134 | 128 |
135 /* | 129 /* |
136 * Timer values | 130 * Timer values |
137 * 1) are spread in small range, usually several minutes, | 131 * 1) are spread in small range, usually several minutes, |
138 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. | 132 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. |
139 * The comparison takes into account that overflow. | 133 * The comparison takes into account that overflow. |
140 */ | 134 */ |
141 | 135 |
142 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key | 136 /* node->key < temp->key */ |
143 < 0) | 137 |
144 { | 138 p = ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key |
145 /* node->key < temp->key */ | 139 < 0) |
146 | 140 ? &temp->left : &temp->right; |
147 if (temp->left == sentinel) { | 141 |
148 temp->left = node; | 142 if (*p == sentinel) { |
149 break; | 143 break; |
150 } | 144 } |
151 | 145 |
152 temp = temp->left; | 146 temp = *p; |
153 | 147 } |
154 } else { | 148 |
155 | 149 *p = node; |
156 if (temp->right == sentinel) { | |
157 temp->right = node; | |
158 break; | |
159 } | |
160 | |
161 temp = temp->right; | |
162 } | |
163 } | |
164 | |
165 node->parent = temp; | 150 node->parent = temp; |
166 node->left = sentinel; | 151 node->left = sentinel; |
167 node->right = sentinel; | 152 node->right = sentinel; |
168 ngx_rbt_red(node); | 153 ngx_rbt_red(node); |
169 } | 154 } |