[PATCH v1 07/30] DynamicTablesPkg: AML tree traversal

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

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

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 <pierre.gondois@arm.com>
Signed-off-by: Sami Mujawar <sami.mujawar@arm.com>
---
 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.<BR>
+
+  SPDX-License-Identifier: BSD-2-Clause-Patent
+**/
+
+#include <Tree/AmlTreeTraversal.h>
+
+#include <AmlCoreInterface.h>
+#include <Tree/AmlTree.h>
+
+/** 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.<BR>
+
+  SPDX-License-Identifier: BSD-2-Clause-Patent
+**/
+
+#ifndef AML_TREE_TRAVERSAL_H_
+#define AML_TREE_TRAVERSAL_H_
+
+#include <AmlNodeDefines.h>
+
+/** 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)'