Mercurial > hg > nginx

comparison src/core/ngx_rbtree.c @ 1743:4fc402c3ec73

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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 }