1 2 /****************************************************************************** 3 * 4 * Module Name: asltree - parse tree management 5 * 6 *****************************************************************************/ 7 8 /* 9 * Copyright (C) 2000 - 2011, Intel Corp. 10 * All rights reserved. 11 * 12 * Redistribution and use in source and binary forms, with or without 13 * modification, are permitted provided that the following conditions 14 * are met: 15 * 1. Redistributions of source code must retain the above copyright 16 * notice, this list of conditions, and the following disclaimer, 17 * without modification. 18 * 2. Redistributions in binary form must reproduce at minimum a disclaimer 19 * substantially similar to the "NO WARRANTY" disclaimer below 20 * ("Disclaimer") and any redistribution must be conditioned upon 21 * including a substantially similar Disclaimer requirement for further 22 * binary redistribution. 23 * 3. Neither the names of the above-listed copyright holders nor the names 24 * of any contributors may be used to endorse or promote products derived 25 * from this software without specific prior written permission. 26 * 27 * Alternatively, this software may be distributed under the terms of the 28 * GNU General Public License ("GPL") version 2 as published by the Free 29 * Software Foundation. 30 * 31 * NO WARRANTY 32 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 33 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 34 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR 35 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 36 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 37 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 38 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 39 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, 40 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING 41 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 42 * POSSIBILITY OF SUCH DAMAGES. 43 */ 44 45 46 #include <contrib/dev/acpica/compiler/aslcompiler.h> 47 #include "aslcompiler.y.h" 48 49 #define _COMPONENT ACPI_COMPILER 50 ACPI_MODULE_NAME ("asltree") 51 52 /* Local prototypes */ 53 54 static ACPI_PARSE_OBJECT * 55 TrGetNextNode ( 56 void); 57 58 static char * 59 TrGetNodeFlagName ( 60 UINT32 Flags); 61 62 63 /******************************************************************************* 64 * 65 * FUNCTION: TrGetNextNode 66 * 67 * PARAMETERS: None 68 * 69 * RETURN: New parse node. Aborts on allocation failure 70 * 71 * DESCRIPTION: Allocate a new parse node for the parse tree. Bypass the local 72 * dynamic memory manager for performance reasons (This has a 73 * major impact on the speed of the compiler.) 74 * 75 ******************************************************************************/ 76 77 static ACPI_PARSE_OBJECT * 78 TrGetNextNode ( 79 void) 80 { 81 82 if (Gbl_NodeCacheNext >= Gbl_NodeCacheLast) 83 { 84 Gbl_NodeCacheNext = UtLocalCalloc (sizeof (ACPI_PARSE_OBJECT) * 85 ASL_NODE_CACHE_SIZE); 86 Gbl_NodeCacheLast = Gbl_NodeCacheNext + ASL_NODE_CACHE_SIZE; 87 } 88 89 return (Gbl_NodeCacheNext++); 90 } 91 92 93 /******************************************************************************* 94 * 95 * FUNCTION: TrAllocateNode 96 * 97 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node 98 * 99 * RETURN: New parse node. Aborts on allocation failure 100 * 101 * DESCRIPTION: Allocate and initialize a new parse node for the parse tree 102 * 103 ******************************************************************************/ 104 105 ACPI_PARSE_OBJECT * 106 TrAllocateNode ( 107 UINT32 ParseOpcode) 108 { 109 ACPI_PARSE_OBJECT *Op; 110 111 112 Op = TrGetNextNode (); 113 114 Op->Asl.ParseOpcode = (UINT16) ParseOpcode; 115 Op->Asl.Filename = Gbl_Files[ASL_FILE_INPUT].Filename; 116 Op->Asl.LineNumber = Gbl_CurrentLineNumber; 117 Op->Asl.LogicalLineNumber = Gbl_LogicalLineNumber; 118 Op->Asl.LogicalByteOffset = Gbl_CurrentLineOffset; 119 Op->Asl.Column = Gbl_CurrentColumn; 120 121 UtSetParseOpName (Op); 122 return Op; 123 } 124 125 126 /******************************************************************************* 127 * 128 * FUNCTION: TrReleaseNode 129 * 130 * PARAMETERS: Op - Op to be released 131 * 132 * RETURN: None 133 * 134 * DESCRIPTION: "release" a node. In truth, nothing is done since the node 135 * is part of a larger buffer 136 * 137 ******************************************************************************/ 138 139 void 140 TrReleaseNode ( 141 ACPI_PARSE_OBJECT *Op) 142 { 143 144 return; 145 } 146 147 148 /******************************************************************************* 149 * 150 * FUNCTION: TrUpdateNode 151 * 152 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 153 * Op - An existing parse node 154 * 155 * RETURN: The updated node 156 * 157 * DESCRIPTION: Change the parse opcode assigned to a node. Usually used to 158 * change an opcode to DEFAULT_ARG so that the node is ignored 159 * during the code generation. Also used to set generic integers 160 * to a specific size (8, 16, 32, or 64 bits) 161 * 162 ******************************************************************************/ 163 164 ACPI_PARSE_OBJECT * 165 TrUpdateNode ( 166 UINT32 ParseOpcode, 167 ACPI_PARSE_OBJECT *Op) 168 { 169 170 if (!Op) 171 { 172 return NULL; 173 } 174 175 DbgPrint (ASL_PARSE_OUTPUT, 176 "\nUpdateNode: Old - %s, New - %s\n\n", 177 UtGetOpName (Op->Asl.ParseOpcode), 178 UtGetOpName (ParseOpcode)); 179 180 /* Assign new opcode and name */ 181 182 if (Op->Asl.ParseOpcode == PARSEOP_ONES) 183 { 184 switch (ParseOpcode) 185 { 186 case PARSEOP_BYTECONST: 187 Op->Asl.Value.Integer = 0xFF; 188 break; 189 190 case PARSEOP_WORDCONST: 191 Op->Asl.Value.Integer = 0xFFFF; 192 break; 193 194 case PARSEOP_DWORDCONST: 195 Op->Asl.Value.Integer = 0xFFFFFFFF; 196 break; 197 198 default: 199 /* Don't care about others, don't need to check QWORD */ 200 break; 201 } 202 } 203 204 Op->Asl.ParseOpcode = (UINT16) ParseOpcode; 205 UtSetParseOpName (Op); 206 207 /* 208 * For the BYTE, WORD, and DWORD constants, make sure that the integer 209 * that was passed in will actually fit into the data type 210 */ 211 switch (ParseOpcode) 212 { 213 case PARSEOP_BYTECONST: 214 Op = UtCheckIntegerRange (Op, 0x00, ACPI_UINT8_MAX); 215 break; 216 217 case PARSEOP_WORDCONST: 218 Op = UtCheckIntegerRange (Op, 0x00, ACPI_UINT16_MAX); 219 break; 220 221 case PARSEOP_DWORDCONST: 222 Op = UtCheckIntegerRange (Op, 0x00, ACPI_UINT32_MAX); 223 break; 224 225 default: 226 /* Don't care about others, don't need to check QWORD */ 227 break; 228 } 229 230 return Op; 231 } 232 233 234 /******************************************************************************* 235 * 236 * FUNCTION: TrGetNodeFlagName 237 * 238 * PARAMETERS: Flags - Flags word to be decoded 239 * 240 * RETURN: Name string. Always returns a valid string pointer. 241 * 242 * DESCRIPTION: Decode a flags word 243 * 244 ******************************************************************************/ 245 246 static char * 247 TrGetNodeFlagName ( 248 UINT32 Flags) 249 { 250 251 switch (Flags) 252 { 253 case NODE_VISITED: 254 return ("NODE_VISITED"); 255 256 case NODE_AML_PACKAGE: 257 return ("NODE_AML_PACKAGE"); 258 259 case NODE_IS_TARGET: 260 return ("NODE_IS_TARGET"); 261 262 case NODE_IS_RESOURCE_DESC: 263 return ("NODE_IS_RESOURCE_DESC"); 264 265 case NODE_IS_RESOURCE_FIELD: 266 return ("NODE_IS_RESOURCE_FIELD"); 267 268 case NODE_HAS_NO_EXIT: 269 return ("NODE_HAS_NO_EXIT"); 270 271 case NODE_IF_HAS_NO_EXIT: 272 return ("NODE_IF_HAS_NO_EXIT"); 273 274 case NODE_NAME_INTERNALIZED: 275 return ("NODE_NAME_INTERNALIZED"); 276 277 case NODE_METHOD_NO_RETVAL: 278 return ("NODE_METHOD_NO_RETVAL"); 279 280 case NODE_METHOD_SOME_NO_RETVAL: 281 return ("NODE_METHOD_SOME_NO_RETVAL"); 282 283 case NODE_RESULT_NOT_USED: 284 return ("NODE_RESULT_NOT_USED"); 285 286 case NODE_METHOD_TYPED: 287 return ("NODE_METHOD_TYPED"); 288 289 case NODE_IS_BIT_OFFSET: 290 return ("NODE_IS_BIT_OFFSET"); 291 292 case NODE_COMPILE_TIME_CONST: 293 return ("NODE_COMPILE_TIME_CONST"); 294 295 case NODE_IS_TERM_ARG: 296 return ("NODE_IS_TERM_ARG"); 297 298 case NODE_WAS_ONES_OP: 299 return ("NODE_WAS_ONES_OP"); 300 301 case NODE_IS_NAME_DECLARATION: 302 return ("NODE_IS_NAME_DECLARATION"); 303 304 default: 305 return ("Multiple Flags (or unknown flag) set"); 306 } 307 } 308 309 310 /******************************************************************************* 311 * 312 * FUNCTION: TrSetNodeFlags 313 * 314 * PARAMETERS: Op - An existing parse node 315 * Flags - New flags word 316 * 317 * RETURN: The updated parser op 318 * 319 * DESCRIPTION: Set bits in the node flags word. Will not clear bits, only set 320 * 321 ******************************************************************************/ 322 323 ACPI_PARSE_OBJECT * 324 TrSetNodeFlags ( 325 ACPI_PARSE_OBJECT *Op, 326 UINT32 Flags) 327 { 328 329 DbgPrint (ASL_PARSE_OUTPUT, 330 "\nSetNodeFlags: Op %p, %8.8X %s\n\n", Op, Flags, 331 TrGetNodeFlagName (Flags)); 332 333 if (!Op) 334 { 335 return NULL; 336 } 337 338 Op->Asl.CompileFlags |= Flags; 339 340 return Op; 341 } 342 343 344 /******************************************************************************* 345 * 346 * FUNCTION: TrSetEndLineNumber 347 * 348 * PARAMETERS: Op - An existing parse node 349 * 350 * RETURN: None. 351 * 352 * DESCRIPTION: Set the ending line numbers (file line and logical line) of a 353 * parse node to the current line numbers. 354 * 355 ******************************************************************************/ 356 357 void 358 TrSetEndLineNumber ( 359 ACPI_PARSE_OBJECT *Op) 360 { 361 362 /* If the end line # is already set, just return */ 363 364 if (Op->Asl.EndLine) 365 { 366 return; 367 } 368 369 Op->Asl.EndLine = Gbl_CurrentLineNumber; 370 Op->Asl.EndLogicalLine = Gbl_LogicalLineNumber; 371 } 372 373 374 /******************************************************************************* 375 * 376 * FUNCTION: TrCreateLeafNode 377 * 378 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 379 * 380 * RETURN: Pointer to the new node. Aborts on allocation failure 381 * 382 * DESCRIPTION: Create a simple leaf node (no children or peers, and no value 383 * assigned to the node) 384 * 385 ******************************************************************************/ 386 387 ACPI_PARSE_OBJECT * 388 TrCreateLeafNode ( 389 UINT32 ParseOpcode) 390 { 391 ACPI_PARSE_OBJECT *Op; 392 393 394 Op = TrAllocateNode (ParseOpcode); 395 396 DbgPrint (ASL_PARSE_OUTPUT, 397 "\nCreateLeafNode Ln/Col %u/%u NewNode %p Op %s\n\n", 398 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode)); 399 400 return Op; 401 } 402 403 404 /******************************************************************************* 405 * 406 * FUNCTION: TrCreateValuedLeafNode 407 * 408 * PARAMETERS: ParseOpcode - New opcode to be assigned to the node 409 * Value - Value to be assigned to the node 410 * 411 * RETURN: Pointer to the new node. Aborts on allocation failure 412 * 413 * DESCRIPTION: Create a leaf node (no children or peers) with a value 414 * assigned to it 415 * 416 ******************************************************************************/ 417 418 ACPI_PARSE_OBJECT * 419 TrCreateValuedLeafNode ( 420 UINT32 ParseOpcode, 421 UINT64 Value) 422 { 423 ACPI_PARSE_OBJECT *Op; 424 425 426 Op = TrAllocateNode (ParseOpcode); 427 428 DbgPrint (ASL_PARSE_OUTPUT, 429 "\nCreateValuedLeafNode Ln/Col %u/%u NewNode %p Op %s Value %8.8X%8.8X ", 430 Op->Asl.LineNumber, Op->Asl.Column, Op, UtGetOpName(ParseOpcode), 431 ACPI_FORMAT_UINT64 (Value)); 432 Op->Asl.Value.Integer = Value; 433 434 switch (ParseOpcode) 435 { 436 case PARSEOP_STRING_LITERAL: 437 DbgPrint (ASL_PARSE_OUTPUT, "STRING->%s", Value); 438 break; 439 440 case PARSEOP_NAMESEG: 441 DbgPrint (ASL_PARSE_OUTPUT, "NAMESEG->%s", Value); 442 break; 443 444 case PARSEOP_NAMESTRING: 445 DbgPrint (ASL_PARSE_OUTPUT, "NAMESTRING->%s", Value); 446 break; 447 448 case PARSEOP_EISAID: 449 DbgPrint (ASL_PARSE_OUTPUT, "EISAID->%s", Value); 450 break; 451 452 case PARSEOP_METHOD: 453 DbgPrint (ASL_PARSE_OUTPUT, "METHOD"); 454 break; 455 456 case PARSEOP_INTEGER: 457 DbgPrint (ASL_PARSE_OUTPUT, "INTEGER"); 458 break; 459 460 default: 461 break; 462 } 463 464 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 465 return Op; 466 } 467 468 469 /******************************************************************************* 470 * 471 * FUNCTION: TrCreateNode 472 * 473 * PARAMETERS: ParseOpcode - Opcode to be assigned to the node 474 * NumChildren - Number of children to follow 475 * ... - A list of child nodes to link to the new 476 * node. NumChildren long. 477 * 478 * RETURN: Pointer to the new node. Aborts on allocation failure 479 * 480 * DESCRIPTION: Create a new parse node and link together a list of child 481 * nodes underneath the new node. 482 * 483 ******************************************************************************/ 484 485 ACPI_PARSE_OBJECT * 486 TrCreateNode ( 487 UINT32 ParseOpcode, 488 UINT32 NumChildren, 489 ...) 490 { 491 ACPI_PARSE_OBJECT *Op; 492 ACPI_PARSE_OBJECT *Child; 493 ACPI_PARSE_OBJECT *PrevChild; 494 va_list ap; 495 UINT32 i; 496 BOOLEAN FirstChild; 497 498 499 va_start (ap, NumChildren); 500 501 /* Allocate one new node */ 502 503 Op = TrAllocateNode (ParseOpcode); 504 505 DbgPrint (ASL_PARSE_OUTPUT, 506 "\nCreateNode Ln/Col %u/%u NewParent %p Child %u Op %s ", 507 Op->Asl.LineNumber, Op->Asl.Column, Op, NumChildren, UtGetOpName(ParseOpcode)); 508 509 /* Some extra debug output based on the parse opcode */ 510 511 switch (ParseOpcode) 512 { 513 case PARSEOP_DEFINITIONBLOCK: 514 RootNode = Op; 515 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 516 break; 517 518 case PARSEOP_OPERATIONREGION: 519 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 520 break; 521 522 case PARSEOP_OR: 523 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 524 break; 525 526 default: 527 /* Nothing to do for other opcodes */ 528 break; 529 } 530 531 /* Link the new node to its children */ 532 533 PrevChild = NULL; 534 FirstChild = TRUE; 535 for (i = 0; i < NumChildren; i++) 536 { 537 /* Get the next child */ 538 539 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 540 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 541 542 /* 543 * If child is NULL, this means that an optional argument 544 * was omitted. We must create a placeholder with a special 545 * opcode (DEFAULT_ARG) so that the code generator will know 546 * that it must emit the correct default for this argument 547 */ 548 if (!Child) 549 { 550 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 551 } 552 553 /* Link first child to parent */ 554 555 if (FirstChild) 556 { 557 FirstChild = FALSE; 558 Op->Asl.Child = Child; 559 } 560 561 /* Point all children to parent */ 562 563 Child->Asl.Parent = Op; 564 565 /* Link children in a peer list */ 566 567 if (PrevChild) 568 { 569 PrevChild->Asl.Next = Child; 570 }; 571 572 /* 573 * This child might be a list, point all nodes in the list 574 * to the same parent 575 */ 576 while (Child->Asl.Next) 577 { 578 Child = Child->Asl.Next; 579 Child->Asl.Parent = Op; 580 } 581 582 PrevChild = Child; 583 } 584 va_end(ap); 585 586 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 587 return Op; 588 } 589 590 591 /******************************************************************************* 592 * 593 * FUNCTION: TrLinkChildren 594 * 595 * PARAMETERS: Op - An existing parse node 596 * NumChildren - Number of children to follow 597 * ... - A list of child nodes to link to the new 598 * node. NumChildren long. 599 * 600 * RETURN: The updated (linked) node 601 * 602 * DESCRIPTION: Link a group of nodes to an existing parse node 603 * 604 ******************************************************************************/ 605 606 ACPI_PARSE_OBJECT * 607 TrLinkChildren ( 608 ACPI_PARSE_OBJECT *Op, 609 UINT32 NumChildren, 610 ...) 611 { 612 ACPI_PARSE_OBJECT *Child; 613 ACPI_PARSE_OBJECT *PrevChild; 614 va_list ap; 615 UINT32 i; 616 BOOLEAN FirstChild; 617 618 619 va_start (ap, NumChildren); 620 621 622 TrSetEndLineNumber (Op); 623 624 DbgPrint (ASL_PARSE_OUTPUT, 625 "\nLinkChildren Line [%u to %u] NewParent %p Child %u Op %s ", 626 Op->Asl.LineNumber, Op->Asl.EndLine, 627 Op, NumChildren, UtGetOpName(Op->Asl.ParseOpcode)); 628 629 switch (Op->Asl.ParseOpcode) 630 { 631 case PARSEOP_DEFINITIONBLOCK: 632 RootNode = Op; 633 DbgPrint (ASL_PARSE_OUTPUT, "DEFINITION_BLOCK (Tree Completed)->"); 634 break; 635 636 case PARSEOP_OPERATIONREGION: 637 DbgPrint (ASL_PARSE_OUTPUT, "OPREGION->"); 638 break; 639 640 case PARSEOP_OR: 641 DbgPrint (ASL_PARSE_OUTPUT, "OR->"); 642 break; 643 644 default: 645 /* Nothing to do for other opcodes */ 646 break; 647 } 648 649 /* Link the new node to it's children */ 650 651 PrevChild = NULL; 652 FirstChild = TRUE; 653 for (i = 0; i < NumChildren; i++) 654 { 655 Child = va_arg (ap, ACPI_PARSE_OBJECT *); 656 657 if ((Child == PrevChild) && (Child != NULL)) 658 { 659 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Child, 660 "Child node list invalid"); 661 return Op; 662 } 663 664 DbgPrint (ASL_PARSE_OUTPUT, "%p, ", Child); 665 666 /* 667 * If child is NULL, this means that an optional argument 668 * was omitted. We must create a placeholder with a special 669 * opcode (DEFAULT_ARG) so that the code generator will know 670 * that it must emit the correct default for this argument 671 */ 672 if (!Child) 673 { 674 Child = TrAllocateNode (PARSEOP_DEFAULT_ARG); 675 } 676 677 /* Link first child to parent */ 678 679 if (FirstChild) 680 { 681 FirstChild = FALSE; 682 Op->Asl.Child = Child; 683 } 684 685 /* Point all children to parent */ 686 687 Child->Asl.Parent = Op; 688 689 /* Link children in a peer list */ 690 691 if (PrevChild) 692 { 693 PrevChild->Asl.Next = Child; 694 }; 695 696 /* 697 * This child might be a list, point all nodes in the list 698 * to the same parent 699 */ 700 while (Child->Asl.Next) 701 { 702 Child = Child->Asl.Next; 703 Child->Asl.Parent = Op; 704 } 705 PrevChild = Child; 706 } 707 va_end(ap); 708 709 DbgPrint (ASL_PARSE_OUTPUT, "\n\n"); 710 return Op; 711 } 712 713 714 /******************************************************************************* 715 * 716 * FUNCTION: TrLinkPeerNode 717 * 718 * PARAMETERS: Op1 - First peer 719 * Op2 - Second peer 720 * 721 * RETURN: Op1 or the non-null node. 722 * 723 * DESCRIPTION: Link two nodes as peers. Handles cases where one peer is null. 724 * 725 ******************************************************************************/ 726 727 ACPI_PARSE_OBJECT * 728 TrLinkPeerNode ( 729 ACPI_PARSE_OBJECT *Op1, 730 ACPI_PARSE_OBJECT *Op2) 731 { 732 ACPI_PARSE_OBJECT *Next; 733 734 735 DbgPrint (ASL_PARSE_OUTPUT, 736 "\nLinkPeerNode: 1=%p (%s), 2=%p (%s)\n\n", 737 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode) : NULL, 738 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode) : NULL); 739 740 741 if ((!Op1) && (!Op2)) 742 { 743 DbgPrint (ASL_PARSE_OUTPUT, "\nTwo Null nodes!\n"); 744 return Op1; 745 } 746 747 /* If one of the nodes is null, just return the non-null node */ 748 749 if (!Op2) 750 { 751 return Op1; 752 } 753 754 if (!Op1) 755 { 756 return Op2; 757 } 758 759 if (Op1 == Op2) 760 { 761 DbgPrint (ASL_DEBUG_OUTPUT, 762 "\n\n************* Internal error, linking node to itself %p\n\n\n", 763 Op1); 764 AslError (ASL_WARNING, ASL_MSG_COMPILER_INTERNAL, Op1, 765 "Linking node to itself"); 766 return Op1; 767 } 768 769 Op1->Asl.Parent = Op2->Asl.Parent; 770 771 /* 772 * Op 1 may already have a peer list (such as an IF/ELSE pair), 773 * so we must walk to the end of the list and attach the new 774 * peer at the end 775 */ 776 Next = Op1; 777 while (Next->Asl.Next) 778 { 779 Next = Next->Asl.Next; 780 } 781 782 Next->Asl.Next = Op2; 783 return Op1; 784 } 785 786 787 /******************************************************************************* 788 * 789 * FUNCTION: TrLinkPeerNodes 790 * 791 * PARAMETERS: NumPeers - The number of nodes in the list to follow 792 * ... - A list of nodes to link together as peers 793 * 794 * RETURN: The first node in the list (head of the peer list) 795 * 796 * DESCRIPTION: Link together an arbitrary number of peer nodes. 797 * 798 ******************************************************************************/ 799 800 ACPI_PARSE_OBJECT * 801 TrLinkPeerNodes ( 802 UINT32 NumPeers, 803 ...) 804 { 805 ACPI_PARSE_OBJECT *This; 806 ACPI_PARSE_OBJECT *Next; 807 va_list ap; 808 UINT32 i; 809 ACPI_PARSE_OBJECT *Start; 810 811 812 DbgPrint (ASL_PARSE_OUTPUT, 813 "\nLinkPeerNodes: (%u) ", NumPeers); 814 815 va_start (ap, NumPeers); 816 This = va_arg (ap, ACPI_PARSE_OBJECT *); 817 Start = This; 818 819 /* 820 * Link all peers 821 */ 822 for (i = 0; i < (NumPeers -1); i++) 823 { 824 DbgPrint (ASL_PARSE_OUTPUT, "%u=%p ", (i+1), This); 825 826 while (This->Asl.Next) 827 { 828 This = This->Asl.Next; 829 } 830 831 /* Get another peer node */ 832 833 Next = va_arg (ap, ACPI_PARSE_OBJECT *); 834 if (!Next) 835 { 836 Next = TrAllocateNode (PARSEOP_DEFAULT_ARG); 837 } 838 839 /* link new node to the current node */ 840 841 This->Asl.Next = Next; 842 This = Next; 843 } 844 va_end (ap); 845 846 DbgPrint (ASL_PARSE_OUTPUT,"\n\n"); 847 return (Start); 848 } 849 850 851 /******************************************************************************* 852 * 853 * FUNCTION: TrLinkChildNode 854 * 855 * PARAMETERS: Op1 - Parent node 856 * Op2 - Op to become a child 857 * 858 * RETURN: The parent node 859 * 860 * DESCRIPTION: Link two nodes together as a parent and child 861 * 862 ******************************************************************************/ 863 864 ACPI_PARSE_OBJECT * 865 TrLinkChildNode ( 866 ACPI_PARSE_OBJECT *Op1, 867 ACPI_PARSE_OBJECT *Op2) 868 { 869 ACPI_PARSE_OBJECT *Next; 870 871 872 DbgPrint (ASL_PARSE_OUTPUT, 873 "\nLinkChildNode: Parent=%p (%s), Child=%p (%s)\n\n", 874 Op1, Op1 ? UtGetOpName(Op1->Asl.ParseOpcode): NULL, 875 Op2, Op2 ? UtGetOpName(Op2->Asl.ParseOpcode): NULL); 876 877 if (!Op1 || !Op2) 878 { 879 return Op1; 880 } 881 882 Op1->Asl.Child = Op2; 883 884 /* Set the child and all peers of the child to point to the parent */ 885 886 Next = Op2; 887 while (Next) 888 { 889 Next->Asl.Parent = Op1; 890 Next = Next->Asl.Next; 891 } 892 893 return Op1; 894 } 895 896 897 /******************************************************************************* 898 * 899 * FUNCTION: TrWalkParseTree 900 * 901 * PARAMETERS: Visitation - Type of walk 902 * DescendingCallback - Called during tree descent 903 * AscendingCallback - Called during tree ascent 904 * Context - To be passed to the callbacks 905 * 906 * RETURN: Status from callback(s) 907 * 908 * DESCRIPTION: Walk the entire parse tree. 909 * 910 ******************************************************************************/ 911 912 ACPI_STATUS 913 TrWalkParseTree ( 914 ACPI_PARSE_OBJECT *Op, 915 UINT32 Visitation, 916 ASL_WALK_CALLBACK DescendingCallback, 917 ASL_WALK_CALLBACK AscendingCallback, 918 void *Context) 919 { 920 UINT32 Level; 921 BOOLEAN NodePreviouslyVisited; 922 ACPI_PARSE_OBJECT *StartOp = Op; 923 ACPI_STATUS Status; 924 925 926 if (!RootNode) 927 { 928 return (AE_OK); 929 } 930 931 Level = 0; 932 NodePreviouslyVisited = FALSE; 933 934 switch (Visitation) 935 { 936 case ASL_WALK_VISIT_DOWNWARD: 937 938 while (Op) 939 { 940 if (!NodePreviouslyVisited) 941 { 942 /* Let the callback process the node. */ 943 944 Status = DescendingCallback (Op, Level, Context); 945 if (ACPI_SUCCESS (Status)) 946 { 947 /* Visit children first, once */ 948 949 if (Op->Asl.Child) 950 { 951 Level++; 952 Op = Op->Asl.Child; 953 continue; 954 } 955 } 956 else if (Status != AE_CTRL_DEPTH) 957 { 958 /* Exit immediately on any error */ 959 960 return (Status); 961 } 962 } 963 964 /* Terminate walk at start op */ 965 966 if (Op == StartOp) 967 { 968 break; 969 } 970 971 /* No more children, visit peers */ 972 973 if (Op->Asl.Next) 974 { 975 Op = Op->Asl.Next; 976 NodePreviouslyVisited = FALSE; 977 } 978 else 979 { 980 /* No children or peers, re-visit parent */ 981 982 if (Level != 0 ) 983 { 984 Level--; 985 } 986 Op = Op->Asl.Parent; 987 NodePreviouslyVisited = TRUE; 988 } 989 } 990 break; 991 992 993 case ASL_WALK_VISIT_UPWARD: 994 995 while (Op) 996 { 997 /* Visit leaf node (no children) or parent node on return trip */ 998 999 if ((!Op->Asl.Child) || 1000 (NodePreviouslyVisited)) 1001 { 1002 /* Let the callback process the node. */ 1003 1004 Status = AscendingCallback (Op, Level, Context); 1005 if (ACPI_FAILURE (Status)) 1006 { 1007 return (Status); 1008 } 1009 } 1010 else 1011 { 1012 /* Visit children first, once */ 1013 1014 Level++; 1015 Op = Op->Asl.Child; 1016 continue; 1017 } 1018 1019 /* Terminate walk at start op */ 1020 1021 if (Op == StartOp) 1022 { 1023 break; 1024 } 1025 1026 /* No more children, visit peers */ 1027 1028 if (Op->Asl.Next) 1029 { 1030 Op = Op->Asl.Next; 1031 NodePreviouslyVisited = FALSE; 1032 } 1033 else 1034 { 1035 /* No children or peers, re-visit parent */ 1036 1037 if (Level != 0 ) 1038 { 1039 Level--; 1040 } 1041 Op = Op->Asl.Parent; 1042 NodePreviouslyVisited = TRUE; 1043 } 1044 } 1045 break; 1046 1047 1048 case ASL_WALK_VISIT_TWICE: 1049 1050 while (Op) 1051 { 1052 if (NodePreviouslyVisited) 1053 { 1054 Status = AscendingCallback (Op, Level, Context); 1055 if (ACPI_FAILURE (Status)) 1056 { 1057 return (Status); 1058 } 1059 } 1060 else 1061 { 1062 /* Let the callback process the node. */ 1063 1064 Status = DescendingCallback (Op, Level, Context); 1065 if (ACPI_SUCCESS (Status)) 1066 { 1067 /* Visit children first, once */ 1068 1069 if (Op->Asl.Child) 1070 { 1071 Level++; 1072 Op = Op->Asl.Child; 1073 continue; 1074 } 1075 } 1076 else if (Status != AE_CTRL_DEPTH) 1077 { 1078 /* Exit immediately on any error */ 1079 1080 return (Status); 1081 } 1082 } 1083 1084 /* Terminate walk at start op */ 1085 1086 if (Op == StartOp) 1087 { 1088 break; 1089 } 1090 1091 /* No more children, visit peers */ 1092 1093 if (Op->Asl.Next) 1094 { 1095 Op = Op->Asl.Next; 1096 NodePreviouslyVisited = FALSE; 1097 } 1098 else 1099 { 1100 /* No children or peers, re-visit parent */ 1101 1102 if (Level != 0 ) 1103 { 1104 Level--; 1105 } 1106 Op = Op->Asl.Parent; 1107 NodePreviouslyVisited = TRUE; 1108 } 1109 } 1110 break; 1111 1112 default: 1113 /* No other types supported */ 1114 break; 1115 } 1116 1117 /* If we get here, the walk completed with no errors */ 1118 1119 return (AE_OK); 1120 } 1121 1122 1123