[PATCH v1 08/30] DynamicTablesPkg: AML tree iterator

["Sami Mujawar" <sami.mujawar@arm.com>]

From: Pierre Gondois <pierre.gondois@arm.com>

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>
---
 DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c | 353 ++++++++++++++++++++
 DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.h | 220 ++++++++++++
 2 files changed, 573 insertions(+)

diff --git a/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c b/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeIterator.c
new file mode 100644
index 0000000000000000000000000000000000000000..e99c234990c669c89767d922aad75627adb2c350
--- /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 0000000000000000000000000000000000000000..d96eecab916818ceb0ab46a25e5151916cd4451d
--- /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_
-- 
'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'