From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from EUR04-VI1-obe.outbound.protection.outlook.com (EUR04-VI1-obe.outbound.protection.outlook.com [40.107.8.57]) by mx.groups.io with SMTP id smtpd.web10.17193.1597245808012342500 for ; Wed, 12 Aug 2020 08:23:28 -0700 Authentication-Results: mx.groups.io; dkim=pass header.i=@armh.onmicrosoft.com header.s=selector2-armh-onmicrosoft-com header.b=eV6ydz+6; spf=pass (domain: arm.com, ip: 40.107.8.57, mailfrom: sami.mujawar@arm.com) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=KDMkVFrjHfPT9uT53KbDc8FJ4HDcEz/dDynnkrf3wKg=; b=eV6ydz+6AFh4ZsWsq8J46RH0uJ15ZGISOkeuQd7VnA77EmQo0X2qMD09+/ie3HqvPWzZUqA8ctTFrv7rCFnYQSFzWMTr+UPHJPoXQc+FMH+oxzIEE2zH7G25Jft90/HPFlnNo884UQXtPUinSQW76teQL/9iVEwp6mSSdShBkgQ= Received: from AM5PR04CA0006.eurprd04.prod.outlook.com (2603:10a6:206:1::19) by VI1PR0802MB2287.eurprd08.prod.outlook.com (2603:10a6:800:9d::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3261.20; Wed, 12 Aug 2020 15:23:24 +0000 Received: from AM5EUR03FT022.eop-EUR03.prod.protection.outlook.com (2603:10a6:206:1:cafe::65) by AM5PR04CA0006.outlook.office365.com (2603:10a6:206:1::19) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3283.16 via Frontend Transport; Wed, 12 Aug 2020 15:23:22 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 63.35.35.123) smtp.mailfrom=arm.com; edk2.groups.io; dkim=pass (signature was verified) header.d=armh.onmicrosoft.com;edk2.groups.io; dmarc=bestguesspass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 63.35.35.123 as permitted sender) receiver=protection.outlook.com; client-ip=63.35.35.123; helo=64aa7808-outbound-1.mta.getcheckrecipient.com; Received: from 64aa7808-outbound-1.mta.getcheckrecipient.com (63.35.35.123) by AM5EUR03FT022.mail.protection.outlook.com (10.152.16.79) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3283.16 via Frontend Transport; Wed, 12 Aug 2020 15:23:22 +0000 Received: ("Tessian outbound 7161e0c2a082:v64"); Wed, 12 Aug 2020 15:23:22 +0000 X-CheckRecipientChecked: true X-CR-MTA-CID: 1ceccb5135ecf61b X-CR-MTA-TID: 64aa7808 Received: from 3af65b739352.1 by 64aa7808-outbound-1.mta.getcheckrecipient.com id 210573BB-F326-49CF-9B74-033508B8DE82.1; Wed, 12 Aug 2020 15:23:16 +0000 Received: from EUR04-VI1-obe.outbound.protection.outlook.com by 64aa7808-outbound-1.mta.getcheckrecipient.com with ESMTPS id 3af65b739352.1 (version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384); Wed, 12 Aug 2020 15:23:16 +0000 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=NJZkfADO2TxBTZTa82TJQU09kOXbGubdKQLcOD08AuknQVpKlf+rx0LK3ZPiX3m+StJLyDKvbQKRDnmDiJISDXovsu6py6gAzuj1Je4L1l9FzudEoI0fMqgY0Y2td0kolnCAhGSg1KEpacVC518RO+GmU9vgDV0OhhbMVSjmmm3RAJ8z9IRfV3fz1xZaDdDUXuvVFEGCgcOqCbxR1rUhc8veN2k9I1+ExY3hPx4gpyjGnoEPLNE9Qo5h1OaKQN9qqUNy8fi419pE0GiJSPSbAXnA5VCT8AA6jmI2qewIOPMoXs0ivCRPjgpmPhTLK0WOdEsf24BSZe/ykvR8A4Zt6g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=KDMkVFrjHfPT9uT53KbDc8FJ4HDcEz/dDynnkrf3wKg=; b=fnVLGHF/a7aEEefcCw1k/fHmvAHsjSFIWt2nMLeJov3jYJ0l2xC74prpAkasnVopR5TWzdWdXRznCq8rjKEVmrmxxIudykZE/fqKMEGfzPYntSAPAUVFyWM7UrHeN0JiXSYjUpVzjzcEiesGPe0puAN5nnCevk4KjFSJp1zNO69AgMSf1Ewrq+NgKGB45cg5j3oJnbsituTxtoxkkpRJsFBR1z3eb0dMUgpTyuWQBSsqMiz1XxSlraORcH4zWKt5CYz97qKlM8CpjAj2un+THWDg9CbDX1aeQOh/SGta1H1pjG2kAufsManKksWF+DKXx63RLRb4CIB2iYWmHe2fhQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass (sender ip is 40.67.248.234) smtp.rcpttodomain=edk2.groups.io smtp.mailfrom=arm.com; dmarc=bestguesspass action=none header.from=arm.com; dkim=none (message not signed); arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector2-armh-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=KDMkVFrjHfPT9uT53KbDc8FJ4HDcEz/dDynnkrf3wKg=; b=eV6ydz+6AFh4ZsWsq8J46RH0uJ15ZGISOkeuQd7VnA77EmQo0X2qMD09+/ie3HqvPWzZUqA8ctTFrv7rCFnYQSFzWMTr+UPHJPoXQc+FMH+oxzIEE2zH7G25Jft90/HPFlnNo884UQXtPUinSQW76teQL/9iVEwp6mSSdShBkgQ= Received: from DB8PR06CA0027.eurprd06.prod.outlook.com (2603:10a6:10:100::40) by VI1PR08MB3456.eurprd08.prod.outlook.com (2603:10a6:803:7e::25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3261.22; Wed, 12 Aug 2020 15:23:14 +0000 Received: from DB5EUR03FT035.eop-EUR03.prod.protection.outlook.com (2603:10a6:10:100:cafe::21) by DB8PR06CA0027.outlook.office365.com (2603:10a6:10:100::40) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3283.15 via Frontend Transport; Wed, 12 Aug 2020 15:23:14 +0000 X-MS-Exchange-Authentication-Results: spf=pass (sender IP is 40.67.248.234) smtp.mailfrom=arm.com; edk2.groups.io; dkim=none (message not signed) header.d=none;edk2.groups.io; dmarc=bestguesspass action=none header.from=arm.com; Received-SPF: Pass (protection.outlook.com: domain of arm.com designates 40.67.248.234 as permitted sender) receiver=protection.outlook.com; client-ip=40.67.248.234; helo=nebula.arm.com; Received: from nebula.arm.com (40.67.248.234) by DB5EUR03FT035.mail.protection.outlook.com (10.152.20.65) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.20.3283.16 via Frontend Transport; Wed, 12 Aug 2020 15:23:14 +0000 Received: from AZ-NEU-EX01.Emea.Arm.com (10.251.26.4) by AZ-NEU-EX04.Arm.com (10.251.24.32) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256) id 15.1.2044.4; Wed, 12 Aug 2020 15:23:11 +0000 Received: from AZ-NEU-EX04.Arm.com (10.251.24.32) by AZ-NEU-EX01.Emea.Arm.com (10.251.26.4) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1779.2; Wed, 12 Aug 2020 15:23:06 +0000 Received: from E107187.Arm.com (10.57.41.222) by mail.arm.com (10.251.24.32) with Microsoft SMTP Server id 15.1.2044.4 via Frontend Transport; Wed, 12 Aug 2020 15:23:06 +0000 From: "Sami Mujawar" To: CC: Sami Mujawar , , , , , , Subject: [PATCH v1 07/30] DynamicTablesPkg: AML tree traversal Date: Wed, 12 Aug 2020 16:22:13 +0100 Message-ID: <20200812152236.31164-8-sami.mujawar@arm.com> X-Mailer: git-send-email 2.11.0.windows.3 In-Reply-To: <20200812152236.31164-1-sami.mujawar@arm.com> References: <20200812152236.31164-1-sami.mujawar@arm.com> MIME-Version: 1.0 X-EOPAttributedMessage: 1 X-MS-Office365-Filtering-HT: Tenant X-MS-PublicTrafficType: Email X-MS-Office365-Filtering-Correlation-Id: 329c66c0-367e-4dcc-978c-08d83ed3a64f X-MS-TrafficTypeDiagnostic: VI1PR08MB3456:|VI1PR0802MB2287: X-Microsoft-Antispam-PRVS: x-checkrecipientrouted: true NoDisclaimer: true X-MS-Oob-TLC-OOBClassifiers: OLM:5236;OLM:5236; X-MS-Exchange-SenderADCheck: 1 X-Microsoft-Antispam-Untrusted: BCL:0; X-Microsoft-Antispam-Message-Info-Original: A1cNZU6VzjvDpdyaJbJS+TcaKIKxdcCW64q92I9r+j/fq/SCI6aSU0MpNE1/iFlKgJosIC0WM+0WRHrTSGry+W8jEvqv+MBCo8uhZAqKnGAkFVnoVTxM+ehyPvxllTqhf/kfhv7Wkxw4L/Uv43XYzkG1h6fXc3QZTl4fcb0n/iZ3dUmEo2QNwBmhkBue8WpyxiNgBqTcntfK26sFq0V05KkY3admejzlvTIMESfj+wJv073vVkV70OO8dQTvmK0yFgnkep+oofwJHq/o0SBu2Zitbd6f33/b7gtME0rmcJlRUvwS2eEQcsCNM7aHWm1ssWnjQyYsC4R8BR5ksNDowD5IMfC8ywPpcGm89qjeurgwpbmFfiXlcfTnucM+m7T5/l5zZu3Uwsm8i9wOROBk4w== X-Forefront-Antispam-Report-Untrusted: CIP:40.67.248.234;CTRY:IE;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:nebula.arm.com;PTR:InfoDomainNonexistent;CAT:NONE;SFTY:;SFS:(4636009)(396003)(39860400002)(346002)(376002)(136003)(46966005)(5660300002)(7696005)(426003)(478600001)(86362001)(44832011)(47076004)(36756003)(70586007)(1076003)(70206006)(54906003)(186003)(336012)(316002)(6666004)(26005)(19627235002)(2906002)(83380400001)(82310400002)(356005)(30864003)(6916009)(8936002)(2616005)(8676002)(4326008)(82740400003)(81166007);DIR:OUT;SFP:1101; X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR08MB3456 Return-Path: Sami.Mujawar@arm.com X-MS-Exchange-Transport-CrossTenantHeadersStripped: AM5EUR03FT022.eop-EUR03.prod.protection.outlook.com X-MS-Office365-Filtering-Correlation-Id-Prvs: d26f1a7c-f247-4b24-4177-08d83ed3a1bb X-Microsoft-Antispam: BCL:0; X-Microsoft-Antispam-Message-Info: 9LnwAvFbclY6vTQJV2NI/CU+Kx5wUPVuwpj/DXI00676lpVTb5/LhLJXOk5XVOGoieAEheLqamRcmdZQIEczhFz4PIHeXgZ7zIS0YgzqthnKxpB/pXVShkEYbGfW2rCOfAXoCbD1tJi9z+hwhtgsed0Fiur7P1p0odWUFVp10gOdH4r2Ot8Rbl9SHEPDnNCwrjFLKCam19uT+IsMNMKtaCIZ+trCHQTCJRkumM9fa8BNOkT+xIlKkpH8diW7KsPPh7CQkBlVMrsLUwWikdHw6OLAvPYSqq5TR87EFCnxUx2Bhh+dh2T5eAk3ErHvJ3Tb3KzUoQQYVERyxSuQNnt1F8CJIzZ7YRJJsdAp15mPwW947yz7i/gXiPyXDeuu4zOgDVwYutUy2Z7qXcof2tKdQw== X-Forefront-Antispam-Report: CIP:63.35.35.123;CTRY:IE;LANG:en;SCL:1;SRV:;IPV:CAL;SFV:NSPM;H:64aa7808-outbound-1.mta.getcheckrecipient.com;PTR:ec2-63-35-35-123.eu-west-1.compute.amazonaws.com;CAT:NONE;SFTY:;SFS:(4636009)(396003)(39860400002)(346002)(376002)(136003)(46966005)(186003)(30864003)(83380400001)(2616005)(1076003)(26005)(8936002)(4326008)(19627235002)(5660300002)(81166007)(2906002)(36756003)(316002)(6666004)(70206006)(54906003)(478600001)(36906005)(86362001)(7696005)(82740400003)(426003)(8676002)(47076004)(6916009)(336012)(44832011)(82310400002)(70586007);DIR:OUT;SFP:1101; X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-OriginalArrivalTime: 12 Aug 2020 15:23:22.1401 (UTC) X-MS-Exchange-CrossTenant-Network-Message-Id: 329c66c0-367e-4dcc-978c-08d83ed3a64f X-MS-Exchange-CrossTenant-Id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-CrossTenant-OriginalAttributedTenantConnectingIp: TenantId=f34e5979-57d9-4aaa-ad4d-b122a662184d;Ip=[63.35.35.123];Helo=[64aa7808-outbound-1.mta.getcheckrecipient.com] X-MS-Exchange-CrossTenant-AuthSource: AM5EUR03FT022.eop-EUR03.prod.protection.outlook.com X-MS-Exchange-CrossTenant-AuthAs: Anonymous X-MS-Exchange-CrossTenant-FromEntityHeader: HybridOnPrem X-MS-Exchange-Transport-CrossTenantHeadersStamped: VI1PR0802MB2287 Content-Type: text/plain From: Pierre Gondois The AML tree traversal provides interfaces to traverse the nodes in the AML tree. It provides interfaces to traverse the AML tree in the following order: - Traverse sibling nodes. (Node) /-i # Child of fixed argument b \ / |- [a][b][c][d] # Fixed Arguments |- {(e)->(f)->(g)} # Variable Arguments \ \-h # Child of variable argument e Traversal Order: - AmlGetNextSibling() : a, b, c, d, e, f, g, NULL - AmlGetPreviousSibling(): g, f, e, d, c, b, a, NULL - Iterate depth-first path (follow AML byte stream). (Node) /-i # Child of fixed argument b \ / |- [a][b][c][d] # Fixed Arguments |- {(e)->(f)->(g)} # Variable Arguments \ \-h # Child of variable argument e Traversal Order: - AmlGetNextNode(): a, b, i, c, d, e, h, f, g, NULL - AmlGetPreviousNode() g, f, h, e, d, c, i, b, a, NULL Note: The branch i and h will be traversed if it has any children. Signed-off-by: Pierre Gondois Signed-off-by: Sami Mujawar --- DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeTraversal.c | 548 ++++++++++++++++++++ DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeTraversal.h | 138 +++++ 2 files changed, 686 insertions(+) diff --git a/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeTraversal.c b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeTraversal.c new file mode 100644 index 0000000000000000000000000000000000000000..9d0c794dbe773061233a4f88e18cb55431bfbf4c --- /dev/null +++ b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeTraversal.c @@ -0,0 +1,548 @@ +/** @file + AML Tree Traversal. + + Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.
+ + SPDX-License-Identifier: BSD-2-Clause-Patent +**/ + +#include + +#include +#include + +/** Get the sibling node among the nodes being in + the same variable argument list. + + (ParentNode) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(VarArgNode)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Node must be in a variable list of arguments. + Traversal Order: VarArgNode, f, g, NULL + + @ingroup CoreNavigationApis + + @param [in] VarArgNode Pointer to a node. + Must be in a variable list of arguments. + + @return The next node after VarArgNode in the variable list of arguments. + Return NULL if + - VarArgNode is the last node of the list, or + - VarArgNode is not part of a variable list of arguments. +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetSiblingVariableArgument ( + IN AML_NODE_HEADER * VarArgNode + ) +{ + EAML_PARSE_INDEX Index; + AML_NODE_HEADER * ParentNode; + + // VarArgNode must be an object node or a data node, + // and be in a variable list of arguments. + if ((!IS_AML_OBJECT_NODE (VarArgNode) && + !IS_AML_DATA_NODE (VarArgNode)) || + AmlIsNodeFixedArgument (VarArgNode, &Index)) { + ASSERT (0); + return NULL; + } + + ParentNode = AmlGetParent (VarArgNode); + if (!IS_AML_NODE_VALID (ParentNode)) { + ASSERT (0); + return NULL; + } + + return AmlGetNextVariableArgument (ParentNode, VarArgNode); +} + +/** Get the next variable argument. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: e, f, g, NULL + + @param [in] Node Pointer to a Root node or Object Node. + @param [in] CurrVarArg Pointer to the Current Variable Argument. + + @return The node after the CurrVarArg in the variable list of arguments. + If CurrVarArg is NULL, return the first node of the + variable argument list. + Return NULL if + - CurrVarArg is the last node of the list, or + - Node does not have a variable list of arguments. +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetNextVariableArgument ( + IN AML_NODE_HEADER * Node, + IN AML_NODE_HEADER * CurrVarArg + ) +{ + CONST LIST_ENTRY * StartLink; + CONST LIST_ENTRY * NextLink; + + // Node must be a RootNode or an Object Node + // and the CurrVarArg must not be a Root Node. + if ((!IS_AML_ROOT_NODE (Node) && + !IS_AML_OBJECT_NODE (Node)) || + ((CurrVarArg != NULL) && + (!IS_AML_OBJECT_NODE (CurrVarArg) && + !IS_AML_DATA_NODE (CurrVarArg)))) { + ASSERT (0); + return NULL; + } + + StartLink = AmlNodeGetVariableArgList (Node); + if (StartLink == NULL) { + return NULL; + } + + // Get the first child of the variable list of arguments. + if (CurrVarArg == NULL) { + NextLink = StartLink->ForwardLink; + if (NextLink != StartLink) { + return (AML_NODE_HEADER*)NextLink; + } + // List is empty. + return NULL; + } + + // Check if CurrVarArg is in the VariableArgument List. + if (!IsNodeInList (StartLink, &CurrVarArg->Link)) { + ASSERT (0); + return NULL; + } + + // Get the node following the CurrVarArg. + NextLink = CurrVarArg->Link.ForwardLink; + if (NextLink != StartLink) { + return (AML_NODE_HEADER*)NextLink; + } + + // End of the list has been reached. + return NULL; +} + +/** Get the previous variable argument. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: g, f, e, NULL + + @param [in] Node Pointer to a root node or an object node. + @param [in] CurrVarArg Pointer to the Current Variable Argument. + + @return The node before the CurrVarArg in the variable list of + arguments. + If CurrVarArg is NULL, return the last node of the + variable list of arguments. + Return NULL if: + - CurrVarArg is the first node of the list, or + - Node doesn't have a variable list of arguments. +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetPreviousVariableArgument ( + IN AML_NODE_HEADER * Node, + IN AML_NODE_HEADER * CurrVarArg + ) +{ + CONST LIST_ENTRY * StartLink; + CONST LIST_ENTRY * PreviousLink; + + // Node must be a RootNode or an Object Node + // and the CurrVarArg must not be a Root Node. + if ((!IS_AML_ROOT_NODE (Node) && + !IS_AML_OBJECT_NODE (Node)) || + ((CurrVarArg != NULL) && + (!IS_AML_OBJECT_NODE (CurrVarArg) && + !IS_AML_DATA_NODE (CurrVarArg)))) { + ASSERT (0); + return NULL; + } + + StartLink = AmlNodeGetVariableArgList (Node); + if (StartLink == NULL) { + return NULL; + } + + // Get the last child of the variable list of arguments. + if (CurrVarArg == NULL) { + PreviousLink = StartLink->BackLink; + if (PreviousLink != StartLink) { + return (AML_NODE_HEADER*)PreviousLink; + } + // List is empty. + return NULL; + } + + // Check if CurrVarArg is in the VariableArgument List. + if (!IsNodeInList (StartLink, &CurrVarArg->Link)) { + ASSERT (0); + return NULL; + } + + // Get the node before the CurrVarArg. + PreviousLink = CurrVarArg->Link.BackLink; + if (PreviousLink != StartLink) { + return (AML_NODE_HEADER*)PreviousLink; + } + + // We have reached the beginning of the list. + return NULL; +} + +/** Get the next sibling node among the children of the input Node. + + This function traverses the FixedArguments followed by the + VariableArguments at the same level in the hierarchy. + + Fixed arguments are before variable arguments. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: a, b, c, d, e, f, g, NULL + + + @param [in] Node Pointer to a root node or an object node. + @param [in] ChildNode Get the node after the ChildNode. + + @return The node after the ChildNode among the children of the input Node. + - If ChildNode is NULL, return the first available node among + the fixed argument list then variable list of arguments; + - If ChildNode is the last node of the fixed argument list, + return the first argument of the variable list of arguments; + - If ChildNode is the last node of the variable list of arguments, + return NULL. + +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetNextSibling ( + IN CONST AML_NODE_HEADER * Node, + IN CONST AML_NODE_HEADER * ChildNode + ) +{ + EAML_PARSE_INDEX Index; + AML_NODE_HEADER * CandidateNode; + + // Node must be a RootNode or an Object Node + // and the CurrVarArg must not be a Root Node. + if ((!IS_AML_ROOT_NODE (Node) && + !IS_AML_OBJECT_NODE (Node)) || + ((ChildNode != NULL) && + (!IS_AML_OBJECT_NODE (ChildNode) && + !IS_AML_DATA_NODE (ChildNode)))) { + ASSERT (0); + return NULL; + } + + if (IS_AML_OBJECT_NODE (Node)) { + if (ChildNode == NULL) { + // Get the fixed argument at index 0 of the ChildNode. + CandidateNode = AmlGetFixedArgument ( + (AML_OBJECT_NODE*)Node, + EAmlParseIndexTerm0 + ); + if (CandidateNode != NULL) { + return CandidateNode; + } + } else { + // (ChildNode != NULL) + if (AmlIsNodeFixedArgument (ChildNode, &Index)) { + // Increment index to point to the next fixed argument. + Index++; + // The node is part of the list of fixed arguments. + if (Index == (EAML_PARSE_INDEX)AmlGetFixedArgumentCount ( + (AML_OBJECT_NODE*)Node) + ) { + // It is at the last argument of the fixed argument list. + // Get the first argument of the variable list of arguments. + ChildNode = NULL; + } else { + // Else return the next node in the list of fixed arguments. + return AmlGetFixedArgument ((AML_OBJECT_NODE*)Node, Index); + } + } + } + } // IS_AML_OBJECT_NODE (Node) + + // Else, get the next node in the variable list of arguments. + return AmlGetNextVariableArgument ( + (AML_NODE_HEADER*)Node, + (AML_NODE_HEADER*)ChildNode + ); +} + +/** Get the previous sibling node among the children of the input Node. + + This function traverses the FixedArguments followed by the + VariableArguments at the same level in the hierarchy. + + Fixed arguments are before variable arguments. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: g, f, e, d, c, b, a, NULL + + @param [in] Node The node to get the fixed argument from. + @param [in] ChildNode Get the node before the ChildNode. + + @return The node before the ChildNode among the children of the input Node. + - If ChildNode is NULL, return the last available node among + the variable list of arguments then fixed argument list; + - If ChildNode is the first node of the variable list of arguments, + return the last argument of the fixed argument list; + - If ChildNode is the first node of the fixed argument list, + return NULL. +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetPreviousSibling ( + IN CONST AML_NODE_HEADER * Node, + IN CONST AML_NODE_HEADER * ChildNode + ) +{ + EAML_PARSE_INDEX Index; + EAML_PARSE_INDEX MaxIndex; + + AML_NODE_HEADER * CandidateNode; + + // Node must be a Root Node or an Object Node + // and the ChildNode must not be a Root Node. + if ((!IS_AML_ROOT_NODE (Node) && + !IS_AML_OBJECT_NODE (Node)) || + ((ChildNode != NULL) && + (!IS_AML_OBJECT_NODE (ChildNode) && + !IS_AML_DATA_NODE (ChildNode)))) { + ASSERT (0); + return NULL; + } + + MaxIndex = (EAML_PARSE_INDEX)AmlGetFixedArgumentCount ( + (AML_OBJECT_NODE*)Node + ); + + // Get the last variable argument if no ChildNode. + // Otherwise the fixed argument list is checked first. + if ((ChildNode != NULL) && + IS_AML_OBJECT_NODE (Node) && + (MaxIndex != EAmlParseIndexTerm0)) { + if (AmlIsNodeFixedArgument (ChildNode, &Index)) { + // The node is part of the list of fixed arguments. + if (Index == EAmlParseIndexTerm0) { + // The node is the first fixed argument, return NULL. + return NULL; + } else { + // Return the previous node in the fixed argument list. + return AmlGetFixedArgument ( + (AML_OBJECT_NODE*)Node, + (EAML_PARSE_INDEX)(Index - 1) + ); + } + } + } + + // ChildNode is in the variable list of arguments. + CandidateNode = AmlGetPreviousVariableArgument ( + (AML_NODE_HEADER*)Node, + (AML_NODE_HEADER*)ChildNode + ); + if (CandidateNode != NULL) { + if (!IS_AML_NODE_VALID (CandidateNode)) { + ASSERT (0); + return NULL; + } + // A Node has been found + return CandidateNode; + } else if (MaxIndex != EAmlParseIndexTerm0) { + // ChildNode was the first node of the variable list of arguments. + return AmlGetFixedArgument ( + (AML_OBJECT_NODE*)Node, + (EAML_PARSE_INDEX)(MaxIndex - 1) + ); + } else { + // No fixed arguments or variable arguments. + return NULL; + } +} + +/** Iterate through the nodes in the same order as the AML bytestream. + + The iteration is similar to a depth-first path. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: a, b, i, c, d, e, h, f, g, NULL + Note: The branch i and h will be traversed if it has any children. + + @param [in] Node Pointer to a node. + + @return The next node in the AML bytestream order. + Return NULL if Node is the Node corresponding to the last + bytecode of the tree. +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetNextNode ( + IN CONST AML_NODE_HEADER * Node + ) +{ + AML_NODE_HEADER * ParentNode; + AML_NODE_HEADER * CandidateNode; + + if (!IS_AML_NODE_VALID (Node)) { + ASSERT (0); + return NULL; + } + + if (IS_AML_ROOT_NODE (Node) || IS_AML_OBJECT_NODE (Node)) { + // The node has children. Get the first child. + CandidateNode = AmlGetNextSibling (Node, NULL); + if (CandidateNode != NULL) { + if (!IS_AML_NODE_VALID (CandidateNode)) { + ASSERT (0); + return NULL; + } + // A Node has been found + return CandidateNode; + } else if (IS_AML_ROOT_NODE (Node)) { + // The node is the root node and it doesn't have children. + return NULL; + } + } + + // We have traversed the current branch, go to the parent node + // and start traversing the next branch. + // Keep going up the tree until you reach the root node. + while (1) { + if (IS_AML_ROOT_NODE (Node)) { + // This is the last node of the tree. + return NULL; + } + + ParentNode = AmlGetParent ((AML_NODE_HEADER*)Node); + if (!IS_AML_NODE_VALID (ParentNode)) { + ASSERT (0); + return NULL; + } + + CandidateNode = AmlGetNextSibling (ParentNode, Node); + if (CandidateNode != NULL) { + if (!IS_AML_NODE_VALID (CandidateNode)) { + ASSERT (0); + return NULL; + } + // A Node has been found + return CandidateNode; + } + + Node = ParentNode; + } // while + + return NULL; +} + +/** Iterate through the nodes in the reverse order of the AML bytestream. + + The iteration is similar to a depth-first path, + but done in a reverse order. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: g, f, h, e, d, c, i, b, a, NULL + Note: The branch i and h will be traversed if it has any children. + + @param [in] Node Pointer to a node. + + @return The previous node in the AML bytestream order. + Return NULL if Node is the Node corresponding to the last + bytecode of the tree. +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetPreviousNode ( + IN CONST AML_NODE_HEADER * Node + ) +{ + AML_NODE_HEADER * ParentNode; + AML_NODE_HEADER * CandidateNode; + AML_NODE_HEADER * PreviousNode; + + if (!IS_AML_NODE_VALID (Node)) { + ASSERT (0); + return NULL; + } + + while (1) { + + if (IS_AML_ROOT_NODE (Node)) { + // This is the root node. + return NULL; + } + + ParentNode = AmlGetParent ((AML_NODE_HEADER*)Node); + CandidateNode = AmlGetPreviousSibling (ParentNode, Node); + + if (CandidateNode == NULL) { + // Node is the first child of its parent. + return ParentNode; + } else if (IS_AML_DATA_NODE (CandidateNode)) { + // CandidateNode is a data node, thus it has no children. + return CandidateNode; + } else if (IS_AML_OBJECT_NODE (CandidateNode)) { + // Get the previous node in the list of children of ParentNode, + // then get the last child of this node. + // If this node has children, get its last child, etc. + while (1) { + PreviousNode = CandidateNode; + CandidateNode = AmlGetPreviousSibling (PreviousNode, NULL); + if (CandidateNode == NULL) { + return PreviousNode; + } else if (IS_AML_DATA_NODE (CandidateNode)) { + return CandidateNode; + } + } // while + + } else { + ASSERT (0); + return NULL; + } + } // while +} diff --git a/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeTraversal.h b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeTraversal.h new file mode 100644 index 0000000000000000000000000000000000000000..a4980b716d7542cd64d39094327e21fa2f164a4c --- /dev/null +++ b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeTraversal.h @@ -0,0 +1,138 @@ +/** @file + AML Tree Traversal. + + Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.
+ + SPDX-License-Identifier: BSD-2-Clause-Patent +**/ + +#ifndef AML_TREE_TRAVERSAL_H_ +#define AML_TREE_TRAVERSAL_H_ + +#include + +/** Get the next sibling node among the children of the input Node. + + This function traverses the FixedArguments followed by the + VariableArguments at the same level in the hierarchy. + + Fixed arguments are before variable arguments. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: a, b, c, d, e, f, g, NULL + + + @param [in] Node Pointer to a root node or an object node. + @param [in] ChildNode Get the node after the ChildNode. + + @return The node after the ChildNode among the children of the input Node. + - If ChildNode is NULL, return the first available node among + the fixed argument list then variable list of arguments; + - If ChildNode is the last node of the fixed argument list, + return the first argument of the variable list of arguments; + - If ChildNode is the last node of the variable list of arguments, + return NULL. + +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetNextSibling ( + IN CONST AML_NODE_HEADER * Node, + IN CONST AML_NODE_HEADER * ChildNode + ); + +/** Get the previous sibling node among the children of the input Node. + + This function traverses the FixedArguments followed by the + VariableArguments at the same level in the hierarchy. + + Fixed arguments are before variable arguments. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: g, f, e, d, c, b, a, NULL + + @param [in] Node The node to get the fixed argument from. + @param [in] ChildNode Get the node before the ChildNode. + + @return The node before the ChildNode among the children of the input Node. + - If ChildNode is NULL, return the last available node among + the variable list of arguments then fixed argument list; + - If ChildNode is the first node of the variable list of arguments, + return the last argument of the fixed argument list; + - If ChildNode is the first node of the fixed argument list, + return NULL. +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetPreviousSibling ( + IN CONST AML_NODE_HEADER * Node, + IN CONST AML_NODE_HEADER * ChildNode + ); + +/** Iterate through the nodes in the same order as the AML bytestream. + + The iteration is similar to a depth-first path. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: a, b, i, c, d, e, h, f, g, NULL + Note: The branch i and h will be traversed if it has any children. + + @param [in] Node Pointer to a node. + + @return The next node in the AML bytestream order. + Return NULL if Node is the Node corresponding to the last + bytecode of the tree. +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetNextNode ( + IN CONST AML_NODE_HEADER * Node + ); + +/** Iterate through the nodes in the reverse order of the AML bytestream. + + The iteration is similar to a depth-first path, + but done in a reverse order. + + (Node) /-i # Child of fixed argument b + \ / + |- [a][b][c][d] # Fixed Arguments + |- {(e)->(f)->(g)} # Variable Arguments + \ + \-h # Child of variable argument e + + Traversal Order: g, f, h, e, d, c, i, b, a, NULL + Note: The branch i and h will be traversed if it has any children. + + @param [in] Node Pointer to a node. + + @return The previous node in the AML bytestream order. + Return NULL if Node is the Node corresponding to the last + bytecode of the tree. +**/ +AML_NODE_HEADER * +EFIAPI +AmlGetPreviousNode ( + IN CONST AML_NODE_HEADER * Node + ); + +#endif // AML_TREE_TRAVERSAL_H_ + -- 'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'