[bd9baa81] | 1 | /* |
---|
[2b36355b] | 2 | * Copyright (c) 2010-2012 Gedare Bloom. |
---|
[bd9baa81] | 3 | * |
---|
| 4 | * The license and distribution terms for this file may be |
---|
| 5 | * found in the file LICENSE in this distribution or at |
---|
[c499856] | 6 | * http://www.rtems.org/license/LICENSE. |
---|
[bd9baa81] | 7 | */ |
---|
| 8 | |
---|
| 9 | #if HAVE_CONFIG_H |
---|
| 10 | #include "config.h" |
---|
| 11 | #endif |
---|
| 12 | |
---|
[93fb3cb0] | 13 | #include <rtems/score/rbtreeimpl.h> |
---|
[bd9baa81] | 14 | #include <rtems/score/isr.h> |
---|
| 15 | |
---|
| 16 | /** @brief Validate and fix-up tree properties for a new insert/colored node |
---|
| 17 | * |
---|
[dacdda30] | 18 | * This routine checks and fixes the Red-Black Tree properties based on |
---|
[bd9baa81] | 19 | * @a the_node being just added to the tree. |
---|
[dacdda30] | 20 | * |
---|
[bd9baa81] | 21 | * @note It does NOT disable interrupts to ensure the atomicity of the |
---|
| 22 | * append operation. |
---|
| 23 | */ |
---|
[4ea97d24] | 24 | static void _RBTree_Validate_insert( |
---|
[bd9baa81] | 25 | RBTree_Node *the_node |
---|
| 26 | ) |
---|
| 27 | { |
---|
| 28 | RBTree_Node *u,*g; |
---|
| 29 | |
---|
| 30 | /* note: the insert root case is handled already */ |
---|
| 31 | /* if the parent is black, nothing needs to be done |
---|
| 32 | * otherwise may need to loop a few times */ |
---|
| 33 | while (_RBTree_Is_red(_RBTree_Parent(the_node))) { |
---|
| 34 | u = _RBTree_Parent_sibling(the_node); |
---|
| 35 | g = the_node->parent->parent; |
---|
[dacdda30] | 36 | |
---|
[bd9baa81] | 37 | /* if uncle is red, repaint uncle/parent black and grandparent red */ |
---|
| 38 | if(_RBTree_Is_red(u)) { |
---|
| 39 | the_node->parent->color = RBT_BLACK; |
---|
| 40 | u->color = RBT_BLACK; |
---|
| 41 | g->color = RBT_RED; |
---|
| 42 | the_node = g; |
---|
| 43 | } else { /* if uncle is black */ |
---|
| 44 | RBTree_Direction dir = the_node != the_node->parent->child[0]; |
---|
| 45 | RBTree_Direction pdir = the_node->parent != g->child[0]; |
---|
[dacdda30] | 46 | |
---|
[bd9baa81] | 47 | /* ensure node is on the same branch direction as parent */ |
---|
| 48 | if (dir != pdir) { |
---|
| 49 | _RBTree_Rotate(the_node->parent, pdir); |
---|
| 50 | the_node = the_node->child[pdir]; |
---|
| 51 | } |
---|
| 52 | the_node->parent->color = RBT_BLACK; |
---|
| 53 | g->color = RBT_RED; |
---|
[dacdda30] | 54 | |
---|
[bd9baa81] | 55 | /* now rotate grandparent in the other branch direction (toward uncle) */ |
---|
| 56 | _RBTree_Rotate(g, (1-pdir)); |
---|
| 57 | } |
---|
| 58 | } |
---|
| 59 | if(!the_node->parent->parent) the_node->color = RBT_BLACK; |
---|
| 60 | } |
---|
| 61 | |
---|
[4ea97d24] | 62 | RBTree_Node *_RBTree_Insert( |
---|
[64939bc] | 63 | RBTree_Control *the_rbtree, |
---|
| 64 | RBTree_Node *the_node, |
---|
| 65 | RBTree_Compare compare, |
---|
| 66 | bool is_unique |
---|
| 67 | ) |
---|
[bd9baa81] | 68 | { |
---|
| 69 | if(!the_node) return (RBTree_Node*)-1; |
---|
| 70 | |
---|
| 71 | RBTree_Node *iter_node = the_rbtree->root; |
---|
[13c4f853] | 72 | int compare_result; |
---|
[bd9baa81] | 73 | |
---|
| 74 | if (!iter_node) { /* special case: first node inserted */ |
---|
| 75 | the_node->color = RBT_BLACK; |
---|
| 76 | the_rbtree->root = the_node; |
---|
| 77 | the_rbtree->first[0] = the_rbtree->first[1] = the_node; |
---|
| 78 | the_node->parent = (RBTree_Node *) the_rbtree; |
---|
| 79 | the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL; |
---|
[dacdda30] | 80 | } else { |
---|
[bd9baa81] | 81 | /* typical binary search tree insert, descend tree to leaf and insert */ |
---|
| 82 | while (iter_node) { |
---|
[64939bc] | 83 | compare_result = ( *compare )( the_node, iter_node ); |
---|
| 84 | if ( is_unique && _RBTree_Is_equal( compare_result ) ) |
---|
[74f1c73e] | 85 | return iter_node; |
---|
[890358f] | 86 | RBTree_Direction dir = !_RBTree_Is_lesser( compare_result ); |
---|
[bd9baa81] | 87 | if (!iter_node->child[dir]) { |
---|
| 88 | the_node->child[RBT_LEFT] = the_node->child[RBT_RIGHT] = NULL; |
---|
| 89 | the_node->color = RBT_RED; |
---|
| 90 | iter_node->child[dir] = the_node; |
---|
| 91 | the_node->parent = iter_node; |
---|
| 92 | /* update min/max */ |
---|
[64939bc] | 93 | compare_result = ( *compare )( |
---|
| 94 | the_node, |
---|
| 95 | _RBTree_First( the_rbtree, dir ) |
---|
[a41950dd] | 96 | ); |
---|
| 97 | if ( (!dir && _RBTree_Is_lesser(compare_result)) || |
---|
| 98 | (dir && _RBTree_Is_greater(compare_result)) ) { |
---|
[bd9baa81] | 99 | the_rbtree->first[dir] = the_node; |
---|
| 100 | } |
---|
| 101 | break; |
---|
| 102 | } else { |
---|
| 103 | iter_node = iter_node->child[dir]; |
---|
| 104 | } |
---|
| 105 | |
---|
| 106 | } /* while(iter_node) */ |
---|
[dacdda30] | 107 | |
---|
[bd9baa81] | 108 | /* verify red-black properties */ |
---|
[4ea97d24] | 109 | _RBTree_Validate_insert(the_node); |
---|
[bd9baa81] | 110 | } |
---|
| 111 | return (RBTree_Node*)0; |
---|
| 112 | } |
---|