rtems-omk-template/edf/rbtree.c

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