Mercurial > hg > nginx-quic
comparison src/core/ngx_rbtree.c @ 826:4390fcad6628
undo the previous wrong commit
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Sat, 28 Oct 2006 14:32:39 +0000 |
parents | f9b9b84a8e18 |
children | 629b5e4f8931 |
comparison
equal
deleted
inserted
replaced
825:f9b9b84a8e18 | 826:4390fcad6628 |
---|---|
45 *root = node; | 45 *root = node; |
46 | 46 |
47 return; | 47 return; |
48 } | 48 } |
49 | 49 |
50 tree->insert(*root, node, sentinel); | 50 /* |
51 * The rbtree is currently used by event timers only. Timer values | |
52 * 1) are spread in small range, usually several minutes, | |
53 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. | |
54 * The below comparison takes into account that overflow. | |
55 * | |
56 * If there will be a necessity to use the rbtree for values with | |
57 * other comparison rules, then a whole "for ( ;; )" loop should | |
58 * be made as tree->insert() function. | |
59 */ | |
60 | |
61 temp = *root; | |
62 | |
63 for ( ;; ) { | |
64 | |
65 /* node->key < temp->key */ | |
66 | |
67 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key | |
68 < 0) | |
69 { | |
70 if (temp->left == sentinel) { | |
71 temp->left = node; | |
72 break; | |
73 } | |
74 | |
75 temp = temp->left; | |
76 continue; | |
77 } | |
78 | |
79 if (temp->right == sentinel) { | |
80 temp->right = node; | |
81 break; | |
82 } | |
83 | |
84 temp = temp->right; | |
85 continue; | |
86 } | |
87 | |
88 node->parent = temp; | |
89 node->left = sentinel; | |
90 node->right = sentinel; | |
91 | |
51 | 92 |
52 /* re-balance tree */ | 93 /* re-balance tree */ |
53 | 94 |
54 ngx_rbt_red(node); | 95 ngx_rbt_red(node); |
55 | 96 |
93 ngx_rbt_black(node->parent); | 134 ngx_rbt_black(node->parent); |
94 ngx_rbt_red(node->parent->parent); | 135 ngx_rbt_red(node->parent->parent); |
95 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); | 136 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); |
96 } | 137 } |
97 } | 138 } |
139 | |
98 } | 140 } |
99 | 141 |
100 ngx_rbt_black(*root); | 142 ngx_rbt_black(*root); |
101 } | |
102 | |
103 | |
104 void | |
105 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, | |
106 ngx_rbtree_node_t *sentinel) | |
107 { | |
108 for ( ;; ) { | |
109 | |
110 /* | |
111 * Timer values | |
112 * 1) are spread in small range, usually several minutes, | |
113 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. | |
114 * The comparison takes into account that overflow. | |
115 */ | |
116 | |
117 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key | |
118 < 0) | |
119 { | |
120 /* node->key < temp->key */ | |
121 | |
122 if (temp->left == sentinel) { | |
123 temp->left = node; | |
124 break; | |
125 } | |
126 | |
127 temp = temp->left; | |
128 continue; | |
129 } | |
130 | |
131 if (temp->right == sentinel) { | |
132 temp->right = node; | |
133 break; | |
134 } | |
135 | |
136 temp = temp->right; | |
137 } | |
138 | |
139 node->parent = temp; | |
140 node->left = sentinel; | |
141 node->right = sentinel; | |
142 } | 143 } |
143 | 144 |
144 | 145 |
145 void | 146 void |
146 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, | 147 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, |