DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTree.c

   1 /** @file
   2   AML Tree.
   3
   4   Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.<BR>
   5
   6   SPDX-License-Identifier: BSD-2-Clause-Patent
   7 **/
   8
   9 #include <Tree/AmlTree.h>
  10
  11 #include <AmlCoreInterface.h>
  12 #include <Tree/AmlNode.h>
  13 #include <Tree/AmlTreeTraversal.h>
  14 #include <Utils/AmlUtility.h>
  15
  16 /** Get the parent node of the input Node.
  17
  18   @param [in] Node  Pointer to a node.
  19
  20   @return The parent node of the input Node.
  21           NULL otherwise.
  22 **/
  23 AML_NODE_HEADER *
  24 EFIAPI
  25 AmlGetParent (
  26   IN  AML_NODE_HEADER   * Node
  27   )
  28 {
  29   if (IS_AML_DATA_NODE (Node) ||
  30       IS_AML_OBJECT_NODE (Node)) {
  31     return Node->Parent;
  32   }
  33
  34   return NULL;
  35 }
  36
  37 /** Get the root node from any node of the tree.
  38     This is done by climbing up the tree until the root node is reached.
  39
  40   @param  [in]  Node    Pointer to a node.
  41
  42   @return The root node of the tree.
  43           NULL if error.
  44 **/
  45 AML_ROOT_NODE *
  46 EFIAPI
  47 AmlGetRootNode (
  48   IN  CONST AML_NODE_HEADER   * Node
  49   )
  50 {
  51   if (!IS_AML_NODE_VALID (Node)) {
  52     ASSERT (0);
  53     return NULL;
  54   }
  55
  56   while (!IS_AML_ROOT_NODE (Node)) {
  57     Node = Node->Parent;
  58     if (!IS_AML_NODE_VALID (Node)) {
  59       ASSERT (0);
  60       return NULL;
  61     }
  62   }
  63   return (AML_ROOT_NODE*)Node;
  64 }
  65
  66 /** Get the node at the input Index in the fixed argument list of the input
  67     ObjectNode.
  68
  69   @param  [in]  ObjectNode  Pointer to an object node.
  70   @param  [in]  Index       The Index of the fixed argument to get.
  71
  72   @return The node at the input Index in the fixed argument list
  73           of the input ObjectNode.
  74           NULL otherwise, e.g. if the node is not an object node, or no
  75           node is available at this Index.
  76 **/
  77 AML_NODE_HEADER *
  78 EFIAPI
  79 AmlGetFixedArgument (
  80   IN  AML_OBJECT_NODE     * ObjectNode,
  81   IN  EAML_PARSE_INDEX      Index
  82   )
  83 {
  84   if (IS_AML_OBJECT_NODE (ObjectNode)) {
  85     if (Index < (EAML_PARSE_INDEX)AmlGetFixedArgumentCount (ObjectNode)) {
  86       return ObjectNode->FixedArgs[Index];
  87     }
  88   }
  89
  90   return NULL;
  91 }
  92
  93 /** Check whether the input Node is in the fixed argument list of its parent
  94     node.
  95
  96   If so, IndexPtr contains this Index.
  97
  98   @param  [in]  Node          Pointer to a Node.
  99   @param  [out] IndexPtr      Pointer holding the Index of the Node in
 100                               its parent's fixed argument list.
 101
 102   @retval TRUE   The node is a fixed argument and the index
 103                  in IndexPtr is valid.
 104   @retval FALSE  The node is not a fixed argument.
 105 **/
 106 BOOLEAN
 107 EFIAPI
 108 AmlIsNodeFixedArgument (
 109   IN  CONST  AML_NODE_HEADER     * Node,
 110   OUT        EAML_PARSE_INDEX    * IndexPtr
 111   )
 112 {
 113   AML_NODE_HEADER         * ParentNode;
 114
 115   EAML_PARSE_INDEX        Index;
 116   EAML_PARSE_INDEX        MaxIndex;
 117
 118   if ((IndexPtr == NULL)               ||
 119       (!IS_AML_DATA_NODE (Node)        &&
 120        !IS_AML_OBJECT_NODE (Node))) {
 121     ASSERT (0);
 122     return FALSE;
 123   }
 124
 125   ParentNode = AmlGetParent ((AML_NODE_HEADER*)Node);
 126   if (IS_AML_ROOT_NODE (ParentNode)) {
 127     return FALSE;
 128   } else if (IS_AML_DATA_NODE (ParentNode)) {
 129     // Tree is inconsistent.
 130     ASSERT (0);
 131     return FALSE;
 132   }
 133
 134   // Check whether the Node is in the fixed argument list.
 135   MaxIndex = (EAML_PARSE_INDEX)AmlGetFixedArgumentCount (
 136                                  (AML_OBJECT_NODE*)ParentNode
 137                                  );
 138   for (Index = EAmlParseIndexTerm0; Index < MaxIndex; Index++) {
 139     if (AmlGetFixedArgument ((AML_OBJECT_NODE*)ParentNode, Index) == Node) {
 140       *IndexPtr = Index;
 141       return TRUE;
 142     }
 143   }
 144
 145   return FALSE;
 146 }
 147
 148 /** Set the fixed argument of the ObjectNode at the Index to the NewNode.
 149
 150   It is the caller's responsibility to save the old node, if desired,
 151   otherwise the reference to the old node will be lost.
 152   If NewNode is not NULL, set its parent to ObjectNode.
 153
 154   @param  [in]  ObjectNode    Pointer to an object node.
 155   @param  [in]  Index         Index in the fixed argument list of
 156                               the ObjectNode to set.
 157   @param  [in]  NewNode       Pointer to the NewNode.
 158                               Can be NULL, a data node or an object node.
 159
 160   @retval EFI_SUCCESS             The function completed successfully.
 161   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 162 **/
 163 EFI_STATUS
 164 EFIAPI
 165 AmlSetFixedArgument (
 166   IN  AML_OBJECT_NODE   * ObjectNode,
 167   IN  EAML_PARSE_INDEX    Index,
 168   IN  AML_NODE_HEADER   * NewNode
 169   )
 170 {
 171   if (IS_AML_OBJECT_NODE (ObjectNode)                                     &&
 172       (Index <= (EAML_PARSE_INDEX)AmlGetFixedArgumentCount (ObjectNode))  &&
 173       ((NewNode == NULL)                                                  ||
 174        IS_AML_OBJECT_NODE (NewNode)                                       ||
 175        IS_AML_DATA_NODE (NewNode))) {
 176     ObjectNode->FixedArgs[Index] = NewNode;
 177
 178     // If NewNode is a data node or an object node, set its parent.
 179     if (NewNode != NULL) {
 180       NewNode->Parent = (AML_NODE_HEADER*)ObjectNode;
 181     }
 182
 183     return EFI_SUCCESS;
 184   }
 185
 186   ASSERT (0);
 187   return EFI_INVALID_PARAMETER;
 188 }
 189
 190 /** If the given AML_NODE_HEADER has a variable list of arguments,
 191     return a pointer to this list.
 192     Return NULL otherwise.
 193
 194   @param  [in]  Node  Pointer to the AML_NODE_HEADER to check.
 195
 196   @return The list of variable arguments if there is one.
 197           NULL otherwise.
 198 **/
 199 LIST_ENTRY *
 200 EFIAPI
 201 AmlNodeGetVariableArgList (
 202   IN  CONST AML_NODE_HEADER   * Node
 203   )
 204 {
 205   if (IS_AML_ROOT_NODE (Node)) {
 206     return &(((AML_ROOT_NODE*)Node)->VariableArgs);
 207   } else if (IS_AML_OBJECT_NODE (Node)) {
 208     return &(((AML_OBJECT_NODE*)Node)->VariableArgs);
 209   }
 210   return NULL;
 211 }
 212
 213 /** Remove the Node from its parent's variable list of arguments.
 214
 215   The function will fail if the Node is in its parent's fixed
 216   argument list.
 217   The Node is not deleted. The deletion is done separately
 218   from the removal.
 219
 220   @param  [in]  Node  Pointer to a Node.
 221                       Must be a data node or an object node.
 222
 223   @retval EFI_SUCCESS             The function completed successfully.
 224   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 225 **/
 226 EFI_STATUS
 227 EFIAPI
 228 AmlRemoveNodeFromVarArgList (
 229   IN  AML_NODE_HEADER   * Node
 230   )
 231 {
 232   EFI_STATUS          Status;
 233   AML_NODE_HEADER   * ParentNode;
 234   UINT32              Size;
 235
 236   if ((!IS_AML_DATA_NODE (Node) &&
 237        !IS_AML_OBJECT_NODE (Node))) {
 238     ASSERT (0);
 239     return EFI_INVALID_PARAMETER;
 240   }
 241
 242   ParentNode = AmlGetParent (Node);
 243   if (!IS_AML_ROOT_NODE (ParentNode)  &&
 244       !IS_AML_OBJECT_NODE (ParentNode)) {
 245     ASSERT (0);
 246     return EFI_INVALID_PARAMETER;
 247   }
 248
 249   // Check the node is in its parent variable list of arguments.
 250   if (!IsNodeInList (
 251          AmlNodeGetVariableArgList (ParentNode),
 252          &Node->Link)) {
 253     ASSERT (0);
 254     return EFI_INVALID_PARAMETER;
 255   }
 256
 257   // Unlink Node from the tree.
 258   RemoveEntryList (&Node->Link);
 259   InitializeListHead (&Node->Link);
 260   Node->Parent = NULL;
 261
 262   // Get the size of the node removed.
 263   Status = AmlComputeSize (Node, &Size);
 264   if (EFI_ERROR (Status)) {
 265     ASSERT (0);
 266     return Status;
 267   }
 268
 269   // Propagate the information.
 270   Status = AmlPropagateInformation (ParentNode, FALSE, Size, 1);
 271   ASSERT_EFI_ERROR (Status);
 272
 273   return Status;
 274 }
 275
 276 /** Detach the Node from the tree.
 277
 278   The function will fail if the Node is in its parent's fixed
 279   argument list.
 280   The Node is not deleted. The deletion is done separately
 281   from the removal.
 282
 283   @param  [in]  Node  Pointer to a Node.
 284                       Must be a data node or an object node.
 285
 286   @retval EFI_SUCCESS             The function completed successfully.
 287   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 288 **/
 289 EFI_STATUS
 290 EFIAPI
 291 AmlDetachNode (
 292   IN  AML_NODE_HEADER   * Node
 293   )
 294 {
 295   return AmlRemoveNodeFromVarArgList (Node);
 296 }
 297
 298 /** Add the NewNode to the head of the variable list of arguments
 299     of the ParentNode.
 300
 301   @param  [in]  ParentNode  Pointer to the parent node.
 302                             Must be a root or an object node.
 303   @param  [in]  NewNode     Pointer to the node to add.
 304
 305   @retval EFI_SUCCESS             The function completed successfully.
 306   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 307 **/
 308 EFI_STATUS
 309 EFIAPI
 310 AmlVarListAddHead (
 311   IN  AML_NODE_HEADER  * ParentNode,
 312   IN  AML_NODE_HEADER  * NewNode
 313   )
 314 {
 315   EFI_STATUS    Status;
 316   UINT32        NewSize;
 317   LIST_ENTRY  * ChildrenList;
 318
 319   // Check arguments and that NewNode is not already attached to a tree.
 320   // ParentNode != Data Node AND NewNode != Root Node AND NewNode != attached.
 321   if ((!IS_AML_ROOT_NODE (ParentNode)     &&
 322        !IS_AML_OBJECT_NODE (ParentNode))  ||
 323       (!IS_AML_DATA_NODE (NewNode)        &&
 324        !IS_AML_OBJECT_NODE (NewNode))     ||
 325       !AML_NODE_IS_DETACHED (NewNode)) {
 326     ASSERT (0);
 327     return EFI_INVALID_PARAMETER;
 328   }
 329
 330   // Insert it at the head of the list.
 331   ChildrenList = AmlNodeGetVariableArgList (ParentNode);
 332   if (ChildrenList == NULL) {
 333     ASSERT (0);
 334     return EFI_INVALID_PARAMETER;
 335   }
 336
 337   InsertHeadList (ChildrenList, &NewNode->Link);
 338   NewNode->Parent = ParentNode;
 339
 340   // Get the size of the NewNode.
 341   Status = AmlComputeSize (NewNode, &NewSize);
 342   if (EFI_ERROR (Status)) {
 343     ASSERT (0);
 344     return Status;
 345   }
 346
 347   // Propagate the new information.
 348   Status = AmlPropagateInformation (ParentNode, TRUE, NewSize, 1);
 349   ASSERT_EFI_ERROR (Status);
 350
 351   return Status;
 352 }
 353
 354 /** Add the NewNode to the tail of the variable list of arguments
 355     of the ParentNode.
 356
 357   NOTE: This is an internal function which does not propagate the size
 358         when a new node is added.
 359
 360   @param  [in]  ParentNode  Pointer to the parent node.
 361                             Must be a root or an object node.
 362   @param  [in]  NewNode     Pointer to the node to add.
 363
 364   @retval EFI_SUCCESS             The function completed successfully.
 365   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 366 **/
 367 EFI_STATUS
 368 EFIAPI
 369 AmlVarListAddTailInternal (
 370   IN  AML_NODE_HEADER  * ParentNode,
 371   IN  AML_NODE_HEADER  * NewNode
 372   )
 373 {
 374   LIST_ENTRY  * ChildrenList;
 375
 376   // Check arguments and that NewNode is not already attached to a tree.
 377   // ParentNode != Data Node AND NewNode != Root Node AND NewNode != attached.
 378   if ((!IS_AML_ROOT_NODE (ParentNode)     &&
 379        !IS_AML_OBJECT_NODE (ParentNode))  ||
 380       (!IS_AML_DATA_NODE (NewNode)        &&
 381        !IS_AML_OBJECT_NODE (NewNode))     ||
 382       !AML_NODE_IS_DETACHED (NewNode)) {
 383     ASSERT (0);
 384     return EFI_INVALID_PARAMETER;
 385   }
 386
 387   // Insert it at the tail of the list.
 388   ChildrenList = AmlNodeGetVariableArgList (ParentNode);
 389   if (ChildrenList == NULL) {
 390     ASSERT (0);
 391     return EFI_INVALID_PARAMETER;
 392   }
 393
 394   InsertTailList (ChildrenList, &NewNode->Link);
 395   NewNode->Parent = ParentNode;
 396
 397   return EFI_SUCCESS;
 398 }
 399
 400 /** Add the NewNode to the tail of the variable list of arguments
 401     of the ParentNode.
 402
 403   @param  [in]  ParentNode  Pointer to the parent node.
 404                             Must be a root or an object node.
 405   @param  [in]  NewNode     Pointer to the node to add.
 406
 407   @retval EFI_SUCCESS             The function completed successfully.
 408   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 409 **/
 410 EFI_STATUS
 411 EFIAPI
 412 AmlVarListAddTail (
 413   IN  AML_NODE_HEADER   * ParentNode,
 414   IN  AML_NODE_HEADER   * NewNode
 415   )
 416 {
 417   EFI_STATUS  Status;
 418   UINT32      NewSize;
 419
 420   // Add the NewNode and check arguments.
 421   Status = AmlVarListAddTailInternal (ParentNode, NewNode);
 422   if (EFI_ERROR (Status)) {
 423     ASSERT (0);
 424     return Status;
 425   }
 426
 427   // Get the size of the NewNode.
 428   Status = AmlComputeSize (NewNode, &NewSize);
 429   if (EFI_ERROR (Status)) {
 430     ASSERT (0);
 431     return Status;
 432   }
 433
 434   // Propagate the new information.
 435   Status = AmlPropagateInformation (ParentNode, TRUE, NewSize, 1);
 436   ASSERT_EFI_ERROR (Status);
 437
 438   return Status;
 439 }
 440
 441 /** Add the NewNode before the Node in the list of variable
 442     arguments of the Node's parent.
 443
 444   @param  [in]  Node      Pointer to a node.
 445                           Must be a root or an object node.
 446   @param  [in]  NewNode   Pointer to the node to add.
 447
 448   @retval EFI_SUCCESS             The function completed successfully.
 449   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 450 **/
 451 EFI_STATUS
 452 EFIAPI
 453 AmlVarListAddBefore (
 454   IN  AML_NODE_HEADER  * Node,
 455   IN  AML_NODE_HEADER  * NewNode
 456   )
 457 {
 458   EFI_STATUS         Status;
 459   AML_NODE_HEADER  * ParentNode;
 460   UINT32             NewSize;
 461
 462   // Check arguments and that NewNode is not already attached to a tree.
 463   if ((!IS_AML_DATA_NODE (NewNode)        &&
 464        !IS_AML_OBJECT_NODE (NewNode))     ||
 465       !AML_NODE_IS_DETACHED (NewNode)) {
 466     ASSERT (0);
 467     return EFI_INVALID_PARAMETER;
 468   }
 469
 470   ParentNode = AmlGetParent (Node);
 471   if (!IS_AML_ROOT_NODE (ParentNode)    &&
 472       !IS_AML_OBJECT_NODE (ParentNode)) {
 473     ASSERT (0);
 474     return EFI_INVALID_PARAMETER;
 475   }
 476
 477   // Insert it before the input Node.
 478   InsertTailList (&Node->Link, &NewNode->Link);
 479   NewNode->Parent = ParentNode;
 480
 481   // Get the size of the NewNode.
 482   Status = AmlComputeSize (NewNode, &NewSize);
 483   if (EFI_ERROR (Status)) {
 484     ASSERT (0);
 485     return Status;
 486   }
 487
 488   // Propagate the new information.
 489   Status = AmlPropagateInformation (ParentNode, TRUE, NewSize, 1);
 490   ASSERT_EFI_ERROR (Status);
 491
 492   return Status;
 493 }
 494
 495 /** Add the NewNode after the Node in the variable list of arguments
 496     of the Node's parent.
 497
 498   @param  [in]  Node      Pointer to a node.
 499                           Must be a root or an object node.
 500   @param  [in]  NewNode   Pointer to the node to add.
 501
 502   @retval EFI_SUCCESS             The function completed successfully.
 503   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 504 **/
 505 EFI_STATUS
 506 EFIAPI
 507 AmlVarListAddAfter (
 508   IN  AML_NODE_HEADER   * Node,
 509   IN  AML_NODE_HEADER   * NewNode
 510   )
 511 {
 512   EFI_STATUS          Status;
 513   AML_NODE_HEADER   * ParentNode;
 514   UINT32              NewSize;
 515
 516   // Check arguments and that NewNode is not already attached to a tree.
 517   if ((!IS_AML_DATA_NODE (NewNode)        &&
 518        !IS_AML_OBJECT_NODE (NewNode))     ||
 519       !AML_NODE_IS_DETACHED (NewNode)) {
 520     ASSERT (0);
 521     return EFI_INVALID_PARAMETER;
 522   }
 523
 524   ParentNode = AmlGetParent (Node);
 525   if (!IS_AML_ROOT_NODE (ParentNode)    &&
 526       !IS_AML_OBJECT_NODE (ParentNode)) {
 527     ASSERT (0);
 528     return EFI_INVALID_PARAMETER;
 529   }
 530
 531   // Insert the new node after the input Node.
 532   InsertHeadList (&Node->Link, &NewNode->Link);
 533   NewNode->Parent = ParentNode;
 534
 535   // Get the size of the NewNode.
 536   Status = AmlComputeSize (NewNode, &NewSize);
 537   if (EFI_ERROR (Status)) {
 538     ASSERT (0);
 539     return Status;
 540   }
 541
 542   // Propagate the new information.
 543   Status = AmlPropagateInformation (ParentNode, TRUE, NewSize, 1);
 544   ASSERT_EFI_ERROR (Status);
 545
 546   return Status;
 547 }
 548
 549 /** Append a Resource Data node to the BufferOpNode.
 550
 551   The Resource Data node is added at the end of the variable
 552   list of arguments of the BufferOpNode, but before the End Tag.
 553   If no End Tag is found, the function returns an error.
 554
 555   @param  [in]  BufferOpNode  Buffer node containing resource data elements.
 556   @param  [in]  NewRdNode     The new Resource Data node to add.
 557
 558   @retval  EFI_SUCCESS            The function completed successfully.
 559   @retval  EFI_INVALID_PARAMETER  Invalid parameter.
 560 **/
 561 EFI_STATUS
 562 EFIAPI
 563 AmlAppendRdNode (
 564   IN  AML_OBJECT_NODE   * BufferOpNode,
 565   IN  AML_DATA_NODE     * NewRdNode
 566   )
 567 {
 568   EFI_STATUS        Status;
 569   AML_DATA_NODE   * LastRdNode;
 570
 571   if (!AmlNodeCompareOpCode (BufferOpNode, AML_BUFFER_OP, 0)  ||
 572       !IS_AML_DATA_NODE (NewRdNode)                           ||
 573       (NewRdNode->DataType != EAmlNodeDataTypeResourceData)) {
 574     ASSERT (0);
 575     return EFI_INVALID_PARAMETER;
 576   }
 577
 578   // To avoid re-computing checksums, if a new resource data elements is
 579   // added/removed/modified in a list of resource data elements, the AmlLib
 580   // resets the checksum to 0.
 581   // It is possible to have only one Resource Data in a BufferOp with
 582   // no EndTag, but it should not be possible to add a new Resource Data
 583   // in the list in this case.
 584   Status = AmlSetRdListCheckSum (BufferOpNode, 0);
 585   if (EFI_ERROR (Status)) {
 586     ASSERT (0);
 587     return Status;
 588   }
 589
 590   // Get the last Resource data node in the variable list of argument of the
 591   // BufferOp node. This must be an EndTag, otherwise setting the checksum
 592   // would have failed.
 593   LastRdNode = (AML_DATA_NODE*)AmlGetPreviousVariableArgument (
 594                                  (AML_NODE_HEADER*)BufferOpNode,
 595                                  NULL
 596                                  );
 597   if ((LastRdNode == NULL)             ||
 598       !IS_AML_DATA_NODE (LastRdNode)   ||
 599       (LastRdNode->DataType != EAmlNodeDataTypeResourceData)) {
 600     ASSERT (0);
 601     return EFI_INVALID_PARAMETER;
 602   }
 603
 604   // Add NewRdNode before the EndTag.
 605   Status = AmlVarListAddBefore (
 606              (AML_NODE_HEADER*)LastRdNode,
 607              (AML_NODE_HEADER*)NewRdNode)
 608              ;
 609   ASSERT_EFI_ERROR (Status);
 610   return Status;
 611 }
 612
 613 /** Replace the fixed argument at the Index of the ParentNode with the NewNode.
 614
 615   Note: This function unlinks the OldNode from the tree. It is the callers
 616         responsibility to delete the OldNode if needed.
 617
 618   @param  [in]  ParentNode  Pointer to the parent node.
 619                             Must be an object node.
 620   @param  [in]  Index       Index of the fixed argument to replace.
 621   @param  [in]  NewNode     The new node to insert.
 622                             Must be an object node or a data node.
 623
 624   @retval EFI_SUCCESS             The function completed successfully.
 625   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 626 **/
 627 STATIC
 628 EFI_STATUS
 629 EFIAPI
 630 AmlReplaceFixedArgument (
 631   IN  AML_OBJECT_NODE      * ParentNode,
 632   IN  EAML_PARSE_INDEX       Index,
 633   IN  AML_NODE_HEADER      * NewNode
 634   )
 635 {
 636   EFI_STATUS              Status;
 637
 638   AML_NODE_HEADER       * OldNode;
 639   UINT32                  NewSize;
 640   UINT32                  OldSize;
 641   AML_PARSE_FORMAT        FixedArgType;
 642
 643   // Check arguments and that NewNode is not already attached to a tree.
 644   if (!IS_AML_OBJECT_NODE (ParentNode)  ||
 645       (!IS_AML_DATA_NODE (NewNode)      &&
 646        !IS_AML_OBJECT_NODE (NewNode))   ||
 647       !AML_NODE_IS_DETACHED (NewNode)) {
 648     ASSERT (0);
 649     return EFI_INVALID_PARAMETER;
 650   }
 651
 652   // Perform some compatibility checks between NewNode and OldNode.
 653   FixedArgType = ParentNode->AmlByteEncoding->Format[Index];
 654   switch (FixedArgType) {
 655     case EAmlFieldPkgLen:
 656     {
 657       // A FieldPkgLen can only have a parent node with the
 658       // AML_IS_FIELD_ELEMENT flag.
 659       if (!AmlNodeHasAttribute (
 660              (AML_OBJECT_NODE*)ParentNode,
 661              AML_HAS_FIELD_LIST)) {
 662         ASSERT (0);
 663         return EFI_INVALID_PARAMETER;
 664       }
 665       // Fall through.
 666     }
 667
 668     case EAmlUInt8:
 669     case EAmlUInt16:
 670     case EAmlUInt32:
 671     case EAmlUInt64:
 672     case EAmlName:
 673     case EAmlString:
 674     {
 675       // A uint, a name, a string and a FieldPkgLen can only be replaced by a
 676       // data node of the same type.
 677       // Note: This condition might be too strict, but safer.
 678       if (!IS_AML_DATA_NODE (NewNode) ||
 679           (((AML_DATA_NODE*)NewNode)->DataType !=
 680             AmlTypeToNodeDataType (FixedArgType))) {
 681         ASSERT (0);
 682         return EFI_INVALID_PARAMETER;
 683       }
 684       break;
 685     }
 686
 687     case EAmlObject:
 688     {
 689       // If it's an object node, the grammar is too complex to do any check.
 690       break;
 691     }
 692
 693     case EAmlNone:
 694     default:
 695     {
 696       ASSERT (0);
 697       return EFI_INVALID_PARAMETER;
 698       break;
 699     }
 700   } // switch
 701
 702   // Replace the OldNode with the NewNode.
 703   OldNode = AmlGetFixedArgument (ParentNode, Index);
 704   if (!IS_AML_NODE_VALID (OldNode)) {
 705     ASSERT (0);
 706     return EFI_INVALID_PARAMETER;
 707   }
 708
 709   // Unlink the old node.
 710   // Note: This function unlinks the OldNode from the tree. It is the callers
 711   //       responsibility to delete the OldNode if needed.
 712   OldNode->Parent = NULL;
 713
 714   Status = AmlSetFixedArgument (ParentNode, Index, NewNode);
 715   if (EFI_ERROR (Status)) {
 716     ASSERT (0);
 717     return Status;
 718   }
 719
 720   // Get the size of the OldNode.
 721   Status = AmlComputeSize (OldNode, &OldSize);
 722   if (EFI_ERROR (Status)) {
 723     ASSERT (0);
 724     return Status;
 725   }
 726
 727   // Get the size of the NewNode.
 728   Status = AmlComputeSize (NewNode, &NewSize);
 729   if (EFI_ERROR (Status)) {
 730     ASSERT (0);
 731     return Status;
 732   }
 733
 734   // Propagate the new information.
 735   Status = AmlPropagateInformation (
 736             (AML_NODE_HEADER*)ParentNode,
 737             (NewSize > OldSize) ? TRUE : FALSE,
 738             (NewSize > OldSize) ? (NewSize - OldSize) : (OldSize - NewSize),
 739             0
 740             );
 741   ASSERT_EFI_ERROR (Status);
 742
 743   return Status;
 744 }
 745
 746 /** Replace the OldNode, which is in a variable list of arguments,
 747     with the NewNode.
 748
 749   Note: This function unlinks the OldNode from the tree. It is the callers
 750         responsibility to delete the OldNode if needed.
 751
 752   @param  [in]  OldNode   Pointer to the node to replace.
 753                           Must be a data node or an object node.
 754   @param  [in]  NewNode   The new node to insert.
 755                           Must be a data node or an object node.
 756
 757   @retval EFI_SUCCESS             The function completed successfully.
 758   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 759 **/
 760 EFI_STATUS
 761 EFIAPI
 762 AmlReplaceVariableArgument (
 763   IN  AML_NODE_HEADER   * OldNode,
 764   IN  AML_NODE_HEADER   * NewNode
 765   )
 766 {
 767   EFI_STATUS          Status;
 768   UINT32              NewSize;
 769   UINT32              OldSize;
 770   EAML_PARSE_INDEX    Index;
 771
 772   AML_DATA_NODE     * NewDataNode;
 773   AML_NODE_HEADER   * ParentNode;
 774   LIST_ENTRY        * NextLink;
 775
 776   // Check arguments, that NewNode is not already attached to a tree,
 777   // and that OldNode is attached and not in a fixed list of arguments.
 778   if ((!IS_AML_DATA_NODE (OldNode)      &&
 779        !IS_AML_OBJECT_NODE (OldNode))   ||
 780       (!IS_AML_DATA_NODE (NewNode)      &&
 781        !IS_AML_OBJECT_NODE (NewNode))   ||
 782       !AML_NODE_IS_DETACHED (NewNode)   ||
 783       AML_NODE_IS_DETACHED (OldNode)    ||
 784       AmlIsNodeFixedArgument (OldNode, &Index)) {
 785     ASSERT (0);
 786     return EFI_INVALID_PARAMETER;
 787   }
 788
 789   ParentNode = AmlGetParent (OldNode);
 790     if (!IS_AML_ROOT_NODE (ParentNode)    &&
 791         !IS_AML_OBJECT_NODE (ParentNode)) {
 792     ASSERT (0);
 793     return EFI_INVALID_PARAMETER;
 794   }
 795
 796   NewDataNode = (AML_DATA_NODE*)NewNode;
 797
 798   // Check attributes if the parent node is an object node.
 799   if (IS_AML_OBJECT_NODE (ParentNode)) {
 800     // A child node of a node with the HAS_CHILD flag must be either a
 801     // data node or an object node. This has already been checked. So,
 802     // check for other cases.
 803
 804     if (AmlNodeHasAttribute ((AML_OBJECT_NODE*)ParentNode, AML_HAS_BYTE_LIST)) {
 805       if (!IS_AML_DATA_NODE (NewNode)                       ||
 806           ((NewDataNode->DataType != EAmlNodeDataTypeRaw)   &&
 807            (NewDataNode->DataType != EAmlNodeDataTypeResourceData))) {
 808         // A child node of a node with the BYTE_LIST flag must be a data node,
 809         // containing raw data or a resource data.
 810         ASSERT (0);
 811         return EFI_INVALID_PARAMETER;
 812       }
 813     } else if (AmlNodeHasAttribute (
 814                 (AML_OBJECT_NODE*)ParentNode,
 815                 AML_HAS_FIELD_LIST)) {
 816       if (!AmlNodeHasAttribute (
 817              (CONST AML_OBJECT_NODE*)NewNode,
 818               AML_IS_FIELD_ELEMENT)) {
 819         // A child node of a node with the FIELD_LIST flag must be an object
 820         // node with AML_IS_FIELD_ELEMENT flag.
 821         ASSERT (0);
 822         return EFI_INVALID_PARAMETER;
 823       }
 824     }
 825   } else {
 826     // Parent node is a root node.
 827     // A root node cannot have a data node as its child.
 828     if (!IS_AML_DATA_NODE (NewNode)) {
 829       ASSERT (0);
 830       return EFI_INVALID_PARAMETER;
 831     }
 832   }
 833
 834   // Unlink OldNode from the tree.
 835   NextLink = RemoveEntryList (&OldNode->Link);
 836   InitializeListHead (&OldNode->Link);
 837   OldNode->Parent = NULL;
 838
 839   // Add the NewNode.
 840   InsertHeadList (NextLink, &NewNode->Link);
 841   NewNode->Parent = ParentNode;
 842
 843   // Get the size of the OldNode.
 844   Status = AmlComputeSize (OldNode, &OldSize);
 845   if (EFI_ERROR (Status)) {
 846     ASSERT (0);
 847     return Status;
 848   }
 849
 850   // Get the size of the NewNode.
 851   Status = AmlComputeSize (NewNode, &NewSize);
 852   if (EFI_ERROR (Status)) {
 853     ASSERT (0);
 854     return Status;
 855   }
 856
 857   // Propagate the new information.
 858   Status = AmlPropagateInformation (
 859              ParentNode,
 860              (NewSize > OldSize) ? TRUE : FALSE,
 861              (NewSize > OldSize) ? (NewSize - OldSize) : (OldSize - NewSize),
 862              0
 863              );
 864   ASSERT_EFI_ERROR (Status);
 865
 866   return Status;
 867 }
 868
 869 /** Replace the OldNode by the NewNode.
 870
 871   Note: This function unlinks the OldNode from the tree. It is the callers
 872         responsibility to delete the OldNode if needed.
 873
 874   @param  [in]  OldNode   Pointer to the node to replace.
 875                           Must be a data node or an object node.
 876   @param  [in]  NewNode   The new node to insert.
 877                           Must be a data node or an object node.
 878
 879   @retval EFI_SUCCESS             The function completed successfully.
 880   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 881 **/
 882 EFI_STATUS
 883 EFIAPI
 884 AmlReplaceArgument (
 885   IN  AML_NODE_HEADER   * OldNode,
 886   IN  AML_NODE_HEADER   * NewNode
 887   )
 888 {
 889   EFI_STATUS            Status;
 890   AML_NODE_HEADER     * ParentNode;
 891   EAML_PARSE_INDEX      Index;
 892
 893   // Check arguments and that NewNode is not already attached to a tree.
 894   if ((!IS_AML_DATA_NODE (OldNode)      &&
 895        !IS_AML_OBJECT_NODE (OldNode))   ||
 896       (!IS_AML_DATA_NODE (NewNode)      &&
 897        !IS_AML_OBJECT_NODE (NewNode))   ||
 898       !AML_NODE_IS_DETACHED (NewNode)) {
 899     ASSERT (0);
 900     return EFI_INVALID_PARAMETER;
 901   }
 902
 903   // ParentNode can be a root node or an object node.
 904   ParentNode = AmlGetParent (OldNode);
 905   if (!IS_AML_ROOT_NODE (ParentNode)  &&
 906       !IS_AML_OBJECT_NODE (ParentNode)) {
 907     ASSERT (0);
 908     return EFI_INVALID_PARAMETER;
 909   }
 910
 911   if (AmlIsNodeFixedArgument (OldNode, &Index)) {
 912     // OldNode is in its parent's fixed argument list at the Index.
 913     Status = AmlReplaceFixedArgument (
 914                (AML_OBJECT_NODE*)ParentNode,
 915                Index,
 916                NewNode
 917                );
 918     if (EFI_ERROR (Status)) {
 919       ASSERT (0);
 920       return Status;
 921     }
 922   } else {
 923     // OldNode is not in its parent's fixed argument list.
 924     // It must be in its variable list of arguments.
 925     Status = AmlReplaceVariableArgument (OldNode, NewNode);
 926     ASSERT_EFI_ERROR (Status);
 927   }
 928
 929   return Status;
 930 }
 931
 932 /** Delete a Node and its children.
 933
 934   The Node must be removed from the tree first,
 935   or must be the root node.
 936
 937   @param  [in]  Node  Pointer to the node to delete.
 938
 939   @retval EFI_SUCCESS             The function completed successfully.
 940   @retval EFI_INVALID_PARAMETER   Invalid parameter.
 941 **/
 942 EFI_STATUS
 943 EFIAPI
 944 AmlDeleteTree (
 945   IN  AML_NODE_HEADER  * Node
 946   )
 947 {
 948   EFI_STATUS            Status;
 949
 950   EAML_PARSE_INDEX      Index;
 951   EAML_PARSE_INDEX      MaxIndex;
 952
 953   AML_NODE_HEADER     * Arg;
 954   LIST_ENTRY          * StartLink;
 955   LIST_ENTRY          * CurrentLink;
 956   LIST_ENTRY          * NextLink;
 957
 958   // Check that the node being deleted is unlinked.
 959   // When removing the node, its parent pointer and
 960   // its lists data structure are reset with
 961   // InitializeListHead. Thus it must be detached
 962   // from the tree to avoid memory leaks.
 963   if (!IS_AML_NODE_VALID (Node)  ||
 964       !AML_NODE_IS_DETACHED (Node)) {
 965     ASSERT (0);
 966     return EFI_INVALID_PARAMETER;
 967   }
 968
 969   // 1. Recursively detach and delete the fixed arguments.
 970   //    Iterate through the fixed list of arguments.
 971   if (IS_AML_OBJECT_NODE (Node)) {
 972     MaxIndex = (EAML_PARSE_INDEX)AmlGetFixedArgumentCount (
 973                                    (AML_OBJECT_NODE*)Node
 974                                    );
 975     for (Index = EAmlParseIndexTerm0; Index < MaxIndex; Index++) {
 976       Arg = AmlGetFixedArgument ((AML_OBJECT_NODE*)Node, Index);
 977       if (Arg == NULL) {
 978         // A fixed argument is missing. The tree is inconsistent.
 979         // Note: During CodeGeneration, the fixed arguments should be set
 980         //       with an incrementing index, and then the variable arguments
 981         //       should be added. This allows to free as many nodes as
 982         //       possible if a crash occurs.
 983         ASSERT (0);
 984         return EFI_INVALID_PARAMETER;
 985       }
 986
 987       // Remove the node from the fixed argument list.
 988       Arg->Parent = NULL;
 989       Status = AmlSetFixedArgument ((AML_OBJECT_NODE*)Node, Index, NULL);
 990       if (EFI_ERROR (Status)) {
 991         ASSERT (0);
 992         return Status;
 993       }
 994
 995       Status = AmlDeleteTree (Arg);
 996       if (EFI_ERROR (Status)) {
 997         ASSERT (0);
 998         return Status;
 999       }
1000     }
1001   }
1002
1003   // 2. Recursively detach and delete the variable arguments.
1004   //    Iterate through the variable list of arguments.
1005   StartLink = AmlNodeGetVariableArgList (Node);
1006   if (StartLink != NULL) {
1007     NextLink = StartLink->ForwardLink;
1008     while (NextLink != StartLink) {
1009       CurrentLink = NextLink;
1010
1011       // Unlink the node from the tree.
1012       NextLink = RemoveEntryList (CurrentLink);
1013       InitializeListHead (CurrentLink);
1014       ((AML_NODE_HEADER*)CurrentLink)->Parent = NULL;
1015
1016       Status = AmlDeleteTree ((AML_NODE_HEADER*)CurrentLink);
1017       if (EFI_ERROR (Status)) {
1018         ASSERT (0);
1019         return Status;
1020       }
1021     } // while
1022   }
1023
1024   // 3. Delete the node.
1025   Status = AmlDeleteNode (Node);
1026   ASSERT_EFI_ERROR (Status);
1027
1028   return Status;
1029 }