pswalk.c revision 71867 
1/******************************************************************************
2 *
3 * Module Name: pswalk - Parser routines to walk parsed op tree(s)
4 *              $Revision: 52 $
5 *
6 *****************************************************************************/
7
8/******************************************************************************
9 *
10 * 1. Copyright Notice
11 *
12 * Some or all of this work - Copyright (c) 1999, 2000, 2001, Intel Corp.
13 * All rights reserved.
14 *
15 * 2. License
16 *
17 * 2.1. This is your license from Intel Corp. under its intellectual property
18 * rights.  You may have additional license terms from the party that provided
19 * you this software, covering your right to use that party's intellectual
20 * property rights.
21 *
22 * 2.2. Intel grants, free of charge, to any person ("Licensee") obtaining a
23 * copy of the source code appearing in this file ("Covered Code") an
24 * irrevocable, perpetual, worldwide license under Intel's copyrights in the
25 * base code distributed originally by Intel ("Original Intel Code") to copy,
26 * make derivatives, distribute, use and display any portion of the Covered
27 * Code in any form, with the right to sublicense such rights; and
28 *
29 * 2.3. Intel grants Licensee a non-exclusive and non-transferable patent
30 * license (with the right to sublicense), under only those claims of Intel
31 * patents that are infringed by the Original Intel Code, to make, use, sell,
32 * offer to sell, and import the Covered Code and derivative works thereof
33 * solely to the minimum extent necessary to exercise the above copyright
34 * license, and in no event shall the patent license extend to any additions
35 * to or modifications of the Original Intel Code.  No other license or right
36 * is granted directly or by implication, estoppel or otherwise;
37 *
38 * The above copyright and patent license is granted only if the following
39 * conditions are met:
40 *
41 * 3. Conditions
42 *
43 * 3.1. Redistribution of Source with Rights to Further Distribute Source.
44 * Redistribution of source code of any substantial portion of the Covered
45 * Code or modification with rights to further distribute source must include
46 * the above Copyright Notice, the above License, this list of Conditions,
47 * and the following Disclaimer and Export Compliance provision.  In addition,
48 * Licensee must cause all Covered Code to which Licensee contributes to
49 * contain a file documenting the changes Licensee made to create that Covered
50 * Code and the date of any change.  Licensee must include in that file the
51 * documentation of any changes made by any predecessor Licensee.  Licensee
52 * must include a prominent statement that the modification is derived,
53 * directly or indirectly, from Original Intel Code.
54 *
55 * 3.2. Redistribution of Source with no Rights to Further Distribute Source.
56 * Redistribution of source code of any substantial portion of the Covered
57 * Code or modification without rights to further distribute source must
58 * include the following Disclaimer and Export Compliance provision in the
59 * documentation and/or other materials provided with distribution.  In
60 * addition, Licensee may not authorize further sublicense of source of any
61 * portion of the Covered Code, and must include terms to the effect that the
62 * license from Licensee to its licensee is limited to the intellectual
63 * property embodied in the software Licensee provides to its licensee, and
64 * not to intellectual property embodied in modifications its licensee may
65 * make.
66 *
67 * 3.3. Redistribution of Executable. Redistribution in executable form of any
68 * substantial portion of the Covered Code or modification must reproduce the
69 * above Copyright Notice, and the following Disclaimer and Export Compliance
70 * provision in the documentation and/or other materials provided with the
71 * distribution.
72 *
73 * 3.4. Intel retains all right, title, and interest in and to the Original
74 * Intel Code.
75 *
76 * 3.5. Neither the name Intel nor any other trademark owned or controlled by
77 * Intel shall be used in advertising or otherwise to promote the sale, use or
78 * other dealings in products derived from or relating to the Covered Code
79 * without prior written authorization from Intel.
80 *
81 * 4. Disclaimer and Export Compliance
82 *
83 * 4.1. INTEL MAKES NO WARRANTY OF ANY KIND REGARDING ANY SOFTWARE PROVIDED
84 * HERE.  ANY SOFTWARE ORIGINATING FROM INTEL OR DERIVED FROM INTEL SOFTWARE
85 * IS PROVIDED "AS IS," AND INTEL WILL NOT PROVIDE ANY SUPPORT,  ASSISTANCE,
86 * INSTALLATION, TRAINING OR OTHER SERVICES.  INTEL WILL NOT PROVIDE ANY
87 * UPDATES, ENHANCEMENTS OR EXTENSIONS.  INTEL SPECIFICALLY DISCLAIMS ANY
88 * IMPLIED WARRANTIES OF MERCHANTABILITY, NONINFRINGEMENT AND FITNESS FOR A
89 * PARTICULAR PURPOSE.
90 *
91 * 4.2. IN NO EVENT SHALL INTEL HAVE ANY LIABILITY TO LICENSEE, ITS LICENSEES
92 * OR ANY OTHER THIRD PARTY, FOR ANY LOST PROFITS, LOST DATA, LOSS OF USE OR
93 * COSTS OF PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES, OR FOR ANY INDIRECT,
94 * SPECIAL OR CONSEQUENTIAL DAMAGES ARISING OUT OF THIS AGREEMENT, UNDER ANY
95 * CAUSE OF ACTION OR THEORY OF LIABILITY, AND IRRESPECTIVE OF WHETHER INTEL
96 * HAS ADVANCE NOTICE OF THE POSSIBILITY OF SUCH DAMAGES.  THESE LIMITATIONS
97 * SHALL APPLY NOTWITHSTANDING THE FAILURE OF THE ESSENTIAL PURPOSE OF ANY
98 * LIMITED REMEDY.
99 *
100 * 4.3. Licensee shall not export, either directly or indirectly, any of this
101 * software or system incorporating such software without first obtaining any
102 * required license or other approval from the U. S. Department of Commerce or
103 * any other agency or department of the United States Government.  In the
104 * event Licensee exports any such software from the United States or
105 * re-exports any such software from a foreign destination, Licensee shall
106 * ensure that the distribution and export/re-export of the software is in
107 * compliance with all laws, regulations, orders, or other restrictions of the
108 * U.S. Export Administration Regulations. Licensee agrees that neither it nor
109 * any of its subsidiaries will export/re-export any technical data, process,
110 * software, or service, directly or indirectly, to any country for which the
111 * United States government or any agency thereof requires an export license,
112 * other governmental approval, or letter of assurance, without first obtaining
113 * such license, approval or letter.
114 *
115 *****************************************************************************/
116
117
118#include "acpi.h"
119#include "amlcode.h"
120#include "acparser.h"
121#include "acdispat.h"
122#include "acnamesp.h"
123#include "acinterp.h"
124
125#define _COMPONENT          PARSER
126        MODULE_NAME         ("pswalk")
127
128
129/*******************************************************************************
130 *
131 * FUNCTION:    AcpiPsGetNextWalkOp
132 *
133 * PARAMETERS:  WalkState           - Current state of the walk
134 *              Op                  - Current Op to be walked
135 *              AscendingCallback   - Procedure called when Op is complete
136 *
137 * RETURN:      Status
138 *
139 * DESCRIPTION: Get the next Op in a walk of the parse tree.
140 *
141 ******************************************************************************/
142
143ACPI_STATUS
144AcpiPsGetNextWalkOp (
145    ACPI_WALK_STATE         *WalkState,
146    ACPI_PARSE_OBJECT       *Op,
147    ACPI_PARSE_UPWARDS      AscendingCallback)
148{
149    ACPI_PARSE_OBJECT       *Next;
150    ACPI_PARSE_OBJECT       *Parent;
151    ACPI_PARSE_OBJECT       *GrandParent;
152    ACPI_STATUS             Status;
153
154
155    FUNCTION_TRACE_PTR ("PsGetNextWalkOp", Op);
156
157
158    /* Check for a argument only if we are descending in the tree */
159
160    if (WalkState->NextOpInfo != NEXT_OP_UPWARD)
161    {
162        /* Look for an argument or child of the current op */
163
164        Next = AcpiPsGetArg (Op, 0);
165        if (Next)
166        {
167            /* Still going downward in tree (Op is not completed yet) */
168
169            WalkState->PrevOp       = Op;
170            WalkState->NextOp       = Next;
171            WalkState->NextOpInfo   = NEXT_OP_DOWNWARD;
172
173            return_ACPI_STATUS (AE_OK);
174        }
175
176
177        /*
178         * No more children, this Op is complete.  Save Next and Parent
179         * in case the Op object gets deleted by the callback routine
180         */
181
182        Next    = Op->Next;
183        Parent  = Op->Parent;
184
185        Status = AscendingCallback (WalkState, Op);
186
187        /*
188         * If we are back to the starting point, the walk is complete.
189         */
190        if (Op == WalkState->Origin)
191        {
192            /* Reached the point of origin, the walk is complete */
193
194            WalkState->PrevOp       = Op;
195            WalkState->NextOp       = NULL;
196
197            return_ACPI_STATUS (Status);
198        }
199
200        /*
201         * Check for a sibling to the current op.  A sibling means
202         * we are still going "downward" in the tree.
203         */
204
205        if (Next)
206        {
207            /* There is a sibling, it will be next */
208
209            WalkState->PrevOp       = Op;
210            WalkState->NextOp       = Next;
211            WalkState->NextOpInfo   = NEXT_OP_DOWNWARD;
212
213            /* Continue downward */
214
215            return_ACPI_STATUS (Status);
216        }
217
218
219        /*
220         * Drop into the loop below because we are moving upwards in
221         * the tree
222         */
223    }
224
225    else
226    {
227        /*
228         * We are resuming a walk, and we were (are) going upward in the tree.
229         * So, we want to drop into the parent loop below.
230         */
231
232        Parent = Op;
233    }
234
235
236    /*
237     * Look for a sibling of the current Op's parent
238     * Continue moving up the tree until we find a node that has not been
239     * visited, or we get back to where we started.
240     */
241    while (Parent)
242    {
243        /* We are moving up the tree, therefore this parent Op is complete */
244
245        GrandParent = Parent->Parent;
246        Next        = Parent->Next;
247
248        Status = AscendingCallback (WalkState, Parent);
249
250        /*
251         * If we are back to the starting point, the walk is complete.
252         */
253        if (Parent == WalkState->Origin)
254        {
255            /* Reached the point of origin, the walk is complete */
256
257            WalkState->PrevOp       = Parent;
258            WalkState->NextOp       = NULL;
259
260            return_ACPI_STATUS (Status);
261        }
262
263        /*
264         * If there is a sibling to this parent (it is not the starting point
265         * Op), then we will visit it.
266         */
267        if (Next)
268        {
269            /* found sibling of parent */
270
271            WalkState->PrevOp       = Parent;
272            WalkState->NextOp       = Next;
273            WalkState->NextOpInfo   = NEXT_OP_DOWNWARD;
274
275            return_ACPI_STATUS (Status);
276        }
277
278        /* No siblings, no errors, just move up one more level in the tree */
279
280        Op                  = Parent;
281        Parent              = GrandParent;
282        WalkState->PrevOp   = Op;
283    }
284
285
286    /* Got all the way to the top of the tree, we must be done! */
287    /* However, the code should have terminated in the loop above */
288
289    WalkState->NextOp       = NULL;
290
291    return_ACPI_STATUS (AE_OK);
292}
293
294
295/*******************************************************************************
296 *
297 * FUNCTION:    AcpiPsDeleteCompletedOp
298 *
299 * PARAMETERS:  State           - Walk state
300 *              Op              - Completed op
301 *
302 * RETURN:      AE_OK
303 *
304 * DESCRIPTION: Callback function for AcpiPsGetNextWalkOp().  Used during
305 *              AcpiPsDeleteParse tree to delete Op objects when all sub-objects
306 *              have been visited (and deleted.)
307 *
308 ******************************************************************************/
309
310static ACPI_STATUS
311AcpiPsDeleteCompletedOp (
312    ACPI_WALK_STATE         *State,
313    ACPI_PARSE_OBJECT       *Op)
314{
315
316    AcpiPsFreeOp (Op);
317    return (AE_OK);
318}
319
320
321/*******************************************************************************
322 *
323 * FUNCTION:    AcpiPsDeleteParseTree
324 *
325 * PARAMETERS:  SubtreeRoot         - Root of tree (or subtree) to delete
326 *
327 * RETURN:      None
328 *
329 * DESCRIPTION: Delete a portion of or an entire parse tree.
330 *
331 ******************************************************************************/
332
333void
334AcpiPsDeleteParseTree (
335    ACPI_PARSE_OBJECT       *SubtreeRoot)
336{
337    ACPI_WALK_STATE         *WalkState;
338    ACPI_WALK_LIST          WalkList;
339
340
341    FUNCTION_TRACE_PTR ("PsDeleteParseTree", SubtreeRoot);
342
343
344    if (!SubtreeRoot)
345    {
346        return_VOID;
347    }
348
349    /* Create and initialize a new walk list */
350
351    WalkList.WalkState = NULL;
352    WalkState = AcpiDsCreateWalkState (TABLE_ID_DSDT, NULL, NULL, &WalkList);
353    if (!WalkState)
354    {
355        return_VOID;
356    }
357
358    WalkState->ParserState          = NULL;
359    WalkState->ParseFlags           = 0;
360    WalkState->DescendingCallback   = NULL;
361    WalkState->AscendingCallback    = NULL;
362
363
364    WalkState->Origin = SubtreeRoot;
365    WalkState->NextOp = SubtreeRoot;
366
367
368    /* Head downward in the tree */
369
370    WalkState->NextOpInfo = NEXT_OP_DOWNWARD;
371
372    /* Visit all nodes in the subtree */
373
374    while (WalkState->NextOp)
375    {
376        AcpiPsGetNextWalkOp (WalkState, WalkState->NextOp,
377                                AcpiPsDeleteCompletedOp);
378    }
379
380    /* We are done with this walk */
381
382    AcpiDsDeleteWalkState (WalkState);
383
384    return_VOID;
385}
386
387
388