rtems-omk-template/appfoo/rbtree.c

   1 #include <rtems/score/rbtree.h>
   2 #include <rtems/score/thread.h>
   3 #include "edf_types.h"
   4
   5
   6 static void _Rotate_Left(
   7    EDF_Chain_Control *chain,
   8    EDF_Node *node
   9 )
  10 {
  11    EDF_Node *right = node->right;
  12
  13    if ((node->right = right->left))
  14         right->left->parent = node;
  15    right->left = node;
  16    if ((right->parent = node->parent))
  17    {
  18         if (node == node->parent->left)
  19                 node->parent->left = right;
  20         else
  21                 node->parent->right = right;
  22    }
  23    else
  24         chain->root = right;
  25    node->parent = right;
  26 }
  27
  28 static void _Rotate_Right(
  29    EDF_Chain_Control *chain,
  30    EDF_Node *node
  31 )
  32 {
  33    EDF_Node *left = node->left;
  34
  35    if ((node->left = left->right))
  36         left->right->parent = node;
  37    left->right = node;
  38
  39    if ((left->parent = node->parent))
  40    {
  41         if (node == node->parent->right)
  42                 node->parent->right = left;
  43         else
  44                 node->parent->left = left;
  45    }
  46    else
  47         chain->root = left;
  48    node->parent = left;
  49 }
  50
  51 void _RBT_Insert(
  52    EDF_Chain_Control *chain,
  53    EDF_Node *node
  54 )
  55 {
  56    EDF_Node *parent, *child, *uncle, *gparent, *tmp;
  57
  58    parent = NULL;
  59    child = chain->root;
  60
  61    /* Insert new node into tree */
  62
  63    while (child)
  64    {
  65            parent = child;
  66            child = ( node->abs_deadline < child->abs_deadline ) \
  67                    ? child->left : child->right;
  68    }
  69
  70    node->parent = parent;
  71    node->left = NULL;
  72    node->right = NULL;
  73    node->color = RED;
  74
  75    if (parent)
  76    {
  77            if ( node->abs_deadline < parent->abs_deadline )
  78            {
  79                    parent->left = node;
  80                    if ( parent == chain->first ) chain->first = node;
  81            }
  82            else parent->right = node;
  83    } else
  84    {
  85            chain->root = node;
  86            chain->first = node;
  87    }
  88
  89    /* Insert_FixUp */
  90    /* check and fix red-back properties eventually */
  91    while ((parent = node->parent) && parent->color == RED)
  92    {
  93            gparent = parent->parent;
  94
  95            if (parent == gparent->left)
  96            {
  97                    uncle = gparent->right;
  98
  99                    if ( uncle && uncle->color == RED)
 100                    {
 101                            parent->color = BLACK;
 102                            uncle->color = BLACK;
 103                            gparent->color = RED;
 104                            node = gparent;
 105                            continue;
 106                    }
 107
 108                    if (node == parent->right)
 109                    {
 110                            _Rotate_Left(chain,parent);
 111                            tmp = parent;
 112                            parent = node;
 113                            node = tmp;
 114                    }
 115
 116                    parent->color = BLACK;
 117                    gparent->color = RED;
 118                    _Rotate_Right(chain, gparent);
 119
 120            } else {
 121                    uncle = gparent->left;
 122
 123                    if (uncle && uncle->color == RED )
 124                    {
 125                            parent->color = BLACK;
 126                            uncle->color = BLACK;
 127                            gparent->color = RED;
 128                            node = parent->parent;
 129                            continue;
 130                    }
 131
 132                    if (node == parent->left)
 133                    {
 134                            _Rotate_Right(chain, parent);
 135                            tmp = parent;
 136                            parent = node;
 137                            node = tmp;
 138
 139                    }
 140
 141                    parent->color = BLACK;
 142                    gparent->color = RED;
 143                    _Rotate_Left(chain, gparent);
 144          }
 145    }
 146
 147    chain->root->color = BLACK;
 148 }
 149
 150 static void _RBT_Delete_Fixup(
 151    EDF_Chain_Control *chain,
 152    EDF_Node *node,
 153    EDF_Node *parent
 154 )
 155 {
 156    EDF_Node *other, *o_child;
 157
 158    while ((!node || node->color == BLACK) && node != chain->root)
 159    {
 160            if (parent->left == node)
 161            {
 162                    other = parent->right;
 163                    if (other->color == RED)
 164                    {
 165                         other->color = BLACK;
 166                         parent->color = RED;
 167                         _Rotate_Left(chain, parent);
 168                         other = parent->right;
 169                    }
 170                    if ((!other->left ||
 171                           other->left->color == BLACK)
 172                         && (!other->right ||
 173                           other->right->color == BLACK))
 174                     {
 175                         other->color = RED;
 176                         node = parent;
 177                         parent = node->parent;
 178                     }
 179                     else
 180                     {
 181                         if (!other->right ||
 182                             other->right->color == BLACK)
 183                         {
 184                                 if ((o_child = other->left))
 185                                         o_child->color = BLACK;
 186                                         other->color = RED;
 187                                         _Rotate_Right(chain,other);
 188                                         other = parent->right;
 189                                 }
 190                                 other->color = parent->color;
 191                                 parent->color = BLACK;
 192                                 if (other->right)
 193                                         other->right->color = BLACK;
 194                                 _Rotate_Left(chain,parent);
 195                                 node = chain->root;
 196                                 break;
 197                         }
 198                 }
 199                 else
 200                 {
 201                         other = parent->left;
 202                         if (other->color == RED)
 203                         {
 204                                 other->color = BLACK;
 205                                 parent->color = RED;
 206                                 _Rotate_Right(chain,parent);
 207                                 other = parent->left;
 208                         }
 209                         if ((!other->left ||
 210                              other->left->color == BLACK)
 211                             && (!other->right ||
 212                                 other->right->color == BLACK))
 213                         {
 214                                 other->color = RED;
 215                                 node = parent;
 216                                 parent = node->parent;
 217                         }
 218                         else
 219                         {
 220                                 if (!other->left ||
 221                                     other->left->color == BLACK)
 222                                 {
 223                                         register struct rb_node *o_right;
 224                                         if ((o_child = other->right))
 225                                                 o_child->color = BLACK;
 226                                         other->color = RED;
 227                                         _Rotate_Left(chain,other);
 228                                         other = parent->left;
 229                                 }
 230                                 other->color = parent->color;
 231                                 parent->color = BLACK;
 232                                 if (other->left)
 233                                         other->left->color = BLACK;
 234                                 _Rotate_Right(chain,parent);
 235                                 node = chain->root;
 236                                 break;
 237                         }
 238                 }
 239         }
 240         if (node)
 241                 node->color = BLACK;
 242 }
 243
 244
 245 void  _RBT_Extract(
 246    EDF_Chain_Control *chain,
 247    EDF_Node *node
 248 )
 249 {
 250    EDF_Node *child, *parent;
 251    int color;
 252
 253    if ( chain->first == node )
 254    {
 255         if ( chain->first->right) chain->first = chain->first->right;
 256         else chain->first = chain->first->parent;
 257    }
 258
 259    if (!node->left)
 260         child = node->right;
 261    else if (!node->right)
 262         child = node->left;
 263    else
 264    {
 265         /* this will never happen since only the first node
 266          * is being removed every time
 267          */
 268
 269         EDF_Node *old = node, *left;
 270
 271         node = node->right;
 272         while ((left = node->left) != NULL)
 273                 node = left;
 274         child = node->right;
 275         parent = node->parent;
 276         color = node->color;
 277
 278         if (child)
 279                 child->parent = parent;
 280         if (parent)
 281         {
 282                 if (parent->left == node)
 283                         parent->left = child;
 284                 else
 285                         parent->right = child;
 286         }
 287         else
 288                 chain->root = child;
 289
 290         if (node->parent == old)
 291                 parent = node;
 292         node->parent = old->parent;
 293         node->color = old->color;
 294         node->right = old->right;
 295         node->left = old->left;
 296
 297         if (old->parent)
 298         {
 299                 if (old->parent->left == old)
 300                         old->parent->left = node;
 301                 else
 302                         old->parent->right = node;
 303         } else
 304                 chain->root = node;
 305
 306         old->left->parent = node;
 307         if (old->right)
 308                 old->right->parent = node;
 309         goto color;
 310    }
 311
 312    parent = node->parent;
 313    color = node->color;
 314
 315    if (child)
 316         child->parent = parent;
 317    if (parent)
 318    {
 319         if (parent->left == node)
 320                 parent->left = child;
 321         else
 322                 parent->right = child;
 323    }
 324    else
 325         chain->root = child;
 326
 327  color:
 328         if (color == BLACK)
 329                 _RBT_Delete_Fixup(chain,child,parent);
 330 }
 331
 332 /*
 333  * TRUE if there is only one node in tree
 334  */
 335
 336 boolean _RBT_Has_only_one_node(
 337    EDF_Chain_Control *chain
 338 )
 339 {
 340    if ( !chain->root ) return 0;
 341    return ( chain->root->left == chain->root->right == NULL ) ;
 342 }
 343
 344 /*
 345  * Returns node with specific absolute deadline
 346  */
 347
 348 EDF_Node* _RBT_Search(
 349    EDF_Chain_Control *chain,
 350    Deadline_Control absdeadline
 351 )
 352 {
 353    EDF_Node *current;
 354
 355    current = chain->root;
 356    while (current != NULL) {
 357        if ( absdeadline == current->abs_deadline) return current;
 358        else {
 359            current = (absdeadline < current->abs_deadline) ?
 360                current->left : current->right;
 361        }
 362    }
 363    return NULL;
 364 }
 365