VirtualBox

Ignore:
Timestamp:
Apr 14, 2023 3:17:44 PM (2 years ago)
Author:
vboxsync
svn:sync-xref-src-repo-rev:
156854
Message:

Devices/EFI/FirmwareNew: Update to edk2-stable202302 and make it build, bugref:4643

Location:
trunk/src/VBox/Devices/EFI/FirmwareNew
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • trunk/src/VBox/Devices/EFI/FirmwareNew

  • trunk/src/VBox/Devices/EFI/FirmwareNew/MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.c

    r80721 r99404  
    3131// the implementation closely.
    3232//
    33 typedef ORDERED_COLLECTION              RED_BLACK_TREE;
    34 typedef ORDERED_COLLECTION_ENTRY        RED_BLACK_TREE_NODE;
    35 typedef ORDERED_COLLECTION_USER_COMPARE RED_BLACK_TREE_USER_COMPARE;
    36 typedef ORDERED_COLLECTION_KEY_COMPARE  RED_BLACK_TREE_KEY_COMPARE;
     33typedef ORDERED_COLLECTION               RED_BLACK_TREE;
     34typedef ORDERED_COLLECTION_ENTRY         RED_BLACK_TREE_NODE;
     35typedef ORDERED_COLLECTION_USER_COMPARE  RED_BLACK_TREE_USER_COMPARE;
     36typedef ORDERED_COLLECTION_KEY_COMPARE   RED_BLACK_TREE_KEY_COMPARE;
    3737
    3838struct ORDERED_COLLECTION {
    39   RED_BLACK_TREE_NODE         *Root;
    40   RED_BLACK_TREE_USER_COMPARE UserStructCompare;
    41   RED_BLACK_TREE_KEY_COMPARE  KeyCompare;
     39  RED_BLACK_TREE_NODE            *Root;
     40  RED_BLACK_TREE_USER_COMPARE    UserStructCompare;
     41  RED_BLACK_TREE_KEY_COMPARE     KeyCompare;
    4242};
    4343
    4444struct ORDERED_COLLECTION_ENTRY {
    45   VOID                 *UserStruct;
    46   RED_BLACK_TREE_NODE  *Parent;
    47   RED_BLACK_TREE_NODE  *Left;
    48   RED_BLACK_TREE_NODE  *Right;
    49   RED_BLACK_TREE_COLOR Color;
     45  VOID                    *UserStruct;
     46  RED_BLACK_TREE_NODE     *Parent;
     47  RED_BLACK_TREE_NODE     *Left;
     48  RED_BLACK_TREE_NODE     *Right;
     49  RED_BLACK_TREE_COLOR    Color;
    5050};
    51 
    5251
    5352/**
    … …  
    6564EFIAPI
    6665OrderedCollectionUserStruct (
    67   IN CONST RED_BLACK_TREE_NODE *Node
     66  IN CONST RED_BLACK_TREE_NODE  *Node
    6867  )
    6968{
    … …  
    8483VOID
    8584RedBlackTreeValidate (
    86   IN CONST RED_BLACK_TREE *Tree
     85  IN CONST RED_BLACK_TREE  *Tree
    8786  );
    88 
    8987
    9088/**
    … …  
    110108EFIAPI
    111109OrderedCollectionInit (
    112   IN RED_BLACK_TREE_USER_COMPARE UserStructCompare,
    113   IN RED_BLACK_TREE_KEY_COMPARE  KeyCompare
    114   )
    115 {
    116   RED_BLACK_TREE *Tree;
     110  IN RED_BLACK_TREE_USER_COMPARE  UserStructCompare,
     111  IN RED_BLACK_TREE_KEY_COMPARE   KeyCompare
     112  )
     113{
     114  RED_BLACK_TREE  *Tree;
    117115
    118116  Tree = AllocatePool (sizeof *Tree);
    … …  
    128126    RedBlackTreeValidate (Tree);
    129127  }
     128
    130129  return Tree;
    131130}
    132 
    133131
    134132/**
    … …  
    146144EFIAPI
    147145OrderedCollectionIsEmpty (
    148   IN CONST RED_BLACK_TREE *Tree
     146  IN CONST RED_BLACK_TREE  *Tree
    149147  )
    150148{
    151149  return (BOOLEAN)(Tree->Root == NULL);
    152150}
    153 
    154151
    155152/**
    … …  
    168165EFIAPI
    169166OrderedCollectionUninit (
    170   IN RED_BLACK_TREE *Tree
     167  IN RED_BLACK_TREE  *Tree
    171168  )
    172169{
    … …  
    174171  FreePool (Tree);
    175172}
    176 
    177173
    178174/**
    … …  
    196192EFIAPI
    197193OrderedCollectionFind (
    198   IN CONST RED_BLACK_TREE *Tree,
    199   IN CONST VOID           *StandaloneKey
    200   )
    201 {
    202   RED_BLACK_TREE_NODE *Node;
     194  IN CONST RED_BLACK_TREE  *Tree,
     195  IN CONST VOID            *StandaloneKey
     196  )
     197{
     198  RED_BLACK_TREE_NODE  *Node;
    203199
    204200  Node = Tree->Root;
    205201  while (Node != NULL) {
    206     INTN Result;
     202    INTN  Result;
    207203
    208204    Result = Tree->KeyCompare (StandaloneKey, Node->UserStruct);
    … …  
    210206      break;
    211207    }
     208
    212209    Node = (Result < 0) ? Node->Left : Node->Right;
    213210  }
     211
    214212  return Node;
    215213}
    216 
    217214
    218215/**
    … …  
    232229EFIAPI
    233230OrderedCollectionMin (
    234   IN CONST RED_BLACK_TREE *Tree
    235   )
    236 {
    237   RED_BLACK_TREE_NODE *Node;
     231  IN CONST RED_BLACK_TREE  *Tree
     232  )
     233{
     234  RED_BLACK_TREE_NODE  *Node;
    238235
    239236  Node = Tree->Root;
    … …  
    241238    return NULL;
    242239  }
     240
    243241  while (Node->Left != NULL) {
    244242    Node = Node->Left;
    245243  }
     244
    246245  return Node;
    247246}
    248 
    249247
    250248/**
    … …  
    264262EFIAPI
    265263OrderedCollectionMax (
    266   IN CONST RED_BLACK_TREE *Tree
    267   )
    268 {
    269   RED_BLACK_TREE_NODE *Node;
     264  IN CONST RED_BLACK_TREE  *Tree
     265  )
     266{
     267  RED_BLACK_TREE_NODE  *Node;
    270268
    271269  Node = Tree->Root;
    … …  
    273271    return NULL;
    274272  }
     273
    275274  while (Node->Right != NULL) {
    276275    Node = Node->Right;
    277276  }
     277
    278278  return Node;
    279279}
    280 
    281280
    282281/**
    … …  
    297296EFIAPI
    298297OrderedCollectionNext (
    299   IN CONST RED_BLACK_TREE_NODE *Node
    300   )
    301 {
    302   RED_BLACK_TREE_NODE       *Walk;
    303   CONST RED_BLACK_TREE_NODE *Child;
     298  IN CONST RED_BLACK_TREE_NODE  *Node
     299  )
     300{
     301  RED_BLACK_TREE_NODE        *Walk;
     302  CONST RED_BLACK_TREE_NODE  *Child;
    304303
    305304  if (Node == NULL) {
    … …  
    316315      Walk = Walk->Left;
    317316    }
     317
    318318    return Walk;
    319319  }
    … …  
    324324  //
    325325  Child = Node;
    326   Walk = Child->Parent;
     326  Walk  = Child->Parent;
    327327  while (Walk != NULL && Child == Walk->Right) {
    328328    Child = Walk;
    329     Walk = Child->Parent;
    330   }
     329    Walk  = Child->Parent;
     330  }
     331
    331332  return Walk;
    332333}
    333 
    334334
    335335/**
    … …  
    350350EFIAPI
    351351OrderedCollectionPrev (
    352   IN CONST RED_BLACK_TREE_NODE *Node
    353   )
    354 {
    355   RED_BLACK_TREE_NODE       *Walk;
    356   CONST RED_BLACK_TREE_NODE *Child;
     352  IN CONST RED_BLACK_TREE_NODE  *Node
     353  )
     354{
     355  RED_BLACK_TREE_NODE        *Walk;
     356  CONST RED_BLACK_TREE_NODE  *Child;
    357357
    358358  if (Node == NULL) {
    … …  
    369369      Walk = Walk->Right;
    370370    }
     371
    371372    return Walk;
    372373  }
    … …  
    377378  //
    378379  Child = Node;
    379   Walk = Child->Parent;
     380  Walk  = Child->Parent;
    380381  while (Walk != NULL && Child == Walk->Left) {
    381382    Child = Walk;
    382     Walk = Child->Parent;
    383   }
     383    Walk  = Child->Parent;
     384  }
     385
    384386  return Walk;
    385387}
    386 
    387388
    388389/**
    … …  
    420421VOID
    421422RedBlackTreeRotateRight (
    422   IN OUT RED_BLACK_TREE_NODE *Pivot,
    423   OUT    RED_BLACK_TREE_NODE **NewRoot
    424   )
    425 {
    426   RED_BLACK_TREE_NODE *Parent;
    427   RED_BLACK_TREE_NODE *LeftChild;
    428   RED_BLACK_TREE_NODE *LeftRightChild;
     423  IN OUT RED_BLACK_TREE_NODE  *Pivot,
     424  OUT    RED_BLACK_TREE_NODE  **NewRoot
     425  )
     426{
     427  RED_BLACK_TREE_NODE  *Parent;
     428  RED_BLACK_TREE_NODE  *LeftChild;
     429  RED_BLACK_TREE_NODE  *LeftRightChild;
    429430
    430431  Parent         = Pivot->Parent;
    … …  
    436437    LeftRightChild->Parent = Pivot;
    437438  }
     439
    438440  LeftChild->Parent = Parent;
    439441  if (Parent == NULL) {
    … …  
    446448    }
    447449  }
     450
    448451  LeftChild->Right = Pivot;
    449   Pivot->Parent = LeftChild;
    450 }
    451 
     452  Pivot->Parent    = LeftChild;
     453}
    452454
    453455/**
    … …  
    485487VOID
    486488RedBlackTreeRotateLeft (
    487   IN OUT RED_BLACK_TREE_NODE *Pivot,
    488   OUT    RED_BLACK_TREE_NODE **NewRoot
    489   )
    490 {
    491   RED_BLACK_TREE_NODE *Parent;
    492   RED_BLACK_TREE_NODE *RightChild;
    493   RED_BLACK_TREE_NODE *RightLeftChild;
     489  IN OUT RED_BLACK_TREE_NODE  *Pivot,
     490  OUT    RED_BLACK_TREE_NODE  **NewRoot
     491  )
     492{
     493  RED_BLACK_TREE_NODE  *Parent;
     494  RED_BLACK_TREE_NODE  *RightChild;
     495  RED_BLACK_TREE_NODE  *RightLeftChild;
    494496
    495497  Parent         = Pivot->Parent;
    … …  
    501503    RightLeftChild->Parent = Pivot;
    502504  }
     505
    503506  RightChild->Parent = Parent;
    504507  if (Parent == NULL) {
    … …  
    511514    }
    512515  }
     516
    513517  RightChild->Left = Pivot;
    514   Pivot->Parent = RightChild;
    515 }
    516 
     518  Pivot->Parent    = RightChild;
     519}
    517520
    518521/**
    … …  
    580583EFIAPI
    581584OrderedCollectionInsert (
    582   IN OUT RED_BLACK_TREE      *Tree,
    583   OUT    RED_BLACK_TREE_NODE **Node      OPTIONAL,
    584   IN     VOID                *UserStruct
    585   )
    586 {
    587   RED_BLACK_TREE_NODE *Tmp;
    588   RED_BLACK_TREE_NODE *Parent;
    589   INTN                Result;
    590   RETURN_STATUS       Status;
    591   RED_BLACK_TREE_NODE *NewRoot;
    592 
    593   Tmp = Tree->Root;
     585  IN OUT RED_BLACK_TREE       *Tree,
     586  OUT    RED_BLACK_TREE_NODE  **Node      OPTIONAL,
     587  IN     VOID                 *UserStruct
     588  )
     589{
     590  RED_BLACK_TREE_NODE  *Tmp;
     591  RED_BLACK_TREE_NODE  *Parent;
     592  INTN                 Result;
     593  RETURN_STATUS        Status;
     594  RED_BLACK_TREE_NODE  *NewRoot;
     595
     596  Tmp    = Tree->Root;
    594597  Parent = NULL;
    595598  Result = 0;
    … …  
    604607      break;
    605608    }
     609
    606610    Parent = Tmp;
    607     Tmp = (Result < 0) ? Tmp->Left : Tmp->Right;
     611    Tmp    = (Result < 0) ? Tmp->Left : Tmp->Right;
    608612  }
    609613
    … …  
    612616      *Node = Tmp;
    613617    }
     618
    614619    Status = RETURN_ALREADY_STARTED;
    615620    goto Done;
    … …  
    624629    goto Done;
    625630  }
     631
    626632  if (Node != NULL) {
    627633    *Node = Tmp;
    … …  
    638644  //
    639645  Tmp->Parent = Parent;
    640   Tmp->Left = NULL;
    641   Tmp->Right = NULL;
     646  Tmp->Left   = NULL;
     647  Tmp->Right  = NULL;
    642648  if (Parent == NULL) {
    643649    Tree->Root = Tmp;
    644650    Tmp->Color = RedBlackTreeBlack;
    645     Status = RETURN_SUCCESS;
     651    Status     = RETURN_SUCCESS;
    646652    goto Done;
    647653  }
     654
    648655  if (Result < 0) {
    649656    Parent->Left = Tmp;
    … …  
    651658    Parent->Right = Tmp;
    652659  }
     660
    653661  Tmp->Color = RedBlackTreeRed;
    654662
    … …  
    675683  NewRoot = Tree->Root;
    676684  while (Tmp != NewRoot && Parent->Color == RedBlackTreeRed) {
    677     RED_BLACK_TREE_NODE *GrandParent;
    678     RED_BLACK_TREE_NODE *Uncle;
     685    RED_BLACK_TREE_NODE  *GrandParent;
     686    RED_BLACK_TREE_NODE  *Uncle;
    679687
    680688    //
    … …  
    692700    if (Parent == GrandParent->Left) {
    693701      Uncle = GrandParent->Right;
    694       if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
     702      if ((Uncle != NULL) && (Uncle->Color == RedBlackTreeRed)) {
    695703        //
    696704        //             GrandParent (black)
    … …  
    701709        //
    702710
    703         Parent->Color = RedBlackTreeBlack;
    704         Uncle->Color = RedBlackTreeBlack;
     711        Parent->Color      = RedBlackTreeBlack;
     712        Uncle->Color       = RedBlackTreeBlack;
    705713        GrandParent->Color = RedBlackTreeRed;
    706714
    … …  
    721729        // restore property #5 after the loop, without breaking any others.
    722730        //
    723         Tmp = GrandParent;
     731        Tmp    = GrandParent;
    724732        Parent = Tmp->Parent;
    725733      } else {
    … …  
    760768        }
    761769
    762         Parent->Color = RedBlackTreeBlack;
     770        Parent->Color      = RedBlackTreeBlack;
    763771        GrandParent->Color = RedBlackTreeRed;
    764772
    … …  
    795803      //
    796804      Uncle = GrandParent->Left;
    797       if (Uncle != NULL && Uncle->Color == RedBlackTreeRed) {
    798         Parent->Color = RedBlackTreeBlack;
    799         Uncle->Color = RedBlackTreeBlack;
     805      if ((Uncle != NULL) && (Uncle->Color == RedBlackTreeRed)) {
     806        Parent->Color      = RedBlackTreeBlack;
     807        Uncle->Color       = RedBlackTreeBlack;
    800808        GrandParent->Color = RedBlackTreeRed;
    801         Tmp = GrandParent;
    802         Parent = Tmp->Parent;
     809        Tmp                = GrandParent;
     810        Parent             = Tmp->Parent;
    803811      } else {
    804812        if (Tmp == Parent->Left) {
    … …  
    808816          ASSERT (GrandParent == Parent->Parent);
    809817        }
    810         Parent->Color = RedBlackTreeBlack;
     818
     819        Parent->Color      = RedBlackTreeBlack;
    811820        GrandParent->Color = RedBlackTreeRed;
    812821        RedBlackTreeRotateLeft (GrandParent, &NewRoot);
    … …  
    816825
    817826  NewRoot->Color = RedBlackTreeBlack;
    818   Tree->Root = NewRoot;
    819   Status = RETURN_SUCCESS;
     827  Tree->Root     = NewRoot;
     828  Status         = RETURN_SUCCESS;
    820829
    821830Done:
    … …  
    823832    RedBlackTreeValidate (Tree);
    824833  }
     834
    825835  return Status;
    826836}
    827 
    828837
    829838/**
    … …  
    838847BOOLEAN
    839848NodeIsNullOrBlack (
    840   IN CONST RED_BLACK_TREE_NODE *Node
     849  IN CONST RED_BLACK_TREE_NODE  *Node
    841850  )
    842851{
    843852  return (BOOLEAN)(Node == NULL || Node->Color == RedBlackTreeBlack);
    844853}
    845 
    846854
    847855/**
    … …  
    913921EFIAPI
    914922OrderedCollectionDelete (
    915   IN OUT RED_BLACK_TREE      *Tree,
    916   IN     RED_BLACK_TREE_NODE *Node,
    917   OUT    VOID                **UserStruct OPTIONAL
    918   )
    919 {
    920   RED_BLACK_TREE_NODE  *NewRoot;
    921   RED_BLACK_TREE_NODE  *OrigLeftChild;
    922   RED_BLACK_TREE_NODE  *OrigRightChild;
    923   RED_BLACK_TREE_NODE  *OrigParent;
    924   RED_BLACK_TREE_NODE  *Child;
    925   RED_BLACK_TREE_NODE  *Parent;
    926   RED_BLACK_TREE_COLOR ColorOfUnlinked;
     923  IN OUT RED_BLACK_TREE       *Tree,
     924  IN     RED_BLACK_TREE_NODE  *Node,
     925  OUT    VOID                 **UserStruct OPTIONAL
     926  )
     927{
     928  RED_BLACK_TREE_NODE   *NewRoot;
     929  RED_BLACK_TREE_NODE   *OrigLeftChild;
     930  RED_BLACK_TREE_NODE   *OrigRightChild;
     931  RED_BLACK_TREE_NODE   *OrigParent;
     932  RED_BLACK_TREE_NODE   *Child;
     933  RED_BLACK_TREE_NODE   *Parent;
     934  RED_BLACK_TREE_COLOR  ColorOfUnlinked;
    927935
    928936  NewRoot        = Tree->Root;
    … …  
    942950  //   that we will have unlinked.
    943951  //
    944   if (OrigLeftChild == NULL || OrigRightChild == NULL) {
     952  if ((OrigLeftChild == NULL) || (OrigRightChild == NULL)) {
    945953    //
    946954    // Node has at most one child. We can connect that child (if any) with
    … …  
    949957    // side of Node's parent (if any) that Node was before.
    950958    //
    951     Parent = OrigParent;
    952     Child = (OrigLeftChild != NULL) ? OrigLeftChild : OrigRightChild;
     959    Parent          = OrigParent;
     960    Child           = (OrigLeftChild != NULL) ? OrigLeftChild : OrigRightChild;
    953961    ColorOfUnlinked = Node->Color;
    954962
    … …  
    956964      Child->Parent = Parent;
    957965    }
     966
    958967    if (OrigParent == NULL) {
    959968      NewRoot = Child;
    … …  
    979988    //   relation.
    980989    //
    981     RED_BLACK_TREE_NODE *ToRelink;
     990    RED_BLACK_TREE_NODE  *ToRelink;
    982991
    983992    ToRelink = OrigRightChild;
    … …  
    9951004      //
    9961005      Parent = OrigRightChild;
    997       Child = OrigRightChild->Right;
     1006      Child  = OrigRightChild->Right;
    9981007    } else {
    9991008      do {
    … …  
    10141023      //                                   D <--- Child
    10151024      Parent = ToRelink->Parent;
    1016       Child = ToRelink->Right;
     1025      Child  = ToRelink->Right;
    10171026
    10181027      //
    … …  
    10471056      //
    10481057      //
    1049       ToRelink->Right = OrigRightChild;
     1058      ToRelink->Right        = OrigRightChild;
    10501059      OrigRightChild->Parent = ToRelink;
    10511060    }
    … …  
    10671076    //                  Child
    10681077    //
    1069     ToRelink->Left = OrigLeftChild;
     1078    ToRelink->Left        = OrigLeftChild;
    10701079    OrigLeftChild->Parent = ToRelink;
    10711080
    … …  
    11301139    //
    11311140    while (Child != NewRoot && NodeIsNullOrBlack (Child)) {
    1132       RED_BLACK_TREE_NODE *Sibling;
    1133       RED_BLACK_TREE_NODE *LeftNephew;
    1134       RED_BLACK_TREE_NODE *RightNephew;
     1141      RED_BLACK_TREE_NODE  *Sibling;
     1142      RED_BLACK_TREE_NODE  *LeftNephew;
     1143      RED_BLACK_TREE_NODE  *RightNephew;
    11351144
    11361145      if (Child == Parent->Left) {
    … …  
    11641173          //
    11651174          Sibling->Color = RedBlackTreeBlack;
    1166           Parent->Color = RedBlackTreeRed;
     1175          Parent->Color  = RedBlackTreeRed;
    11671176          RedBlackTreeRotateLeft (Parent, &NewRoot);
    11681177          Sibling = Parent->Right;
    … …  
    11781187        //
    11791188        ASSERT (Sibling->Color == RedBlackTreeBlack);
    1180         LeftNephew = Sibling->Left;
     1189        LeftNephew  = Sibling->Left;
    11811190        RightNephew = Sibling->Right;
    11821191        if (NodeIsNullOrBlack (LeftNephew) &&
    1183             NodeIsNullOrBlack (RightNephew)) {
     1192            NodeIsNullOrBlack (RightNephew))
     1193        {
    11841194          //
    11851195          // In this case we can "steal" one black value from Child and Sibling
    … …  
    12011211          //
    12021212          Sibling->Color = RedBlackTreeRed;
    1203           Child = Parent;
    1204           Parent = Parent->Parent;
     1213          Child          = Parent;
     1214          Parent         = Parent->Parent;
    12051215          //
    12061216          // Continue ascending.
    … …  
    12311241            //
    12321242            LeftNephew->Color = RedBlackTreeBlack;
    1233             Sibling->Color = RedBlackTreeRed;
     1243            Sibling->Color    = RedBlackTreeRed;
    12341244            RedBlackTreeRotateRight (Sibling, &NewRoot);
    1235             Sibling = Parent->Right;
     1245            Sibling     = Parent->Right;
    12361246            RightNephew = Sibling->Right;
    12371247            //
    … …  
    12391249            //
    12401250          }
     1251
    12411252          //
    12421253          // ... RightNephew is definitely red here, plus Sibling is (still)
    … …  
    12731284          //
    12741285          //
    1275           Sibling->Color = Parent->Color;
    1276           Parent->Color = RedBlackTreeBlack;
     1286          Sibling->Color     = Parent->Color;
     1287          Parent->Color      = RedBlackTreeBlack;
    12771288          RightNephew->Color = RedBlackTreeBlack;
    12781289          RedBlackTreeRotateLeft (Parent, &NewRoot);
    … …  
    12901301        if (Sibling->Color == RedBlackTreeRed) {
    12911302          Sibling->Color = RedBlackTreeBlack;
    1292           Parent->Color = RedBlackTreeRed;
     1303          Parent->Color  = RedBlackTreeRed;
    12931304          RedBlackTreeRotateRight (Parent, &NewRoot);
    12941305          Sibling = Parent->Left;
    … …  
    12981309        ASSERT (Sibling->Color == RedBlackTreeBlack);
    12991310        RightNephew = Sibling->Right;
    1300         LeftNephew = Sibling->Left;
     1311        LeftNephew  = Sibling->Left;
    13011312        if (NodeIsNullOrBlack (RightNephew) &&
    1302             NodeIsNullOrBlack (LeftNephew)) {
     1313            NodeIsNullOrBlack (LeftNephew))
     1314        {
    13031315          Sibling->Color = RedBlackTreeRed;
    1304           Child = Parent;
    1305           Parent = Parent->Parent;
     1316          Child          = Parent;
     1317          Parent         = Parent->Parent;
    13061318        } else {
    13071319          if (NodeIsNullOrBlack (LeftNephew)) {
    13081320            RightNephew->Color = RedBlackTreeBlack;
    1309             Sibling->Color = RedBlackTreeRed;
     1321            Sibling->Color     = RedBlackTreeRed;
    13101322            RedBlackTreeRotateLeft (Sibling, &NewRoot);
    1311             Sibling = Parent->Left;
     1323            Sibling    = Parent->Left;
    13121324            LeftNephew = Sibling->Left;
    13131325          }
     1326
    13141327          ASSERT (LeftNephew != NULL);
    13151328          ASSERT (LeftNephew->Color == RedBlackTreeRed);
    13161329          ASSERT (Sibling != NULL);
    13171330          ASSERT (Sibling->Color == RedBlackTreeBlack);
    1318           Sibling->Color = Parent->Color;
    1319           Parent->Color = RedBlackTreeBlack;
     1331          Sibling->Color    = Parent->Color;
     1332          Parent->Color     = RedBlackTreeBlack;
    13201333          LeftNephew->Color = RedBlackTreeBlack;
    13211334          RedBlackTreeRotateRight (Parent, &NewRoot);
    … …  
    13371350}
    13381351
    1339 
    13401352/**
    13411353  Recursively check the red-black tree properties #1 to #4 on a node.
    … …  
    13471359UINT32
    13481360RedBlackTreeRecursiveCheck (
    1349   IN CONST RED_BLACK_TREE_NODE *Node
    1350   )
    1351 {
    1352   UINT32 LeftHeight;
    1353   UINT32 RightHeight;
     1361  IN CONST RED_BLACK_TREE_NODE  *Node
     1362  )
     1363{
     1364  UINT32  LeftHeight;
     1365  UINT32  RightHeight;
    13541366
    13551367  //
    … …  
    13761388  // property #4
    13771389  //
    1378   LeftHeight = RedBlackTreeRecursiveCheck (Node->Left);
     1390  LeftHeight  = RedBlackTreeRecursiveCheck (Node->Left);
    13791391  RightHeight = RedBlackTreeRecursiveCheck (Node->Right);
    13801392  ASSERT (LeftHeight == RightHeight);
    … …  
    13831395}
    13841396
    1385 
    13861397/**
    13871398  A slow function that asserts that the tree is a valid red-black tree, and
    … …  
    13971408VOID
    13981409RedBlackTreeValidate (
    1399   IN CONST RED_BLACK_TREE *Tree
    1400   )
    1401 {
    1402   UINT32                    BlackHeight;
    1403   UINT32                    ForwardCount;
    1404   UINT32                    BackwardCount;
    1405   CONST RED_BLACK_TREE_NODE *Last;
    1406   CONST RED_BLACK_TREE_NODE *Node;
     1410  IN CONST RED_BLACK_TREE  *Tree
     1411  )
     1412{
     1413  UINT32                     BlackHeight;
     1414  UINT32                     ForwardCount;
     1415  UINT32                     BackwardCount;
     1416  CONST RED_BLACK_TREE_NODE  *Last;
     1417  CONST RED_BLACK_TREE_NODE  *Node;
    14071418
    14081419  DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p\n", __FUNCTION__, Tree));
    … …  
    14211432  // forward ordering
    14221433  //
    1423   Last = OrderedCollectionMin (Tree);
     1434  Last         = OrderedCollectionMin (Tree);
    14241435  ForwardCount = (Last != NULL);
    14251436  for (Node = OrderedCollectionNext (Last); Node != NULL;
    1426        Node = OrderedCollectionNext (Last)) {
     1437       Node = OrderedCollectionNext (Last))
     1438  {
    14271439    ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) < 0);
    14281440    Last = Node;
    … …  
    14331445  // backward ordering
    14341446  //
    1435   Last = OrderedCollectionMax (Tree);
     1447  Last          = OrderedCollectionMax (Tree);
    14361448  BackwardCount = (Last != NULL);
    14371449  for (Node = OrderedCollectionPrev (Last); Node != NULL;
    1438        Node = OrderedCollectionPrev (Last)) {
     1450       Node = OrderedCollectionPrev (Last))
     1451  {
    14391452    ASSERT (Tree->UserStructCompare (Last->UserStruct, Node->UserStruct) > 0);
    14401453    Last = Node;
    … …  
    14441457  ASSERT (ForwardCount == BackwardCount);
    14451458
    1446   DEBUG ((DEBUG_VERBOSE, "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",
    1447     __FUNCTION__, Tree, (INT64)BlackHeight, (INT64)ForwardCount));
    1448 }
     1459  DEBUG ((
     1460    DEBUG_VERBOSE,
     1461    "%a: Tree=%p BlackHeight=%Ld Count=%Ld\n",
     1462    __FUNCTION__,
     1463    Tree,
     1464    (INT64)BlackHeight,
     1465    (INT64)ForwardCount
     1466    ));
     1467}
Note: See TracChangeset for help on using the changeset viewer.

© 2025 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette