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
54static ACPI_PARSE_OBJECT *
55TrGetNextNode (
56 void);
57
58static char *
59TrGetNodeFlagName (
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
77static ACPI_PARSE_OBJECT *
78TrGetNextNode (
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
105ACPI_PARSE_OBJECT *
106TrAllocateNode (
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
139void
140TrReleaseNode (
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
164ACPI_PARSE_OBJECT *
165TrUpdateNode (
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
246static char *
247TrGetNodeFlagName (
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
323ACPI_PARSE_OBJECT *
324TrSetNodeFlags (
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
357void
358TrSetEndLineNumber (
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
387ACPI_PARSE_OBJECT *
388TrCreateLeafNode (
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
418ACPI_PARSE_OBJECT *
419TrCreateValuedLeafNode (
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
485ACPI_PARSE_OBJECT *
486TrCreateNode (
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
606ACPI_PARSE_OBJECT *
607TrLinkChildren (
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
727ACPI_PARSE_OBJECT *
728TrLinkPeerNode (
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
800ACPI_PARSE_OBJECT *
801TrLinkPeerNodes (
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
864ACPI_PARSE_OBJECT *
865TrLinkChildNode (
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
912ACPI_STATUS
913TrWalkParseTree (
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