/src/leptonica/src/rbtree.c
Line | Count | Source (jump to first uncovered line) |
1 | | /*====================================================================* |
2 | | - Copyright (C) 2001 Leptonica. All rights reserved. |
3 | | - |
4 | | - Redistribution and use in source and binary forms, with or without |
5 | | - modification, are permitted provided that the following conditions |
6 | | - are met: |
7 | | - 1. Redistributions of source code must retain the above copyright |
8 | | - notice, this list of conditions and the following disclaimer. |
9 | | - 2. Redistributions in binary form must reproduce the above |
10 | | - copyright notice, this list of conditions and the following |
11 | | - disclaimer in the documentation and/or other materials |
12 | | - provided with the distribution. |
13 | | - |
14 | | - THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
15 | | - ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
16 | | - LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
17 | | - A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL ANY |
18 | | - CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
19 | | - EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
20 | | - PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
21 | | - PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
22 | | - OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING |
23 | | - NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS |
24 | | - SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
25 | | *====================================================================*/ |
26 | | |
27 | | /* |
28 | | * Modified from the excellent code here: |
29 | | * http://en.literateprograms.org/Red-black_tree_(C)?oldid=19567 |
30 | | * which has been placed in the public domain under the Creative Commons |
31 | | * CC0 1.0 waiver (http://creativecommons.org/publicdomain/zero/1.0/). |
32 | | */ |
33 | | |
34 | | /*! |
35 | | * \file rbtree.c |
36 | | * <pre> |
37 | | * |
38 | | * Basic functions for using red-black trees. These are "nearly" balanced |
39 | | * sorted trees with ordering by key that allows insertion, lookup and |
40 | | * deletion of key/value pairs in log(n) time. |
41 | | * |
42 | | * We use red-black trees to implement our version of: |
43 | | * * a map: a function that maps keys to values (e.g., int64 --> int64). |
44 | | * * a set: a collection that is sorted by unique keys (without |
45 | | * associated values) |
46 | | * |
47 | | * There are 5 invariant properties of RB trees: |
48 | | * (1) Each node is either red or black. |
49 | | * (2) The root node is black. |
50 | | * (3) All leaves are black and contain no data (null). |
51 | | * (4) Every red node has two children and both are black. This is |
52 | | * equivalent to requiring the parent of every red node to be black. |
53 | | * (5) All paths from any given node to its leaf nodes contain the |
54 | | * same number of black nodes. |
55 | | * |
56 | | * Interface to red-black tree |
57 | | * L_RBTREE *l_rbtreeCreate() |
58 | | * RB_TYPE *l_rbtreeLookup() |
59 | | * void l_rbtreeInsert() |
60 | | * void l_rbtreeDelete() |
61 | | * void l_rbtreeDestroy() |
62 | | * L_RBTREE_NODE *l_rbtreeGetFirst() |
63 | | * L_RBTREE_NODE *l_rbtreeGetNext() |
64 | | * L_RBTREE_NODE *l_rbtreeGetLast() |
65 | | * L_RBTREE_NODE *l_rbtreeGetPrev() |
66 | | * l_int32 l_rbtreeGetCount() |
67 | | * void l_rbtreePrint() |
68 | | * |
69 | | * General comparison function |
70 | | * static l_int32 compareKeys() |
71 | | * </pre> |
72 | | */ |
73 | | |
74 | | #ifdef HAVE_CONFIG_H |
75 | | #include <config_auto.h> |
76 | | #endif /* HAVE_CONFIG_H */ |
77 | | |
78 | | #include "allheaders.h" |
79 | | |
80 | | /* The node color enum is only needed in the rbtree implementation */ |
81 | | enum { |
82 | | L_RED_NODE = 1, |
83 | | L_BLACK_NODE = 2 |
84 | | }; |
85 | | |
86 | | /* This makes it simpler to read the code */ |
87 | | typedef L_RBTREE_NODE node; |
88 | | |
89 | | /* Lots of static helper functions */ |
90 | | static void destroy_helper(node *n); |
91 | | static void count_helper(node *n, l_int32 *pcount); |
92 | | static void print_tree_helper(FILE *fp, node *n, l_int32 keytype, |
93 | | l_int32 indent); |
94 | | |
95 | | static l_int32 compareKeys(l_int32 keytype, RB_TYPE left, RB_TYPE right); |
96 | | |
97 | | static node *grandparent(node *n); |
98 | | static node *sibling(node *n); |
99 | | static node *uncle(node *n); |
100 | | static l_int32 node_color(node *n); |
101 | | static node *new_node(RB_TYPE key, RB_TYPE value, l_int32 node_color, |
102 | | node *left, node *right); |
103 | | static node *lookup_node(L_RBTREE *t, RB_TYPE key); |
104 | | static void rotate_left(L_RBTREE *t, node *n); |
105 | | static void rotate_right(L_RBTREE *t, node *n); |
106 | | static void replace_node(L_RBTREE *t, node *oldn, node *newn); |
107 | | static void insert_case1(L_RBTREE *t, node *n); |
108 | | static void insert_case2(L_RBTREE *t, node *n); |
109 | | static void insert_case3(L_RBTREE *t, node *n); |
110 | | static void insert_case4(L_RBTREE *t, node *n); |
111 | | static void insert_case5(L_RBTREE *t, node *n); |
112 | | static node *maximum_node(node *root); |
113 | | static void delete_case1(L_RBTREE *t, node *n); |
114 | | static void delete_case2(L_RBTREE *t, node *n); |
115 | | static void delete_case3(L_RBTREE *t, node *n); |
116 | | static void delete_case4(L_RBTREE *t, node *n); |
117 | | static void delete_case5(L_RBTREE *t, node *n); |
118 | | static void delete_case6(L_RBTREE *t, node *n); |
119 | | static void verify_properties(L_RBTREE *t); |
120 | | |
121 | | #ifndef NO_CONSOLE_IO |
122 | | #define VERIFY_RBTREE 0 /* only for debugging */ |
123 | | #endif /* ~NO_CONSOLE_IO */ |
124 | | |
125 | | /* ------------------------------------------------------------- * |
126 | | * Interface to Red-black Tree * |
127 | | * ------------------------------------------------------------- */ |
128 | | /*! |
129 | | * \brief l_rbtreeCreate() |
130 | | * |
131 | | * \param[in] keytype defined by an enum for an RB_TYPE union |
132 | | * \return rbtree container with empty ptr to the root |
133 | | */ |
134 | | L_RBTREE * |
135 | | l_rbtreeCreate(l_int32 keytype) |
136 | 0 | { |
137 | 0 | L_RBTREE *t; |
138 | |
|
139 | 0 | if (keytype != L_INT_TYPE && keytype != L_UINT_TYPE && |
140 | 0 | keytype != L_FLOAT_TYPE && keytype) |
141 | 0 | return (L_RBTREE *)ERROR_PTR("invalid keytype", __func__, NULL); |
142 | | |
143 | 0 | t = (L_RBTREE *)LEPT_CALLOC(1, sizeof(L_RBTREE)); |
144 | 0 | t->keytype = keytype; |
145 | 0 | verify_properties(t); |
146 | 0 | return t; |
147 | 0 | } |
148 | | |
149 | | /*! |
150 | | * \brief l_rbtreeLookup() |
151 | | * |
152 | | * \param[in] t rbtree, including root node |
153 | | * \param[in] key find a node with this key |
154 | | * \return &value a pointer to a union, if the node exists; else NULL |
155 | | */ |
156 | | RB_TYPE * |
157 | | l_rbtreeLookup(L_RBTREE *t, |
158 | | RB_TYPE key) |
159 | 0 | { |
160 | 0 | node *n; |
161 | |
|
162 | 0 | if (!t) |
163 | 0 | return (RB_TYPE *)ERROR_PTR("tree is null\n", __func__, NULL); |
164 | | |
165 | 0 | n = lookup_node(t, key); |
166 | 0 | return n == NULL ? NULL : &n->value; |
167 | 0 | } |
168 | | |
169 | | /*! |
170 | | * \brief l_rbtreeInsert() |
171 | | * |
172 | | * \param[in] t rbtree, including root node |
173 | | * \param[in] key insert a node with this key, if the key does not |
174 | | * already exist in the tree |
175 | | * \param[in] value typically an int, used for an index |
176 | | * \return void |
177 | | * |
178 | | * <pre> |
179 | | * Notes: |
180 | | * (1) If a node with the key already exists, this just updates the value. |
181 | | * </pre> |
182 | | */ |
183 | | void |
184 | | l_rbtreeInsert(L_RBTREE *t, |
185 | | RB_TYPE key, |
186 | | RB_TYPE value) |
187 | 0 | { |
188 | 0 | node *n, *inserted_node; |
189 | |
|
190 | 0 | if (!t) { |
191 | 0 | L_ERROR("tree is null\n", __func__); |
192 | 0 | return; |
193 | 0 | } |
194 | | |
195 | 0 | inserted_node = new_node(key, value, L_RED_NODE, NULL, NULL); |
196 | 0 | if (t->root == NULL) { |
197 | 0 | t->root = inserted_node; |
198 | 0 | } else { |
199 | 0 | n = t->root; |
200 | 0 | while (1) { |
201 | 0 | int comp_result = compareKeys(t->keytype, key, n->key); |
202 | 0 | if (comp_result == 0) { |
203 | 0 | n->value = value; |
204 | 0 | LEPT_FREE(inserted_node); |
205 | 0 | return; |
206 | 0 | } else if (comp_result < 0) { |
207 | 0 | if (n->left == NULL) { |
208 | 0 | n->left = inserted_node; |
209 | 0 | break; |
210 | 0 | } else { |
211 | 0 | n = n->left; |
212 | 0 | } |
213 | 0 | } else { /* comp_result > 0 */ |
214 | 0 | if (n->right == NULL) { |
215 | 0 | n->right = inserted_node; |
216 | 0 | break; |
217 | 0 | } else { |
218 | 0 | n = n->right; |
219 | 0 | } |
220 | 0 | } |
221 | 0 | } |
222 | 0 | inserted_node->parent = n; |
223 | 0 | } |
224 | 0 | insert_case1(t, inserted_node); |
225 | 0 | verify_properties(t); |
226 | 0 | } |
227 | | |
228 | | /*! |
229 | | * \brief l_rbtreeDelete() |
230 | | * |
231 | | * \param[in] t rbtree, including root node |
232 | | * \param[in] key delete the node with this key |
233 | | * \return void |
234 | | */ |
235 | | void |
236 | | l_rbtreeDelete(L_RBTREE *t, |
237 | | RB_TYPE key) |
238 | 0 | { |
239 | 0 | node *n, *child; |
240 | |
|
241 | 0 | if (!t) { |
242 | 0 | L_ERROR("tree is null\n", __func__); |
243 | 0 | return; |
244 | 0 | } |
245 | | |
246 | 0 | n = lookup_node(t, key); |
247 | 0 | if (n == NULL) return; /* Key not found, do nothing */ |
248 | 0 | if (n->left != NULL && n->right != NULL) { |
249 | | /* Copy key/value from predecessor and then delete it instead */ |
250 | 0 | node *pred = maximum_node(n->left); |
251 | 0 | n->key = pred->key; |
252 | 0 | n->value = pred->value; |
253 | 0 | n = pred; |
254 | 0 | } |
255 | | |
256 | | /* n->left == NULL || n->right == NULL */ |
257 | 0 | child = n->right == NULL ? n->left : n->right; |
258 | 0 | if (node_color(n) == L_BLACK_NODE) { |
259 | 0 | n->color = node_color(child); |
260 | 0 | delete_case1(t, n); |
261 | 0 | } |
262 | 0 | replace_node(t, n, child); |
263 | 0 | if (n->parent == NULL && child != NULL) /* root should be black */ |
264 | 0 | child->color = L_BLACK_NODE; |
265 | 0 | LEPT_FREE(n); |
266 | |
|
267 | 0 | verify_properties(t); |
268 | 0 | } |
269 | | |
270 | | /*! |
271 | | * \brief l_rbtreeDestroy() |
272 | | * |
273 | | * \param[in] pt pointer to tree; will be wet to null before returning |
274 | | * \return void |
275 | | * |
276 | | * <pre> |
277 | | * Notes: |
278 | | * (1) Destroys the tree and nulls the input tree ptr. |
279 | | * </pre> |
280 | | */ |
281 | | void |
282 | | l_rbtreeDestroy(L_RBTREE **pt) |
283 | 0 | { |
284 | 0 | node *n; |
285 | |
|
286 | 0 | if (!pt) return; |
287 | 0 | if (*pt == NULL) return; |
288 | 0 | n = (*pt)->root; |
289 | 0 | destroy_helper(n); |
290 | 0 | LEPT_FREE(*pt); |
291 | 0 | *pt = NULL; |
292 | 0 | } |
293 | | |
294 | | /* postorder DFS */ |
295 | | static void |
296 | | destroy_helper(node *n) |
297 | 0 | { |
298 | 0 | if (!n) return; |
299 | 0 | destroy_helper(n->left); |
300 | 0 | destroy_helper(n->right); |
301 | 0 | LEPT_FREE(n); |
302 | 0 | } |
303 | | |
304 | | /*! |
305 | | * \brief l_rbtreeGetFirst() |
306 | | * |
307 | | * \param[in] t rbtree, including root node |
308 | | * \return first node, or NULL on error or if the tree is empty |
309 | | * |
310 | | * <pre> |
311 | | * Notes: |
312 | | * (1) This is the first node in an in-order traversal. |
313 | | * </pre> |
314 | | */ |
315 | | L_RBTREE_NODE * |
316 | | l_rbtreeGetFirst(L_RBTREE *t) |
317 | 0 | { |
318 | 0 | node *n; |
319 | |
|
320 | 0 | if (!t) |
321 | 0 | return (L_RBTREE_NODE *)ERROR_PTR("tree is null", __func__, NULL); |
322 | 0 | if (t->root == NULL) { |
323 | 0 | L_INFO("tree is empty\n", __func__); |
324 | 0 | return NULL; |
325 | 0 | } |
326 | | |
327 | | /* Just go down the left side as far as possible */ |
328 | 0 | n = t->root; |
329 | 0 | while (n && n->left) |
330 | 0 | n = n->left; |
331 | 0 | return n; |
332 | 0 | } |
333 | | |
334 | | /*! |
335 | | * \brief l_rbtreeGetNext() |
336 | | * |
337 | | * \param[in] n current node |
338 | | * \return next node, or NULL if it's the last node |
339 | | * |
340 | | * <pre> |
341 | | * Notes: |
342 | | * (1) This finds the next node, in an in-order traversal, from |
343 | | * the current node. |
344 | | * (2) It is useful as an iterator for a map. |
345 | | * (3) Call l_rbtreeGetFirst() to get the first node. |
346 | | * </pre> |
347 | | */ |
348 | | L_RBTREE_NODE * |
349 | | l_rbtreeGetNext(L_RBTREE_NODE *n) |
350 | 0 | { |
351 | 0 | if (!n) |
352 | 0 | return (L_RBTREE_NODE *)ERROR_PTR("n not defined", __func__, NULL); |
353 | | |
354 | | /* If there is a right child, go to it, and then go left all the |
355 | | * way to the end. Otherwise go up to the parent; continue upward |
356 | | * as long as you're on the right branch, but stop at the parent |
357 | | * when you hit it from the left branch. */ |
358 | 0 | if (n->right) { |
359 | 0 | n = n->right; |
360 | 0 | while (n->left) |
361 | 0 | n = n->left; |
362 | 0 | return n; |
363 | 0 | } else { |
364 | 0 | while (n->parent && n->parent->right == n) |
365 | 0 | n = n->parent; |
366 | 0 | return n->parent; |
367 | 0 | } |
368 | 0 | } |
369 | | |
370 | | /*! |
371 | | * \brief l_rbtreeGetLast() |
372 | | * |
373 | | * \param[in] t rbtree, including root node |
374 | | * \return last node, or NULL on error or if the tree is empty |
375 | | * |
376 | | * <pre> |
377 | | * Notes: |
378 | | * (1) This is the last node in an in-order traversal. |
379 | | * </pre> |
380 | | */ |
381 | | L_RBTREE_NODE * |
382 | | l_rbtreeGetLast(L_RBTREE *t) |
383 | 0 | { |
384 | 0 | node *n; |
385 | |
|
386 | 0 | if (!t) |
387 | 0 | return (L_RBTREE_NODE *)ERROR_PTR("tree is null", __func__, NULL); |
388 | 0 | if (t->root == NULL) { |
389 | 0 | L_INFO("tree is empty\n", __func__); |
390 | 0 | return NULL; |
391 | 0 | } |
392 | | |
393 | | /* Just go down the right side as far as possible */ |
394 | 0 | n = t->root; |
395 | 0 | while (n && n->right) |
396 | 0 | n = n->right; |
397 | 0 | return n; |
398 | 0 | } |
399 | | |
400 | | /*! |
401 | | * \brief l_rbtreeGetPrev() |
402 | | * |
403 | | * \param[in] n current node |
404 | | * \return next node, or NULL if it's the first node |
405 | | * |
406 | | * <pre> |
407 | | * Notes: |
408 | | * (1) This finds the previous node, in an in-order traversal, from |
409 | | * the current node. |
410 | | * (2) It is useful as an iterator for a map. |
411 | | * (3) Call l_rbtreeGetLast() to get the last node. |
412 | | * </pre> |
413 | | */ |
414 | | L_RBTREE_NODE * |
415 | | l_rbtreeGetPrev(L_RBTREE_NODE *n) |
416 | 0 | { |
417 | 0 | if (!n) |
418 | 0 | return (L_RBTREE_NODE *)ERROR_PTR("n not defined", __func__, NULL); |
419 | | |
420 | | /* If there is a left child, go to it, and then go right all the |
421 | | * way to the end. Otherwise go up to the parent; continue upward |
422 | | * as long as you're on the left branch, but stop at the parent |
423 | | * when you hit it from the right branch. */ |
424 | 0 | if (n->left) { |
425 | 0 | n = n->left; |
426 | 0 | while (n->right) |
427 | 0 | n = n->right; |
428 | 0 | return n; |
429 | 0 | } else { |
430 | 0 | while (n->parent && n->parent->left == n) |
431 | 0 | n = n->parent; |
432 | 0 | return n->parent; |
433 | 0 | } |
434 | 0 | } |
435 | | |
436 | | /*! |
437 | | * \brief l_rbtreeGetCount() |
438 | | * |
439 | | * \param[in] t rbtree |
440 | | * \return count the number of nodes in the tree, or 0 on error |
441 | | */ |
442 | | l_int32 |
443 | | l_rbtreeGetCount(L_RBTREE *t) |
444 | 0 | { |
445 | 0 | l_int32 count = 0; |
446 | 0 | node *n; |
447 | |
|
448 | 0 | if (!t) return 0; |
449 | 0 | n = t->root; |
450 | 0 | count_helper(n, &count); |
451 | 0 | return count; |
452 | 0 | } |
453 | | |
454 | | /* preorder DFS */ |
455 | | static void |
456 | | count_helper(node *n, l_int32 *pcount) |
457 | 0 | { |
458 | 0 | if (n) |
459 | 0 | (*pcount)++; |
460 | 0 | else |
461 | 0 | return; |
462 | | |
463 | 0 | count_helper(n->left, pcount); |
464 | 0 | count_helper(n->right, pcount); |
465 | 0 | } |
466 | | |
467 | | |
468 | | /*! |
469 | | * \brief l_rbtreePrint() |
470 | | * |
471 | | * \param[in] fp file stream |
472 | | * \param[in] t rbtree |
473 | | * \return void |
474 | | */ |
475 | | void |
476 | | l_rbtreePrint(FILE *fp, |
477 | | L_RBTREE *t) |
478 | 0 | { |
479 | 0 | if (!fp) { |
480 | 0 | L_ERROR("stream not defined\n", __func__); |
481 | 0 | return; |
482 | 0 | } |
483 | 0 | if (!t) { |
484 | 0 | L_ERROR("tree not defined\n", __func__); |
485 | 0 | return; |
486 | 0 | } |
487 | | |
488 | 0 | print_tree_helper(fp, t->root, t->keytype, 0); |
489 | 0 | fprintf(fp, "\n"); |
490 | 0 | } |
491 | | |
492 | 0 | #define INDENT_STEP 4 |
493 | | |
494 | | static void |
495 | | print_tree_helper(FILE *fp, |
496 | | node *n, |
497 | | l_int32 keytype, |
498 | | l_int32 indent) |
499 | 0 | { |
500 | 0 | l_int32 i; |
501 | |
|
502 | 0 | if (n == NULL) { |
503 | 0 | fprintf(fp, "<empty tree>"); |
504 | 0 | return; |
505 | 0 | } |
506 | 0 | if (n->right != NULL) { |
507 | 0 | print_tree_helper(fp, n->right, keytype, indent + INDENT_STEP); |
508 | 0 | } |
509 | 0 | for (i = 0; i < indent; i++) |
510 | 0 | fprintf(fp, " "); |
511 | 0 | if (n->color == L_BLACK_NODE) { |
512 | 0 | if (keytype == L_INT_TYPE) |
513 | 0 | fprintf(fp, "%lld\n", n->key.itype); |
514 | 0 | else if (keytype == L_UINT_TYPE) |
515 | 0 | fprintf(fp, "%llx\n", n->key.utype); |
516 | 0 | else if (keytype == L_FLOAT_TYPE) |
517 | 0 | fprintf(fp, "%f\n", n->key.ftype); |
518 | 0 | } else { |
519 | 0 | if (keytype == L_INT_TYPE) |
520 | 0 | fprintf(fp, "<%lld>\n", n->key.itype); |
521 | 0 | else if (keytype == L_UINT_TYPE) |
522 | 0 | fprintf(fp, "<%llx>\n", n->key.utype); |
523 | 0 | else if (keytype == L_FLOAT_TYPE) |
524 | 0 | fprintf(fp, "<%f>\n", n->key.ftype); |
525 | 0 | } |
526 | 0 | if (n->left != NULL) { |
527 | 0 | print_tree_helper(fp, n->left, keytype, indent + INDENT_STEP); |
528 | 0 | } |
529 | 0 | } |
530 | | |
531 | | |
532 | | /* ------------------------------------------------------------- * |
533 | | * Static key comparison function * |
534 | | * ------------------------------------------------------------- */ |
535 | | static l_int32 |
536 | | compareKeys(l_int32 keytype, |
537 | | RB_TYPE left, |
538 | | RB_TYPE right) |
539 | 0 | { |
540 | 0 | if (keytype == L_INT_TYPE) { |
541 | 0 | if (left.itype < right.itype) |
542 | 0 | return -1; |
543 | 0 | else if (left.itype > right.itype) |
544 | 0 | return 1; |
545 | 0 | else { /* equality */ |
546 | 0 | return 0; |
547 | 0 | } |
548 | 0 | } else if (keytype == L_UINT_TYPE) { |
549 | 0 | if (left.utype < right.utype) |
550 | 0 | return -1; |
551 | 0 | else if (left.utype > right.utype) |
552 | 0 | return 1; |
553 | 0 | else { /* equality */ |
554 | 0 | return 0; |
555 | 0 | } |
556 | 0 | } else if (keytype == L_FLOAT_TYPE) { |
557 | 0 | if (left.ftype < right.ftype) |
558 | 0 | return -1; |
559 | 0 | else if (left.ftype > right.ftype) |
560 | 0 | return 1; |
561 | 0 | else { /* equality */ |
562 | 0 | return 0; |
563 | 0 | } |
564 | 0 | } else { |
565 | 0 | L_ERROR("unknown keytype %d\n", __func__, keytype); |
566 | 0 | return 0; |
567 | 0 | } |
568 | 0 | } |
569 | | |
570 | | |
571 | | /* ------------------------------------------------------------- * |
572 | | * Static red-black tree helpers * |
573 | | * ------------------------------------------------------------- */ |
574 | 0 | static node *grandparent(node *n) { |
575 | 0 | if (!n || !n->parent || !n->parent->parent) { |
576 | 0 | L_ERROR("root and child of root have no grandparent\n", "grandparent"); |
577 | 0 | return NULL; |
578 | 0 | } |
579 | 0 | return n->parent->parent; |
580 | 0 | } |
581 | | |
582 | 0 | static node *sibling(node *n) { |
583 | 0 | if (!n || !n->parent) { |
584 | 0 | L_ERROR("root has no sibling\n", "sibling"); |
585 | 0 | return NULL; |
586 | 0 | } |
587 | 0 | if (n == n->parent->left) |
588 | 0 | return n->parent->right; |
589 | 0 | else |
590 | 0 | return n->parent->left; |
591 | 0 | } |
592 | | |
593 | 0 | static node *uncle(node *n) { |
594 | 0 | if (!n || !n->parent || !n->parent->parent) { |
595 | 0 | L_ERROR("root and child of root have no uncle\n", "uncle"); |
596 | 0 | return NULL; |
597 | 0 | } |
598 | 0 | return sibling(n->parent); |
599 | 0 | } |
600 | | |
601 | 0 | static l_int32 node_color(node *n) { |
602 | 0 | return n == NULL ? L_BLACK_NODE : n->color; |
603 | 0 | } |
604 | | |
605 | | |
606 | | static node *new_node(RB_TYPE key, RB_TYPE value, l_int32 node_color, |
607 | 0 | node *left, node *right) { |
608 | 0 | node *result = (node *)LEPT_CALLOC(1, sizeof(node)); |
609 | 0 | result->key = key; |
610 | 0 | result->value = value; |
611 | 0 | result->color = node_color; |
612 | 0 | result->left = left; |
613 | 0 | result->right = right; |
614 | 0 | if (left != NULL) left->parent = result; |
615 | 0 | if (right != NULL) right->parent = result; |
616 | 0 | result->parent = NULL; |
617 | 0 | return result; |
618 | 0 | } |
619 | | |
620 | 0 | static node *lookup_node(L_RBTREE *t, RB_TYPE key) { |
621 | 0 | node *n = t->root; |
622 | 0 | while (n != NULL) { |
623 | 0 | int comp_result = compareKeys(t->keytype, key, n->key); |
624 | 0 | if (comp_result == 0) { |
625 | 0 | return n; |
626 | 0 | } else if (comp_result < 0) { |
627 | 0 | n = n->left; |
628 | 0 | } else { /* comp_result > 0 */ |
629 | 0 | n = n->right; |
630 | 0 | } |
631 | 0 | } |
632 | 0 | return n; |
633 | 0 | } |
634 | | |
635 | 0 | static void rotate_left(L_RBTREE *t, node *n) { |
636 | 0 | node *r = n->right; |
637 | 0 | replace_node(t, n, r); |
638 | 0 | n->right = r->left; |
639 | 0 | if (r->left != NULL) { |
640 | 0 | r->left->parent = n; |
641 | 0 | } |
642 | 0 | r->left = n; |
643 | 0 | n->parent = r; |
644 | 0 | } |
645 | | |
646 | 0 | static void rotate_right(L_RBTREE *t, node *n) { |
647 | 0 | node *L = n->left; |
648 | 0 | replace_node(t, n, L); |
649 | 0 | n->left = L->right; |
650 | 0 | if (L->right != NULL) { |
651 | 0 | L->right->parent = n; |
652 | 0 | } |
653 | 0 | L->right = n; |
654 | 0 | n->parent = L; |
655 | 0 | } |
656 | | |
657 | 0 | static void replace_node(L_RBTREE *t, node *oldn, node *newn) { |
658 | 0 | if (oldn->parent == NULL) { |
659 | 0 | t->root = newn; |
660 | 0 | } else { |
661 | 0 | if (oldn == oldn->parent->left) |
662 | 0 | oldn->parent->left = newn; |
663 | 0 | else |
664 | 0 | oldn->parent->right = newn; |
665 | 0 | } |
666 | 0 | if (newn != NULL) { |
667 | 0 | newn->parent = oldn->parent; |
668 | 0 | } |
669 | 0 | } |
670 | | |
671 | 0 | static void insert_case1(L_RBTREE *t, node *n) { |
672 | 0 | if (n->parent == NULL) |
673 | 0 | n->color = L_BLACK_NODE; |
674 | 0 | else |
675 | 0 | insert_case2(t, n); |
676 | 0 | } |
677 | | |
678 | 0 | static void insert_case2(L_RBTREE *t, node *n) { |
679 | 0 | if (node_color(n->parent) == L_BLACK_NODE) |
680 | 0 | return; /* Tree is still valid */ |
681 | 0 | else |
682 | 0 | insert_case3(t, n); |
683 | 0 | } |
684 | | |
685 | 0 | static void insert_case3(L_RBTREE *t, node *n) { |
686 | 0 | if (node_color(uncle(n)) == L_RED_NODE) { |
687 | 0 | n->parent->color = L_BLACK_NODE; |
688 | 0 | uncle(n)->color = L_BLACK_NODE; |
689 | 0 | grandparent(n)->color = L_RED_NODE; |
690 | 0 | insert_case1(t, grandparent(n)); |
691 | 0 | } else { |
692 | 0 | insert_case4(t, n); |
693 | 0 | } |
694 | 0 | } |
695 | | |
696 | 0 | static void insert_case4(L_RBTREE *t, node *n) { |
697 | 0 | if (n == n->parent->right && n->parent == grandparent(n)->left) { |
698 | 0 | rotate_left(t, n->parent); |
699 | 0 | n = n->left; |
700 | 0 | } else if (n == n->parent->left && n->parent == grandparent(n)->right) { |
701 | 0 | rotate_right(t, n->parent); |
702 | 0 | n = n->right; |
703 | 0 | } |
704 | 0 | insert_case5(t, n); |
705 | 0 | } |
706 | | |
707 | 0 | static void insert_case5(L_RBTREE *t, node *n) { |
708 | 0 | n->parent->color = L_BLACK_NODE; |
709 | 0 | grandparent(n)->color = L_RED_NODE; |
710 | 0 | if (n == n->parent->left && n->parent == grandparent(n)->left) { |
711 | 0 | rotate_right(t, grandparent(n)); |
712 | 0 | } else if (n == n->parent->right && n->parent == grandparent(n)->right) { |
713 | 0 | rotate_left(t, grandparent(n)); |
714 | 0 | } else { |
715 | 0 | L_ERROR("identity confusion\n", "insert_case5"); |
716 | 0 | } |
717 | 0 | } |
718 | | |
719 | 0 | static node *maximum_node(node *n) { |
720 | 0 | if (!n) { |
721 | 0 | L_ERROR("n not defined\n", "maximum_node"); |
722 | 0 | return NULL; |
723 | 0 | } |
724 | 0 | while (n->right != NULL) { |
725 | 0 | n = n->right; |
726 | 0 | } |
727 | 0 | return n; |
728 | 0 | } |
729 | | |
730 | 0 | static void delete_case1(L_RBTREE *t, node *n) { |
731 | 0 | if (n->parent == NULL) |
732 | 0 | return; |
733 | 0 | else |
734 | 0 | delete_case2(t, n); |
735 | 0 | } |
736 | | |
737 | 0 | static void delete_case2(L_RBTREE *t, node *n) { |
738 | 0 | if (node_color(sibling(n)) == L_RED_NODE) { |
739 | 0 | n->parent->color = L_RED_NODE; |
740 | 0 | sibling(n)->color = L_BLACK_NODE; |
741 | 0 | if (n == n->parent->left) |
742 | 0 | rotate_left(t, n->parent); |
743 | 0 | else |
744 | 0 | rotate_right(t, n->parent); |
745 | 0 | } |
746 | 0 | delete_case3(t, n); |
747 | 0 | } |
748 | | |
749 | 0 | static void delete_case3(L_RBTREE *t, node *n) { |
750 | 0 | if (node_color(n->parent) == L_BLACK_NODE && |
751 | 0 | node_color(sibling(n)) == L_BLACK_NODE && |
752 | 0 | node_color(sibling(n)->left) == L_BLACK_NODE && |
753 | 0 | node_color(sibling(n)->right) == L_BLACK_NODE) { |
754 | 0 | sibling(n)->color = L_RED_NODE; |
755 | 0 | delete_case1(t, n->parent); |
756 | 0 | } else { |
757 | 0 | delete_case4(t, n); |
758 | 0 | } |
759 | 0 | } |
760 | | |
761 | 0 | static void delete_case4(L_RBTREE *t, node *n) { |
762 | 0 | if (node_color(n->parent) == L_RED_NODE && |
763 | 0 | node_color(sibling(n)) == L_BLACK_NODE && |
764 | 0 | node_color(sibling(n)->left) == L_BLACK_NODE && |
765 | 0 | node_color(sibling(n)->right) == L_BLACK_NODE) { |
766 | 0 | sibling(n)->color = L_RED_NODE; |
767 | 0 | n->parent->color = L_BLACK_NODE; |
768 | 0 | } else { |
769 | 0 | delete_case5(t, n); |
770 | 0 | } |
771 | 0 | } |
772 | | |
773 | 0 | static void delete_case5(L_RBTREE *t, node *n) { |
774 | 0 | if (n == n->parent->left && |
775 | 0 | node_color(sibling(n)) == L_BLACK_NODE && |
776 | 0 | node_color(sibling(n)->left) == L_RED_NODE && |
777 | 0 | node_color(sibling(n)->right) == L_BLACK_NODE) { |
778 | 0 | sibling(n)->color = L_RED_NODE; |
779 | 0 | sibling(n)->left->color = L_BLACK_NODE; |
780 | 0 | rotate_right(t, sibling(n)); |
781 | 0 | } else if (n == n->parent->right && |
782 | 0 | node_color(sibling(n)) == L_BLACK_NODE && |
783 | 0 | node_color(sibling(n)->right) == L_RED_NODE && |
784 | 0 | node_color(sibling(n)->left) == L_BLACK_NODE) { |
785 | 0 | sibling(n)->color = L_RED_NODE; |
786 | 0 | sibling(n)->right->color = L_BLACK_NODE; |
787 | 0 | rotate_left(t, sibling(n)); |
788 | 0 | } |
789 | 0 | delete_case6(t, n); |
790 | 0 | } |
791 | | |
792 | 0 | static void delete_case6(L_RBTREE *t, node *n) { |
793 | 0 | sibling(n)->color = node_color(n->parent); |
794 | 0 | n->parent->color = L_BLACK_NODE; |
795 | 0 | if (n == n->parent->left) { |
796 | 0 | if (node_color(sibling(n)->right) != L_RED_NODE) { |
797 | 0 | L_ERROR("right sibling is not RED", "delete_case6"); |
798 | 0 | return; |
799 | 0 | } |
800 | 0 | sibling(n)->right->color = L_BLACK_NODE; |
801 | 0 | rotate_left(t, n->parent); |
802 | 0 | } else { |
803 | 0 | if (node_color(sibling(n)->left) != L_RED_NODE) { |
804 | 0 | L_ERROR("left sibling is not RED", "delete_case6"); |
805 | 0 | return; |
806 | 0 | } |
807 | 0 | sibling(n)->left->color = L_BLACK_NODE; |
808 | 0 | rotate_right(t, n->parent); |
809 | 0 | } |
810 | 0 | } |
811 | | |
812 | | |
813 | | /* ------------------------------------------------------------- * |
814 | | * Debugging: verify if tree is valid * |
815 | | * ------------------------------------------------------------- */ |
816 | | #if VERIFY_RBTREE |
817 | | static void verify_property_1(node *root); |
818 | | static void verify_property_2(node *root); |
819 | | static void verify_property_4(node *root); |
820 | | static void verify_property_5(node *root); |
821 | | static void verify_property_5_helper(node *n, int black_count, |
822 | | int* black_count_path); |
823 | | #endif |
824 | | |
825 | 0 | static void verify_properties(L_RBTREE *t) { |
826 | | #if VERIFY_RBTREE |
827 | | verify_property_1(t->root); |
828 | | verify_property_2(t->root); |
829 | | /* Property 3 is implicit */ |
830 | | verify_property_4(t->root); |
831 | | verify_property_5(t->root); |
832 | | #endif |
833 | 0 | } |
834 | | |
835 | | #if VERIFY_RBTREE |
836 | | static void verify_property_1(node *n) { |
837 | | if (node_color(n) != L_RED_NODE && node_color(n) != L_BLACK_NODE) { |
838 | | L_ERROR("color neither RED nor BLACK\n", "verify_property_1"); |
839 | | return; |
840 | | } |
841 | | if (n == NULL) return; |
842 | | verify_property_1(n->left); |
843 | | verify_property_1(n->right); |
844 | | } |
845 | | |
846 | | static void verify_property_2(node *root) { |
847 | | if (node_color(root) != L_BLACK_NODE) |
848 | | L_ERROR("root is not black!\n", "verify_property_2"); |
849 | | } |
850 | | |
851 | | static void verify_property_4(node *n) { |
852 | | if (node_color(n) == L_RED_NODE) { |
853 | | if (node_color(n->left) != L_BLACK_NODE || |
854 | | node_color(n->right) != L_BLACK_NODE || |
855 | | node_color(n->parent) != L_BLACK_NODE) { |
856 | | L_ERROR("children & parent not all BLACK", "verify_property_4"); |
857 | | return; |
858 | | } |
859 | | } |
860 | | if (n == NULL) return; |
861 | | verify_property_4(n->left); |
862 | | verify_property_4(n->right); |
863 | | } |
864 | | |
865 | | static void verify_property_5(node *root) { |
866 | | int black_count_path = -1; |
867 | | verify_property_5_helper(root, 0, &black_count_path); |
868 | | } |
869 | | |
870 | | static void verify_property_5_helper(node *n, int black_count, |
871 | | int* path_black_count) { |
872 | | if (node_color(n) == L_BLACK_NODE) { |
873 | | black_count++; |
874 | | } |
875 | | if (n == NULL) { |
876 | | if (*path_black_count == -1) { |
877 | | *path_black_count = black_count; |
878 | | } else if (*path_black_count != black_count) { |
879 | | L_ERROR("incorrect black count", "verify_property_5_helper"); |
880 | | } |
881 | | return; |
882 | | } |
883 | | verify_property_5_helper(n->left, black_count, path_black_count); |
884 | | verify_property_5_helper(n->right, black_count, path_black_count); |
885 | | } |
886 | | #endif |