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