1/******************************************************************************
2 *
3 * Module Name: pstree - Parser op tree manipulation/traversal/search
4 *
5 *****************************************************************************/
6
7/*
8 * Copyright (C) 2000 - 2011, Intel Corp.
9 * All rights reserved.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 *    notice, this list of conditions, and the following disclaimer,
16 *    without modification.
17 * 2. Redistributions in binary form must reproduce at minimum a disclaimer
18 *    substantially similar to the "NO WARRANTY" disclaimer below
19 *    ("Disclaimer") and any redistribution must be conditioned upon
20 *    including a substantially similar Disclaimer requirement for further
21 *    binary redistribution.
22 * 3. Neither the names of the above-listed copyright holders nor the names
23 *    of any contributors may be used to endorse or promote products derived
24 *    from this software without specific prior written permission.
25 *
26 * Alternatively, this software may be distributed under the terms of the
27 * GNU General Public License ("GPL") version 2 as published by the Free
28 * Software Foundation.
29 *
30 * NO WARRANTY
31 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
32 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
33 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
34 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
35 * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
36 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
37 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
38 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
40 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
41 * POSSIBILITY OF SUCH DAMAGES.
42 */
43
44
45#define __PSTREE_C__
46
47#include "acpi.h"
48#include "accommon.h"
49#include "acparser.h"
50#include "amlcode.h"
51
52#define _COMPONENT          ACPI_PARSER
53        ACPI_MODULE_NAME    ("pstree")
54
55/* Local prototypes */
56
57#ifdef ACPI_OBSOLETE_FUNCTIONS
58ACPI_PARSE_OBJECT *
59AcpiPsGetChild (
60    ACPI_PARSE_OBJECT       *op);
61#endif
62
63
64/*******************************************************************************
65 *
66 * FUNCTION:    AcpiPsGetArg
67 *
68 * PARAMETERS:  Op              - Get an argument for this op
69 *              Argn            - Nth argument to get
70 *
71 * RETURN:      The argument (as an Op object). NULL if argument does not exist
72 *
73 * DESCRIPTION: Get the specified op's argument.
74 *
75 ******************************************************************************/
76
77ACPI_PARSE_OBJECT *
78AcpiPsGetArg (
79    ACPI_PARSE_OBJECT       *Op,
80    UINT32                  Argn)
81{
82    ACPI_PARSE_OBJECT       *Arg = NULL;
83    const ACPI_OPCODE_INFO  *OpInfo;
84
85
86    ACPI_FUNCTION_ENTRY ();
87
88
89    /* Get the info structure for this opcode */
90
91    OpInfo = AcpiPsGetOpcodeInfo (Op->Common.AmlOpcode);
92    if (OpInfo->Class == AML_CLASS_UNKNOWN)
93    {
94        /* Invalid opcode or ASCII character */
95
96        return (NULL);
97    }
98
99    /* Check if this opcode requires argument sub-objects */
100
101    if (!(OpInfo->Flags & AML_HAS_ARGS))
102    {
103        /* Has no linked argument objects */
104
105        return (NULL);
106    }
107
108    /* Get the requested argument object */
109
110    Arg = Op->Common.Value.Arg;
111    while (Arg && Argn)
112    {
113        Argn--;
114        Arg = Arg->Common.Next;
115    }
116
117    return (Arg);
118}
119
120
121/*******************************************************************************
122 *
123 * FUNCTION:    AcpiPsAppendArg
124 *
125 * PARAMETERS:  Op              - Append an argument to this Op.
126 *              Arg             - Argument Op to append
127 *
128 * RETURN:      None.
129 *
130 * DESCRIPTION: Append an argument to an op's argument list (a NULL arg is OK)
131 *
132 ******************************************************************************/
133
134void
135AcpiPsAppendArg (
136    ACPI_PARSE_OBJECT       *Op,
137    ACPI_PARSE_OBJECT       *Arg)
138{
139    ACPI_PARSE_OBJECT       *PrevArg;
140    const ACPI_OPCODE_INFO  *OpInfo;
141
142
143    ACPI_FUNCTION_ENTRY ();
144
145
146    if (!Op)
147    {
148        return;
149    }
150
151    /* Get the info structure for this opcode */
152
153    OpInfo = AcpiPsGetOpcodeInfo (Op->Common.AmlOpcode);
154    if (OpInfo->Class == AML_CLASS_UNKNOWN)
155    {
156        /* Invalid opcode */
157
158        ACPI_ERROR ((AE_INFO, "Invalid AML Opcode: 0x%2.2X",
159            Op->Common.AmlOpcode));
160        return;
161    }
162
163    /* Check if this opcode requires argument sub-objects */
164
165    if (!(OpInfo->Flags & AML_HAS_ARGS))
166    {
167        /* Has no linked argument objects */
168
169        return;
170    }
171
172    /* Append the argument to the linked argument list */
173
174    if (Op->Common.Value.Arg)
175    {
176        /* Append to existing argument list */
177
178        PrevArg = Op->Common.Value.Arg;
179        while (PrevArg->Common.Next)
180        {
181            PrevArg = PrevArg->Common.Next;
182        }
183        PrevArg->Common.Next = Arg;
184    }
185    else
186    {
187        /* No argument list, this will be the first argument */
188
189        Op->Common.Value.Arg = Arg;
190    }
191
192    /* Set the parent in this arg and any args linked after it */
193
194    while (Arg)
195    {
196        Arg->Common.Parent = Op;
197        Arg = Arg->Common.Next;
198
199        Op->Common.ArgListLength++;
200    }
201}
202
203
204/*******************************************************************************
205 *
206 * FUNCTION:    AcpiPsGetDepthNext
207 *
208 * PARAMETERS:  Origin          - Root of subtree to search
209 *              Op              - Last (previous) Op that was found
210 *
211 * RETURN:      Next Op found in the search.
212 *
213 * DESCRIPTION: Get next op in tree (walking the tree in depth-first order)
214 *              Return NULL when reaching "origin" or when walking up from root
215 *
216 ******************************************************************************/
217
218ACPI_PARSE_OBJECT *
219AcpiPsGetDepthNext (
220    ACPI_PARSE_OBJECT       *Origin,
221    ACPI_PARSE_OBJECT       *Op)
222{
223    ACPI_PARSE_OBJECT       *Next = NULL;
224    ACPI_PARSE_OBJECT       *Parent;
225    ACPI_PARSE_OBJECT       *Arg;
226
227
228    ACPI_FUNCTION_ENTRY ();
229
230
231    if (!Op)
232    {
233        return (NULL);
234    }
235
236    /* Look for an argument or child */
237
238    Next = AcpiPsGetArg (Op, 0);
239    if (Next)
240    {
241        return (Next);
242    }
243
244    /* Look for a sibling */
245
246    Next = Op->Common.Next;
247    if (Next)
248    {
249        return (Next);
250    }
251
252    /* Look for a sibling of parent */
253
254    Parent = Op->Common.Parent;
255
256    while (Parent)
257    {
258        Arg = AcpiPsGetArg (Parent, 0);
259        while (Arg && (Arg != Origin) && (Arg != Op))
260        {
261            Arg = Arg->Common.Next;
262        }
263
264        if (Arg == Origin)
265        {
266            /* Reached parent of origin, end search */
267
268            return (NULL);
269        }
270
271        if (Parent->Common.Next)
272        {
273            /* Found sibling of parent */
274
275            return (Parent->Common.Next);
276        }
277
278        Op = Parent;
279        Parent = Parent->Common.Parent;
280    }
281
282    return (Next);
283}
284
285
286#ifdef ACPI_OBSOLETE_FUNCTIONS
287/*******************************************************************************
288 *
289 * FUNCTION:    AcpiPsGetChild
290 *
291 * PARAMETERS:  Op              - Get the child of this Op
292 *
293 * RETURN:      Child Op, Null if none is found.
294 *
295 * DESCRIPTION: Get op's children or NULL if none
296 *
297 ******************************************************************************/
298
299ACPI_PARSE_OBJECT *
300AcpiPsGetChild (
301    ACPI_PARSE_OBJECT       *Op)
302{
303    ACPI_PARSE_OBJECT       *Child = NULL;
304
305
306    ACPI_FUNCTION_ENTRY ();
307
308
309    switch (Op->Common.AmlOpcode)
310    {
311    case AML_SCOPE_OP:
312    case AML_ELSE_OP:
313    case AML_DEVICE_OP:
314    case AML_THERMAL_ZONE_OP:
315    case AML_INT_METHODCALL_OP:
316
317        Child = AcpiPsGetArg (Op, 0);
318        break;
319
320
321    case AML_BUFFER_OP:
322    case AML_PACKAGE_OP:
323    case AML_METHOD_OP:
324    case AML_IF_OP:
325    case AML_WHILE_OP:
326    case AML_FIELD_OP:
327
328        Child = AcpiPsGetArg (Op, 1);
329        break;
330
331
332    case AML_POWER_RES_OP:
333    case AML_INDEX_FIELD_OP:
334
335        Child = AcpiPsGetArg (Op, 2);
336        break;
337
338
339    case AML_PROCESSOR_OP:
340    case AML_BANK_FIELD_OP:
341
342        Child = AcpiPsGetArg (Op, 3);
343        break;
344
345
346    default:
347        /* All others have no children */
348        break;
349    }
350
351    return (Child);
352}
353#endif
354
355
356