diff options
| author | Pierre Gondois <pierre.gondois@arm.com> | 2020-08-03 16:39:57 +0100 |
|---|---|---|
| committer | mergify[bot] <37929162+mergify[bot]@users.noreply.github.com> | 2020-08-13 18:00:06 +0000 |
| commit | e2c1104c504024b6bbee7c34a87cc9add59f37d5 (patch) | |
| tree | 0c1036d21059b3a22ec48fc262e24a34b50a512b /DynamicTablesPkg | |
| parent | f96dd8185d6ba79de57fc6c4f9ccc4d7482b1200 (diff) | |
| download | edk2-e2c1104c504024b6bbee7c34a87cc9add59f37d5.tar.gz edk2-e2c1104c504024b6bbee7c34a87cc9add59f37d5.tar.bz2 edk2-e2c1104c504024b6bbee7c34a87cc9add59f37d5.zip | |
DynamicTablesPkg: AML tree iterator
The AML tree iterator provides interfaces to traverse the nodes
in the AML tree. The iterator can traverse the AML tree nodes in
the following order:
- Linear progression: Iterate following the AML byte stream
order (depth first).
- Branch progression: Iterate following the AML byte stream
order (depth first), but stop iterating
at the end of the branch.
Signed-off-by: Pierre Gondois <pierre.gondois@arm.com>
Signed-off-by: Sami Mujawar <sami.mujawar@arm.com>
Reviewed-by: Alexei Fedorov <Alexei.Fedorov@arm.com>
Diffstat (limited to 'DynamicTablesPkg')
| -rw-r--r-- | DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c | 353 | ||||
| -rw-r--r-- | DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.h | 220 |
2 files changed, 573 insertions, 0 deletions
diff --git a/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c new file mode 100644 index 0000000000..e99c234990 --- /dev/null +++ b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c @@ -0,0 +1,353 @@ +/** @file
+ AML Tree Iterator.
+
+ Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.<BR>
+
+ SPDX-License-Identifier: BSD-2-Clause-Patent
+**/
+
+#include <AmlNodeDefines.h>
+#include <Tree/AmlTreeIterator.h>
+
+#include <AmlCoreInterface.h>
+#include <Tree/AmlTreeTraversal.h>
+
+/** Iterator to traverse the tree.
+
+ This is an internal structure.
+*/
+typedef struct AmlTreeInternalIterator {
+ /// External iterator structure, containing the external APIs.
+ /// Must be the first field.
+ AML_TREE_ITERATOR Iterator;
+
+ // Note: The following members of this structure are opaque to the users
+ // of the Tree iterator APIs.
+
+ /// Pointer to the node on which the iterator has been initialized.
+ CONST AML_NODE_HEADER * InitialNode;
+
+ /// Pointer to the current node.
+ CONST AML_NODE_HEADER * CurrentNode;
+
+ /// Iteration mode.
+ /// Allow to choose how to traverse the tree/choose which node is next.
+ EAML_ITERATOR_MODE Mode;
+} AML_TREE_ITERATOR_INTERNAL;
+
+/** Get the current node of an iterator.
+
+ @param [in] Iterator Pointer to an iterator.
+ @param [out] OutNode Pointer holding the current node.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+**/
+STATIC
+EFI_STATUS
+EFIAPI
+AmlIteratorGetNode (
+ IN AML_TREE_ITERATOR * Iterator,
+ OUT AML_NODE_HEADER ** OutNode
+ )
+{
+ AML_TREE_ITERATOR_INTERNAL * InternalIterator;
+
+ InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator;
+
+ // CurrentNode can be NULL, but InitialNode cannot.
+ if ((OutNode == NULL) ||
+ (InternalIterator == NULL) ||
+ (InternalIterator->Mode <= EAmlIteratorUnknown) ||
+ (InternalIterator->Mode >= EAmlIteratorModeMax) ||
+ !IS_AML_NODE_VALID (InternalIterator->InitialNode) ||
+ ((InternalIterator->CurrentNode != NULL) &&
+ !IS_AML_NODE_VALID (InternalIterator->CurrentNode))) {
+ ASSERT (0);
+ return EFI_INVALID_PARAMETER;
+ }
+
+ *OutNode = (AML_NODE_HEADER*)InternalIterator->CurrentNode;
+
+ return EFI_SUCCESS;
+}
+
+/** Move the current node of the iterator to the next node,
+ according to the iteration mode selected.
+
+ If NextNode is not NULL, return the next node.
+
+ @param [in] Iterator Pointer to an iterator.
+ @param [out] NextNode If not NULL, updated to the next node.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+**/
+STATIC
+EFI_STATUS
+EFIAPI
+AmlIteratorGetNextLinear (
+ IN AML_TREE_ITERATOR * Iterator,
+ OUT AML_NODE_HEADER ** NextNode
+ )
+{
+ AML_TREE_ITERATOR_INTERNAL * InternalIterator;
+
+ InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator;
+
+ // CurrentNode can be NULL, but InitialNode cannot.
+ if ((InternalIterator == NULL) ||
+ (InternalIterator->Mode != EAmlIteratorLinear) ||
+ !IS_AML_NODE_VALID (InternalIterator->InitialNode) ||
+ !IS_AML_NODE_VALID (InternalIterator->CurrentNode)) {
+ ASSERT (0);
+ return EFI_INVALID_PARAMETER;
+ }
+
+ // Get the next node according to the iteration mode.
+ InternalIterator->CurrentNode = AmlGetNextNode (
+ InternalIterator->CurrentNode
+ );
+
+ if (NextNode != NULL) {
+ *NextNode = (AML_NODE_HEADER*)InternalIterator->CurrentNode;
+ }
+ return EFI_SUCCESS;
+}
+
+/** Move the current node of the iterator to the previous node,
+ according to the iteration mode selected.
+
+ If PrevNode is not NULL, return the previous node.
+
+ @param [in] Iterator Pointer to an iterator.
+ @param [out] PrevNode If not NULL, updated to the previous node.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+**/
+STATIC
+EFI_STATUS
+EFIAPI
+AmlIteratorGetPreviousLinear (
+ IN AML_TREE_ITERATOR * Iterator,
+ OUT AML_NODE_HEADER ** PrevNode
+ )
+{
+ AML_TREE_ITERATOR_INTERNAL * InternalIterator;
+
+ InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator;
+
+ // CurrentNode can be NULL, but InitialNode cannot.
+ if ((InternalIterator == NULL) ||
+ (InternalIterator->Mode != EAmlIteratorLinear) ||
+ !IS_AML_NODE_VALID (InternalIterator->InitialNode) ||
+ !IS_AML_NODE_VALID (InternalIterator->CurrentNode)) {
+ ASSERT (0);
+ return EFI_INVALID_PARAMETER;
+ }
+
+ // Get the previous node according to the iteration mode.
+ InternalIterator->CurrentNode = AmlGetPreviousNode (
+ InternalIterator->CurrentNode
+ );
+ if (PrevNode != NULL) {
+ *PrevNode = (AML_NODE_HEADER*)InternalIterator->CurrentNode;
+ }
+ return EFI_SUCCESS;
+}
+
+/** Move the current node of the iterator to the next node,
+ according to the iteration mode selected.
+
+ If NextNode is not NULL, return the next node.
+
+ @param [in] Iterator Pointer to an iterator.
+ @param [out] NextNode If not NULL, updated to the next node.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+**/
+STATIC
+EFI_STATUS
+EFIAPI
+AmlIteratorGetNextBranch (
+ IN AML_TREE_ITERATOR * Iterator,
+ OUT AML_NODE_HEADER ** NextNode
+ )
+{
+ AML_TREE_ITERATOR_INTERNAL * InternalIterator;
+ AML_NODE_HEADER * Node;
+
+ InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator;
+
+ // CurrentNode can be NULL, but InitialNode cannot.
+ if ((InternalIterator == NULL) ||
+ (InternalIterator->Mode != EAmlIteratorBranch) ||
+ !IS_AML_NODE_VALID (InternalIterator->InitialNode) ||
+ !IS_AML_NODE_VALID (InternalIterator->CurrentNode)) {
+ ASSERT (0);
+ return EFI_INVALID_PARAMETER;
+ }
+
+ Node = AmlGetNextNode (InternalIterator->CurrentNode);
+ // Check whether NextNode is a sibling of InitialNode.
+ if (AmlGetParent (Node) ==
+ AmlGetParent ((AML_NODE_HEADER*)InternalIterator->InitialNode)) {
+ Node = NULL;
+ }
+
+ InternalIterator->CurrentNode = Node;
+
+ if (NextNode != NULL) {
+ *NextNode = Node;
+ }
+ return EFI_SUCCESS;
+}
+
+/** Move the current node of the iterator to the previous node,
+ according to the iteration mode selected.
+
+ If PrevNode is not NULL, return the previous node.
+
+ @param [in] Iterator Pointer to an iterator.
+ @param [out] PrevNode If not NULL, updated to the previous node.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+**/
+STATIC
+EFI_STATUS
+EFIAPI
+AmlIteratorGetPreviousBranch (
+ IN AML_TREE_ITERATOR * Iterator,
+ OUT AML_NODE_HEADER ** PrevNode
+ )
+{
+ AML_TREE_ITERATOR_INTERNAL * InternalIterator;
+ AML_NODE_HEADER * Node;
+
+ InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)Iterator;
+
+ // CurrentNode can be NULL, but InitialNode cannot.
+ if ((InternalIterator == NULL) ||
+ (InternalIterator->Mode != EAmlIteratorBranch) ||
+ !IS_AML_NODE_VALID (InternalIterator->InitialNode) ||
+ !IS_AML_NODE_VALID (InternalIterator->CurrentNode)) {
+ ASSERT (0);
+ return EFI_INVALID_PARAMETER;
+ }
+
+ Node = AmlGetPreviousNode (InternalIterator->CurrentNode);
+ // Check whether PreviousNode is a sibling of InitialNode.
+ if (AmlGetParent (Node) ==
+ AmlGetParent ((AML_NODE_HEADER*)InternalIterator->InitialNode)) {
+ Node = NULL;
+ }
+
+ InternalIterator->CurrentNode = Node;
+
+ if (PrevNode != NULL) {
+ *PrevNode = Node;
+ }
+ return EFI_SUCCESS;
+}
+
+/** Initialize an iterator.
+
+ Note: The caller must call AmlDeleteIterator () to free the memory
+ allocated for the iterator.
+
+ @param [in] Node Pointer to the node.
+ @param [in] IteratorMode Selected mode to traverse the tree.
+ @param [out] IteratorPtr Pointer holding the created iterator.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+ @retval EFI_OUT_OF_RESOURCES Could not allocate memory.
+**/
+EFI_STATUS
+EFIAPI
+AmlInitializeIterator (
+ IN AML_NODE_HEADER * Node,
+ IN EAML_ITERATOR_MODE IteratorMode,
+ OUT AML_TREE_ITERATOR ** IteratorPtr
+ )
+{
+ AML_TREE_ITERATOR_INTERNAL * InternalIterator;
+
+ if (!IS_AML_NODE_VALID (Node) ||
+ (IteratorMode <= EAmlIteratorUnknown) ||
+ (IteratorMode >= EAmlIteratorModeMax) ||
+ (IteratorPtr == NULL)) {
+ ASSERT (0);
+ return EFI_INVALID_PARAMETER;
+ }
+
+ *IteratorPtr = NULL;
+ InternalIterator = (AML_TREE_ITERATOR_INTERNAL*)AllocateZeroPool (
+ sizeof (
+ AML_TREE_ITERATOR_INTERNAL
+ )
+ );
+ if (InternalIterator == NULL) {
+ ASSERT (0);
+ return EFI_OUT_OF_RESOURCES;
+ }
+
+ InternalIterator->InitialNode = Node;
+ InternalIterator->CurrentNode = Node;
+ InternalIterator->Mode = IteratorMode;
+ InternalIterator->Iterator.GetNode = AmlIteratorGetNode;
+
+ switch (InternalIterator->Mode) {
+ case EAmlIteratorLinear:
+ {
+ InternalIterator->Iterator.GetNext = AmlIteratorGetNextLinear;
+ InternalIterator->Iterator.GetPrevious = AmlIteratorGetPreviousLinear;
+ break;
+ }
+ case EAmlIteratorBranch:
+ {
+ InternalIterator->Iterator.GetNext = AmlIteratorGetNextBranch;
+ InternalIterator->Iterator.GetPrevious = AmlIteratorGetPreviousBranch;
+ break;
+ }
+ default:
+ {
+ ASSERT (0);
+ FreePool (InternalIterator);
+ return EFI_INVALID_PARAMETER;
+ }
+ } // switch
+
+ *IteratorPtr = &InternalIterator->Iterator;
+
+ return EFI_SUCCESS;
+}
+
+/** Delete an iterator.
+
+ Note: The caller must have first initialized the iterator with the
+ AmlInitializeIterator () function.
+
+ @param [in] Iterator Pointer to an iterator.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlDeleteIterator (
+ IN AML_TREE_ITERATOR * Iterator
+ )
+{
+ if (Iterator == NULL) {
+ ASSERT (0);
+ return EFI_INVALID_PARAMETER;
+ }
+
+ FreePool (Iterator);
+
+ return EFI_SUCCESS;
+}
diff --git a/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.h b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.h new file mode 100644 index 0000000000..d96eecab91 --- /dev/null +++ b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.h @@ -0,0 +1,220 @@ +/** @file
+ AML Iterator.
+
+ Copyright (c) 2019 - 2020, Arm Limited. All rights reserved.<BR>
+
+ SPDX-License-Identifier: BSD-2-Clause-Patent
+**/
+
+#ifndef AML_ITERATOR_H_
+#define AML_ITERATOR_H_
+
+/* This header file does not include internal Node definition,
+ i.e. AML_ROOT_NODE, AML_OBJECT_NODE, etc. The node definitions
+ must be included by the caller file. The function prototypes must
+ only expose AML_NODE_HANDLE, AML_ROOT_NODE_HANDLE, etc. node
+ definitions.
+ This allows to keep the functions defined here both internal and
+ potentially external. If necessary, any function of this file can
+ be exposed externally.
+ The Api folder is internal to the AmlLib, but should only use these
+ functions. They provide a "safe" way to interact with the AmlLib.
+*/
+
+/**
+ @defgroup IteratorLibrary Iterator library
+ @ingroup NavigationApis
+ @{
+ The iterator library allow to navigate in the AML tree using an iterator.
+ It is possible to initialize/delete an iterator.
+
+ This iterator can progress in the tree by different orders:
+ - Linear progression: Iterate following the AML bytestream order
+ (depth first).
+ - Branch progression: Iterate following the AML bytestream order
+ (depth first), but stop iterating at the
+ end of the branch.
+
+ An iterator has the following features:
+ - GetNode: Get the current node pointed by the iterator.
+ - GetNext: Move the current node of the iterator to the next
+ node, according to the iteration mode selected.
+ - GetPrevious: Move the current node of the iterator to the previous
+ node, according to the iteration mode selected.
+ @}
+*/
+
+/**
+ @defgroup IteratorApis Iterator APIs
+ @ingroup IteratorLibrary
+ @{
+ Iterator APIs defines the action that can be done on an iterator:
+ - Initialization;
+ - Deletion;
+ - Getting the node currently pointed by the iterator;
+ - Moving to the next node;
+ - Moving to the previous node.
+ @}
+*/
+
+/**
+ @defgroup IteratorStructures Iterator structures
+ @ingroup IteratorLibrary
+ @{
+ Iterator structures define the enum/define values and structures related
+ to iterators.
+ @}
+*/
+
+/** Iterator mode.
+
+ Modes to choose how the iterator is progressing in the tree.
+ A
+ \-B <- Iterator initialized with this node.
+ | \-C
+ | | \-D
+ | \-E
+ | \-F
+ | \-G
+ \-H
+ \-I
+
+ @ingroup IteratorStructures
+*/
+typedef enum EAmlIteratorMode {
+ EAmlIteratorUnknown, ///< Unknown/Invalid AML IteratorMode
+ EAmlIteratorLinear, ///< Iterate following the AML bytestream order
+ /// (depth first).
+ /// The order followed by the iterator would be:
+ /// B, C, D, E, F, G, H, I, NULL.
+ EAmlIteratorBranch, ///< Iterate through the node of a branch.
+ /// The iteration follows the AML bytestream
+ /// order but within the branch B.
+ /// The order followed by the iterator would be:
+ /// B, C, D, E, F, G, NULL.
+ EAmlIteratorModeMax ///< Max enum.
+} EAML_ITERATOR_MODE;
+
+/** Iterator.
+
+ Allows to traverse the tree in different orders.
+
+ @ingroup IteratorStructures
+*/
+typedef struct AmlTreeIterator AML_TREE_ITERATOR;
+
+/** Function pointer to a get the current node of the iterator.
+
+ @ingroup IteratorApis
+
+ @param [in] Iterator Pointer to an iterator.
+ @param [out] OutNode Pointer holding the current node.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+*/
+typedef
+EFI_STATUS
+(EFIAPI * EDKII_AML_TREE_ITERATOR_GET_NODE) (
+ IN AML_TREE_ITERATOR * Iterator,
+ OUT AML_NODE_HANDLE * OutNode
+ );
+
+/** Function pointer to move the current node of the iterator to the
+ next node, according to the iteration mode selected.
+
+ If NextNode is not NULL, return the next node.
+
+ @ingroup IteratorApis
+
+ @param [in] Iterator Pointer to an iterator.
+ @param [out] NextNode If not NULL, updated to the next node.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+*/
+typedef
+EFI_STATUS
+(EFIAPI * EDKII_AML_TREE_ITERATOR_GET_NEXT) (
+ IN AML_TREE_ITERATOR * Iterator,
+ OUT AML_NODE_HANDLE * NextNode
+ );
+
+/** Function pointer to move the current node of the iterator to the
+ previous node, according to the iteration mode selected.
+
+ If PrevNode is not NULL, return the previous node.
+
+ @ingroup IteratorApis
+
+ @param [in] Iterator Pointer to an iterator.
+ @param [out] PrevNode If not NULL, updated to the previous node.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+*/
+typedef
+EFI_STATUS
+(EFIAPI * EDKII_AML_TREE_ITERATOR_GET_PREVIOUS) (
+ IN AML_TREE_ITERATOR * Iterator,
+ OUT AML_NODE_HANDLE * PrevNode
+ );
+
+/** Iterator structure to traverse the tree.
+
+ @ingroup IteratorStructures
+*/
+typedef struct AmlTreeIterator {
+ /// Get the current node of the iterator.
+ EDKII_AML_TREE_ITERATOR_GET_NODE GetNode;
+
+ /// Update the current node of the iterator with the next node.
+ EDKII_AML_TREE_ITERATOR_GET_NEXT GetNext;
+
+ /// Update the current node of the iterator with the previous node.
+ EDKII_AML_TREE_ITERATOR_GET_PREVIOUS GetPrevious;
+} AML_TREE_ITERATOR;
+
+
+/** Initialize an iterator.
+
+ Note: The caller must call AmlDeleteIterator () to free the memory
+ allocated for the iterator.
+
+ @ingroup IteratorApis
+
+ @param [in] Node Pointer to the node.
+ @param [in] IteratorMode Selected mode to traverse the tree.
+ @param [out] IteratorPtr Pointer holding the created iterator.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+ @retval EFI_OUT_OF_RESOURCES Could not allocate memory.
+**/
+EFI_STATUS
+EFIAPI
+AmlInitializeIterator (
+ IN AML_NODE_HANDLE Node,
+ IN EAML_ITERATOR_MODE IteratorMode,
+ OUT AML_TREE_ITERATOR ** IteratorPtr
+ );
+
+/** Delete an iterator.
+
+ Note: The caller must have first initialized the iterator with the
+ AmlInitializeIterator () function.
+
+ @ingroup IteratorApis
+
+ @param [in] Iterator Pointer to an iterator.
+
+ @retval EFI_SUCCESS The function completed successfully.
+ @retval EFI_INVALID_PARAMETER Invalid parameter.
+**/
+EFI_STATUS
+EFIAPI
+AmlDeleteIterator (
+ IN AML_TREE_ITERATOR * Iterator
+ );
+
+#endif // AML_ITERATOR_H_
|