path: root/DynamicTablesPkg/Library/Common/AmlLib/Tree/AmlTreeTraversal.c

/** @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
}