1
2 /*
3 * Copyright (C) Igor Sysoev
4 * Copyright (C) NGINX, Inc.
5 */
6
7
8 #include <nxt_main.h>
9 #include "nxt_rbtree1.h"
10
11
12 /*
13 * The red-black tree code is based on the algorithm described in
14 * the "Introduction to Algorithms" by Cormen, Leiserson and Rivest.
15 */
16
17
18 nxt_inline void nxt_rbtree1_left_rotate(nxt_rbtree1_node_t **root,
19 nxt_rbtree1_node_t *sentinel, nxt_rbtree1_node_t *node);
20 nxt_inline void nxt_rbtree1_right_rotate(nxt_rbtree1_node_t **root,
21 nxt_rbtree1_node_t *sentinel, nxt_rbtree1_node_t *node);
22
23
24 void
nxt_rbtree1_insert(nxt_rbtree1_t * tree,nxt_rbtree1_node_t * node)25 nxt_rbtree1_insert(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node)
26 {
27 nxt_rbtree1_node_t **root, *temp, *sentinel;
28
29 /* a binary tree insert */
30
31 root = (nxt_rbtree1_node_t **) &tree->root;
32 sentinel = tree->sentinel;
33
34 if (*root == sentinel) {
35 node->parent = NULL;
36 node->left = sentinel;
37 node->right = sentinel;
38 nxt_rbtree1_black(node);
39 *root = node;
40
41 return;
42 }
43
44 tree->insert(*root, node, sentinel);
45
46 /* re-balance tree */
47
48 while (node != *root && nxt_rbtree1_is_red(node->parent)) {
49
50 if (node->parent == node->parent->parent->left) {
51 temp = node->parent->parent->right;
52
53 if (nxt_rbtree1_is_red(temp)) {
54 nxt_rbtree1_black(node->parent);
55 nxt_rbtree1_black(temp);
56 nxt_rbtree1_red(node->parent->parent);
57 node = node->parent->parent;
58
59 } else {
60 if (node == node->parent->right) {
61 node = node->parent;
62 nxt_rbtree1_left_rotate(root, sentinel, node);
63 }
64
65 nxt_rbtree1_black(node->parent);
66 nxt_rbtree1_red(node->parent->parent);
67 nxt_rbtree1_right_rotate(root, sentinel, node->parent->parent);
68 }
69
70 } else {
71 temp = node->parent->parent->left;
72
73 if (nxt_rbtree1_is_red(temp)) {
74 nxt_rbtree1_black(node->parent);
75 nxt_rbtree1_black(temp);
76 nxt_rbtree1_red(node->parent->parent);
77 node = node->parent->parent;
78
79 } else {
80 if (node == node->parent->left) {
81 node = node->parent;
82 nxt_rbtree1_right_rotate(root, sentinel, node);
83 }
84
85 nxt_rbtree1_black(node->parent);
86 nxt_rbtree1_red(node->parent->parent);
87 nxt_rbtree1_left_rotate(root, sentinel, node->parent->parent);
88 }
89 }
90 }
91
92 nxt_rbtree1_black(*root);
93 }
94
95
96 void
nxt_rbtree1_insert_value(nxt_rbtree1_node_t * temp,nxt_rbtree1_node_t * node,nxt_rbtree1_node_t * sentinel)97 nxt_rbtree1_insert_value(nxt_rbtree1_node_t *temp, nxt_rbtree1_node_t *node,
98 nxt_rbtree1_node_t *sentinel)
99 {
100 nxt_rbtree1_node_t **p;
101
102 for ( ;; ) {
103
104 p = (node->key < temp->key) ? &temp->left : &temp->right;
105
106 if (*p == sentinel) {
107 break;
108 }
109
110 temp = *p;
111 }
112
113 *p = node;
114 node->parent = temp;
115 node->left = sentinel;
116 node->right = sentinel;
117 nxt_rbtree1_red(node);
118 }
119
120
121 void
nxt_rbtree1_insert_timer_value(nxt_rbtree1_node_t * temp,nxt_rbtree1_node_t * node,nxt_rbtree1_node_t * sentinel)122 nxt_rbtree1_insert_timer_value(nxt_rbtree1_node_t *temp,
123 nxt_rbtree1_node_t *node, nxt_rbtree1_node_t *sentinel)
124 {
125 nxt_rbtree1_node_t **p;
126
127 for ( ;; ) {
128
129 /*
130 * Timer values
131 * 1) are spread in small range, usually several minutes,
132 * 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
133 * The comparison takes into account that overflow.
134 */
135
136 /* node->key < temp->key */
137
138 p = ((nxt_rbtree1_key_int_t) (node->key - temp->key) < 0)
139 ? &temp->left : &temp->right;
140
141 if (*p == sentinel) {
142 break;
143 }
144
145 temp = *p;
146 }
147
148 *p = node;
149 node->parent = temp;
150 node->left = sentinel;
151 node->right = sentinel;
152 nxt_rbtree1_red(node);
153 }
154
155
156 void
nxt_rbtree1_delete(nxt_rbtree1_t * tree,nxt_rbtree1_node_t * node)157 nxt_rbtree1_delete(nxt_rbtree1_t *tree, nxt_rbtree1_node_t *node)
158 {
159 nxt_uint_t red;
160 nxt_rbtree1_node_t **root, *sentinel, *subst, *temp, *w;
161
162 /* a binary tree delete */
163
164 root = (nxt_rbtree1_node_t **) &tree->root;
165 sentinel = tree->sentinel;
166
167 if (node->left == sentinel) {
168 temp = node->right;
169 subst = node;
170
171 } else if (node->right == sentinel) {
172 temp = node->left;
173 subst = node;
174
175 } else {
176 subst = nxt_rbtree1_min(node->right, sentinel);
177
178 if (subst->left != sentinel) {
179 temp = subst->left;
180 } else {
181 temp = subst->right;
182 }
183 }
184
185 if (subst == *root) {
186 *root = temp;
187 nxt_rbtree1_black(temp);
188
189 /* DEBUG stuff */
190 node->left = NULL;
191 node->right = NULL;
192 node->parent = NULL;
193 node->key = 0;
194
195 return;
196 }
197
198 red = nxt_rbtree1_is_red(subst);
199
200 if (subst == subst->parent->left) {
201 subst->parent->left = temp;
202
203 } else {
204 subst->parent->right = temp;
205 }
206
207 if (subst == node) {
208
209 temp->parent = subst->parent;
210
211 } else {
212
213 if (subst->parent == node) {
214 temp->parent = subst;
215
216 } else {
217 temp->parent = subst->parent;
218 }
219
220 subst->left = node->left;
221 subst->right = node->right;
222 subst->parent = node->parent;
223 nxt_rbtree1_copy_color(subst, node);
224
225 if (node == *root) {
226 *root = subst;
227
228 } else {
229 if (node == node->parent->left) {
230 node->parent->left = subst;
231 } else {
232 node->parent->right = subst;
233 }
234 }
235
236 if (subst->left != sentinel) {
237 subst->left->parent = subst;
238 }
239
240 if (subst->right != sentinel) {
241 subst->right->parent = subst;
242 }
243 }
244
245 /* DEBUG stuff */
246 node->left = NULL;
247 node->right = NULL;
248 node->parent = NULL;
249 node->key = 0;
250
251 if (red) {
252 return;
253 }
254
255 /* a delete fixup */
256
257 while (temp != *root && nxt_rbtree1_is_black(temp)) {
258
259 if (temp == temp->parent->left) {
260 w = temp->parent->right;
261
262 if (nxt_rbtree1_is_red(w)) {
263 nxt_rbtree1_black(w);
264 nxt_rbtree1_red(temp->parent);
265 nxt_rbtree1_left_rotate(root, sentinel, temp->parent);
266 w = temp->parent->right;
267 }
268
269 if (nxt_rbtree1_is_black(w->left) && nxt_rbtree1_is_black(w->right))
270 {
271 nxt_rbtree1_red(w);
272 temp = temp->parent;
273
274 } else {
275 if (nxt_rbtree1_is_black(w->right)) {
276 nxt_rbtree1_black(w->left);
277 nxt_rbtree1_red(w);
278 nxt_rbtree1_right_rotate(root, sentinel, w);
279 w = temp->parent->right;
280 }
281
282 nxt_rbtree1_copy_color(w, temp->parent);
283 nxt_rbtree1_black(temp->parent);
284 nxt_rbtree1_black(w->right);
285 nxt_rbtree1_left_rotate(root, sentinel, temp->parent);
286 temp = *root;
287 }
288
289 } else {
290 w = temp->parent->left;
291
292 if (nxt_rbtree1_is_red(w)) {
293 nxt_rbtree1_black(w);
294 nxt_rbtree1_red(temp->parent);
295 nxt_rbtree1_right_rotate(root, sentinel, temp->parent);
296 w = temp->parent->left;
297 }
298
299 if (nxt_rbtree1_is_black(w->left) && nxt_rbtree1_is_black(w->right))
300 {
301 nxt_rbtree1_red(w);
302 temp = temp->parent;
303
304 } else {
305 if (nxt_rbtree1_is_black(w->left)) {
306 nxt_rbtree1_black(w->right);
307 nxt_rbtree1_red(w);
308 nxt_rbtree1_left_rotate(root, sentinel, w);
309 w = temp->parent->left;
310 }
311
312 nxt_rbtree1_copy_color(w, temp->parent);
313 nxt_rbtree1_black(temp->parent);
314 nxt_rbtree1_black(w->left);
315 nxt_rbtree1_right_rotate(root, sentinel, temp->parent);
316 temp = *root;
317 }
318 }
319 }
320
321 nxt_rbtree1_black(temp);
322 }
323
324
325 nxt_inline void
nxt_rbtree1_left_rotate(nxt_rbtree1_node_t ** root,nxt_rbtree1_node_t * sentinel,nxt_rbtree1_node_t * node)326 nxt_rbtree1_left_rotate(nxt_rbtree1_node_t **root, nxt_rbtree1_node_t *sentinel,
327 nxt_rbtree1_node_t *node)
328 {
329 nxt_rbtree1_node_t *temp;
330
331 temp = node->right;
332 node->right = temp->left;
333
334 if (temp->left != sentinel) {
335 temp->left->parent = node;
336 }
337
338 temp->parent = node->parent;
339
340 if (node == *root) {
341 *root = temp;
342
343 } else if (node == node->parent->left) {
344 node->parent->left = temp;
345
346 } else {
347 node->parent->right = temp;
348 }
349
350 temp->left = node;
351 node->parent = temp;
352 }
353
354
355 nxt_inline void
nxt_rbtree1_right_rotate(nxt_rbtree1_node_t ** root,nxt_rbtree1_node_t * sentinel,nxt_rbtree1_node_t * node)356 nxt_rbtree1_right_rotate(nxt_rbtree1_node_t **root,
357 nxt_rbtree1_node_t *sentinel, nxt_rbtree1_node_t *node)
358 {
359 nxt_rbtree1_node_t *temp;
360
361 temp = node->left;
362 node->left = temp->right;
363
364 if (temp->right != sentinel) {
365 temp->right->parent = node;
366 }
367
368 temp->parent = node->parent;
369
370 if (node == *root) {
371 *root = temp;
372
373 } else if (node == node->parent->right) {
374 node->parent->right = temp;
375
376 } else {
377 node->parent->left = temp;
378 }
379
380 temp->right = node;
381 node->parent = temp;
382 }
383