Mercurial > hg > nginx-quic
comparison src/core/ngx_rbtree.c @ 853:a7c8cbb4c55f
rbtree insert procedure
author | Igor Sysoev <igor@sysoev.ru> |
---|---|
date | Thu, 16 Nov 2006 15:34:52 +0000 |
parents | 629b5e4f8931 |
children | 4924b71d77f6 |
comparison
equal
deleted
inserted
replaced
852:629b5e4f8931 | 853:a7c8cbb4c55f |
---|---|
45 *root = node; | 45 *root = node; |
46 | 46 |
47 return; | 47 return; |
48 } | 48 } |
49 | 49 |
50 /* | 50 tree->insert(*root, node, sentinel); |
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 | |
92 | 51 |
93 /* re-balance tree */ | 52 /* re-balance tree */ |
94 | |
95 ngx_rbt_red(node); | |
96 | 53 |
97 while (node != *root && ngx_rbt_is_red(node->parent)) { | 54 while (node != *root && ngx_rbt_is_red(node->parent)) { |
98 | 55 |
99 if (node->parent == node->parent->parent->left) { | 56 if (node->parent == node->parent->parent->left) { |
100 temp = node->parent->parent->right; | 57 temp = node->parent->parent->right; |
134 ngx_rbt_black(node->parent); | 91 ngx_rbt_black(node->parent); |
135 ngx_rbt_red(node->parent->parent); | 92 ngx_rbt_red(node->parent->parent); |
136 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); | 93 ngx_rbtree_left_rotate(root, sentinel, node->parent->parent); |
137 } | 94 } |
138 } | 95 } |
139 | |
140 } | 96 } |
141 | 97 |
142 ngx_rbt_black(*root); | 98 ngx_rbt_black(*root); |
99 } | |
100 | |
101 | |
102 void | |
103 ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node, | |
104 ngx_rbtree_node_t *sentinel) | |
105 { | |
106 for ( ;; ) { | |
107 | |
108 /* | |
109 * Timer values | |
110 * 1) are spread in small range, usually several minutes, | |
111 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits. | |
112 * The comparison takes into account that overflow. | |
113 */ | |
114 | |
115 if ((ngx_rbtree_key_int_t) node->key - (ngx_rbtree_key_int_t) temp->key | |
116 < 0) | |
117 { | |
118 /* node->key < temp->key */ | |
119 | |
120 if (temp->left == sentinel) { | |
121 temp->left = node; | |
122 break; | |
123 } | |
124 | |
125 temp = temp->left; | |
126 | |
127 } else { | |
128 | |
129 if (temp->right == sentinel) { | |
130 temp->right = node; | |
131 break; | |
132 } | |
133 | |
134 temp = temp->right; | |
135 } | |
136 } | |
137 | |
138 node->parent = temp; | |
139 node->left = sentinel; | |
140 node->right = sentinel; | |
141 ngx_rbt_red(node); | |
143 } | 142 } |
144 | 143 |
145 | 144 |
146 void | 145 void |
147 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, | 146 ngx_rbtree_delete(ngx_thread_volatile ngx_rbtree_t *tree, |
148 ngx_rbtree_node_t *node) | 147 ngx_rbtree_node_t *node) |
149 { | 148 { |
150 ngx_int_t red; | 149 ngx_uint_t red; |
151 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; | 150 ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w; |
152 | 151 |
153 /* a binary tree delete */ | 152 /* a binary tree delete */ |
154 | 153 |
155 root = (ngx_rbtree_node_t **) &tree->root; | 154 root = (ngx_rbtree_node_t **) &tree->root; |