[PATCH v3 1/2] MdePkg/BaseLib: Add IsNodeInList() function.

[PATCH v3 1/2] MdePkg/BaseLib: Add IsNodeInList() function.

[Marvin Häuser]

This patch adds IsNodeInList() to BaseLib, which verifies the given
Node is part of the doubly-linked List provided.

V2:
  - Rename "List" to "FirstEntry" and "Node" to "SecondEntry" to clarify that
    "FirstEntry" does not need to be the doubly-linked list's head node.

V3:
  - Remove ASSERTs from IsNodeInList() which are present in
    InternalBaseLibIsListValid().

Contributed-under: TianoCore Contribution Agreement 1.1
Signed-off-by: Marvin Haeuser <Marvin.Haeuser@outlook.com>
---
 MdePkg/Library/BaseLib/LinkedList.c       | 66 +++++++++++++++++++-
 MdePkg/Include/Library/BaseLib.h          | 27 ++++++++
 MdePkg/Library/BaseLib/BaseLibInternals.h | 28 ---------
 3 files changed, 92 insertions(+), 29 deletions(-)

diff --git a/MdePkg/Library/BaseLib/LinkedList.c b/MdePkg/Library/BaseLib/LinkedList.c
index ba373f4b7be3..af27b0dd9a5c 100644
--- a/MdePkg/Library/BaseLib/LinkedList.c
+++ b/MdePkg/Library/BaseLib/LinkedList.c
@@ -1,7 +1,7 @@
 /** @file
   Linked List Library Functions.
 
-  Copyright (c) 2006 - 2013, Intel Corporation. All rights reserved.<BR>
+  Copyright (c) 2006 - 2017, Intel Corporation. All rights reserved.<BR>
   This program and the accompanying materials
   are licensed and made available under the terms and conditions of the BSD License
   which accompanies this distribution.  The full text of the license may be found at
@@ -113,6 +113,70 @@ InternalBaseLibIsNodeInList (
 }
 
 /**
+  Checks whether FirstEntry and SecondEntry are part of the same doubly-linked
+  list.
+
+  If FirstEntry is NULL, then ASSERT().
+  If FirstEntry->ForwardLink is NULL, then ASSERT().
+  If FirstEntry->BackLink is NULL, then ASSERT().
+  If SecondEntry is NULL, then ASSERT();
+  If PcdMaximumLinkedListLength is not zero, and List contains more than
+  PcdMaximumLinkedListLength nodes, then ASSERT().
+
+  @param  FirstEntry   A pointer to a node in a linked list.
+  @param  SecondEntry  A pointer to the node to locate.
+
+  @retval TRUE   SecondEntry is in the same doubly-linked list as FirstEntry.
+  @retval FALSE  SecondEntry isn't in the same doubly-linked list as FirstEntry,
+                 or FirstEntry is invalid.
+
+**/
+BOOLEAN
+EFIAPI
+IsNodeInList (
+  IN      CONST LIST_ENTRY      *FirstEntry,
+  IN      CONST LIST_ENTRY      *SecondEntry
+  )
+{
+  UINTN             Count;
+  CONST LIST_ENTRY  *Ptr;
+
+  //
+  // ASSERT List not too long
+  //
+  ASSERT (InternalBaseLibIsListValid (FirstEntry));
+
+  ASSERT (SecondEntry != NULL);
+
+  Count = 0;
+  Ptr   = FirstEntry;
+
+  //
+  // Check to see if SecondEntry is a member of FirstEntry.  
+  // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
+  //
+  do {
+    Ptr = Ptr->ForwardLink;
+    if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
+      Count++;
+
+      //
+      // Return if the linked list is too long
+      //
+      if (Count == PcdGet32 (PcdMaximumLinkedListLength)) {
+        return (BOOLEAN)(Ptr == SecondEntry);
+      }
+    }
+
+    if (Ptr == SecondEntry) {
+      return TRUE;
+    }
+  } while (Ptr != FirstEntry);
+
+  return FALSE;
+}
+
+/**
   Initializes the head node of a doubly-linked list, and returns the pointer to
   the head node of the doubly-linked list.
 
diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/BaseLib.h
index 791849b80406..40b96b761a85 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -2869,6 +2869,33 @@ PathCleanUpDirectories(
 
 
 /**
+  Checks whether FirstEntry and SecondEntry are part of the same doubly-linked
+  list.
+
+  If FirstEntry is NULL, then ASSERT().
+  If FirstEntry->ForwardLink is NULL, then ASSERT().
+  If FirstEntry->BackLink is NULL, then ASSERT().
+  If SecondEntry is NULL, then ASSERT();
+  If PcdMaximumLinkedListLength is not zero, and List contains more than
+  PcdMaximumLinkedListLength nodes, then ASSERT().
+
+  @param  FirstEntry   A pointer to a node in a linked list.
+  @param  SecondEntry  A pointer to the node to locate.
+
+  @retval TRUE   SecondEntry is in the same doubly-linked list as FirstEntry.
+  @retval FALSE  SecondEntry isn't in the same doubly-linked list as FirstEntry,
+                 or FirstEntry is invalid.
+
+**/
+BOOLEAN
+EFIAPI
+IsNodeInList (
+  IN      CONST LIST_ENTRY      *FirstEntry,
+  IN      CONST LIST_ENTRY      *SecondEntry
+  );
+
+
+/**
   Initializes the head node of a doubly linked list, and returns the pointer to
   the head node of the doubly linked list.
 
diff --git a/MdePkg/Library/BaseLib/BaseLibInternals.h b/MdePkg/Library/BaseLib/BaseLibInternals.h
index ea387ce37d27..9dca97a0dcc9 100644
--- a/MdePkg/Library/BaseLib/BaseLibInternals.h
+++ b/MdePkg/Library/BaseLib/BaseLibInternals.h
@@ -340,34 +340,6 @@ InternalSwitchStack (
 
 
 /**
-  Worker function that locates the Node in the List.
-
-  By searching the List, finds the location of the Node in List. At the same time,
-  verifies the validity of this list.
-
-  If List is NULL, then ASSERT().
-  If List->ForwardLink is NULL, then ASSERT().
-  If List->backLink is NULL, then ASSERT().
-  If Node is NULL, then ASSERT();
-  If PcdMaximumLinkedListLength is not zero, and prior to insertion the number
-  of nodes in ListHead, including the ListHead node, is greater than or
-  equal to PcdMaximumLinkedListLength, then ASSERT().
-
-  @param  List  A pointer to a node in a linked list.
-  @param  Node  A pointer to one nod.
-
-  @retval TRUE   Node is in List.
-  @retval FALSE  Node isn't in List, or List is invalid.
-
-**/
-BOOLEAN
-EFIAPI
-IsNodeInList (
-  IN      CONST LIST_ENTRY      *List,
-  IN      CONST LIST_ENTRY      *Node
-  );
-
-/**
   Worker function that returns a bit field from Operand.
 
   Returns the bitfield specified by the StartBit and the EndBit from Operand.
-- 
2.12.2.windows.2

Re: [PATCH v3 1/2] MdePkg/BaseLib: Add IsNodeInList() function.

[Gao, Liming]

Marvin:
  I have no other comments. Reviewed-by: Liming Gao <liming.gao@intel.com>

Thanks
Liming
> -----Original Message-----
> From: Marvin Häuser [mailto:Marvin.Haeuser@outlook.com]
> Sent: Friday, August 4, 2017 3:52 AM
> To: edk2-devel@lists.01.org
> Cc: Kinney, Michael D <michael.d.kinney@intel.com>; Gao, Liming <liming.gao@intel.com>
> Subject: [PATCH v3 1/2] MdePkg/BaseLib: Add IsNodeInList() function.
> 
> This patch adds IsNodeInList() to BaseLib, which verifies the given
> Node is part of the doubly-linked List provided.
> 
> V2:
>   - Rename "List" to "FirstEntry" and "Node" to "SecondEntry" to clarify that
>     "FirstEntry" does not need to be the doubly-linked list's head node.
> 
> V3:
>   - Remove ASSERTs from IsNodeInList() which are present in
>     InternalBaseLibIsListValid().
> 
> Contributed-under: TianoCore Contribution Agreement 1.1
> Signed-off-by: Marvin Haeuser <Marvin.Haeuser@outlook.com>
> ---
>  MdePkg/Library/BaseLib/LinkedList.c       | 66 +++++++++++++++++++-
>  MdePkg/Include/Library/BaseLib.h          | 27 ++++++++
>  MdePkg/Library/BaseLib/BaseLibInternals.h | 28 ---------
>  3 files changed, 92 insertions(+), 29 deletions(-)
> 
> diff --git a/MdePkg/Library/BaseLib/LinkedList.c b/MdePkg/Library/BaseLib/LinkedList.c
> index ba373f4b7be3..af27b0dd9a5c 100644
> --- a/MdePkg/Library/BaseLib/LinkedList.c
> +++ b/MdePkg/Library/BaseLib/LinkedList.c
> @@ -1,7 +1,7 @@
>  /** @file
>    Linked List Library Functions.
> 
> -  Copyright (c) 2006 - 2013, Intel Corporation. All rights reserved.<BR>
> +  Copyright (c) 2006 - 2017, Intel Corporation. All rights reserved.<BR>
>    This program and the accompanying materials
>    are licensed and made available under the terms and conditions of the BSD License
>    which accompanies this distribution.  The full text of the license may be found at
> @@ -113,6 +113,70 @@ InternalBaseLibIsNodeInList (
>  }
> 
>  /**
> +  Checks whether FirstEntry and SecondEntry are part of the same doubly-linked
> +  list.
> +
> +  If FirstEntry is NULL, then ASSERT().
> +  If FirstEntry->ForwardLink is NULL, then ASSERT().
> +  If FirstEntry->BackLink is NULL, then ASSERT().
> +  If SecondEntry is NULL, then ASSERT();
> +  If PcdMaximumLinkedListLength is not zero, and List contains more than
> +  PcdMaximumLinkedListLength nodes, then ASSERT().
> +
> +  @param  FirstEntry   A pointer to a node in a linked list.
> +  @param  SecondEntry  A pointer to the node to locate.
> +
> +  @retval TRUE   SecondEntry is in the same doubly-linked list as FirstEntry.
> +  @retval FALSE  SecondEntry isn't in the same doubly-linked list as FirstEntry,
> +                 or FirstEntry is invalid.
> +
> +**/
> +BOOLEAN
> +EFIAPI
> +IsNodeInList (
> +  IN      CONST LIST_ENTRY      *FirstEntry,
> +  IN      CONST LIST_ENTRY      *SecondEntry
> +  )
> +{
> +  UINTN             Count;
> +  CONST LIST_ENTRY  *Ptr;
> +
> +  //
> +  // ASSERT List not too long
> +  //
> +  ASSERT (InternalBaseLibIsListValid (FirstEntry));
> +
> +  ASSERT (SecondEntry != NULL);
> +
> +  Count = 0;
> +  Ptr   = FirstEntry;
> +
> +  //
> +  // Check to see if SecondEntry is a member of FirstEntry.
> +  // Exit early if the number of nodes in List >= PcdMaximumLinkedListLength
> +  //
> +  do {
> +    Ptr = Ptr->ForwardLink;
> +    if (PcdGet32 (PcdMaximumLinkedListLength) > 0) {
> +      Count++;
> +
> +      //
> +      // Return if the linked list is too long
> +      //
> +      if (Count == PcdGet32 (PcdMaximumLinkedListLength)) {
> +        return (BOOLEAN)(Ptr == SecondEntry);
> +      }
> +    }
> +
> +    if (Ptr == SecondEntry) {
> +      return TRUE;
> +    }
> +  } while (Ptr != FirstEntry);
> +
> +  return FALSE;
> +}
> +
> +/**
>    Initializes the head node of a doubly-linked list, and returns the pointer to
>    the head node of the doubly-linked list.
> 
> diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/BaseLib.h
> index 791849b80406..40b96b761a85 100644
> --- a/MdePkg/Include/Library/BaseLib.h
> +++ b/MdePkg/Include/Library/BaseLib.h
> @@ -2869,6 +2869,33 @@ PathCleanUpDirectories(
> 
> 
>  /**
> +  Checks whether FirstEntry and SecondEntry are part of the same doubly-linked
> +  list.
> +
> +  If FirstEntry is NULL, then ASSERT().
> +  If FirstEntry->ForwardLink is NULL, then ASSERT().
> +  If FirstEntry->BackLink is NULL, then ASSERT().
> +  If SecondEntry is NULL, then ASSERT();
> +  If PcdMaximumLinkedListLength is not zero, and List contains more than
> +  PcdMaximumLinkedListLength nodes, then ASSERT().
> +
> +  @param  FirstEntry   A pointer to a node in a linked list.
> +  @param  SecondEntry  A pointer to the node to locate.
> +
> +  @retval TRUE   SecondEntry is in the same doubly-linked list as FirstEntry.
> +  @retval FALSE  SecondEntry isn't in the same doubly-linked list as FirstEntry,
> +                 or FirstEntry is invalid.
> +
> +**/
> +BOOLEAN
> +EFIAPI
> +IsNodeInList (
> +  IN      CONST LIST_ENTRY      *FirstEntry,
> +  IN      CONST LIST_ENTRY      *SecondEntry
> +  );
> +
> +
> +/**
>    Initializes the head node of a doubly linked list, and returns the pointer to
>    the head node of the doubly linked list.
> 
> diff --git a/MdePkg/Library/BaseLib/BaseLibInternals.h b/MdePkg/Library/BaseLib/BaseLibInternals.h
> index ea387ce37d27..9dca97a0dcc9 100644
> --- a/MdePkg/Library/BaseLib/BaseLibInternals.h
> +++ b/MdePkg/Library/BaseLib/BaseLibInternals.h
> @@ -340,34 +340,6 @@ InternalSwitchStack (
> 
> 
>  /**
> -  Worker function that locates the Node in the List.
> -
> -  By searching the List, finds the location of the Node in List. At the same time,
> -  verifies the validity of this list.
> -
> -  If List is NULL, then ASSERT().
> -  If List->ForwardLink is NULL, then ASSERT().
> -  If List->backLink is NULL, then ASSERT().
> -  If Node is NULL, then ASSERT();
> -  If PcdMaximumLinkedListLength is not zero, and prior to insertion the number
> -  of nodes in ListHead, including the ListHead node, is greater than or
> -  equal to PcdMaximumLinkedListLength, then ASSERT().
> -
> -  @param  List  A pointer to a node in a linked list.
> -  @param  Node  A pointer to one nod.
> -
> -  @retval TRUE   Node is in List.
> -  @retval FALSE  Node isn't in List, or List is invalid.
> -
> -**/
> -BOOLEAN
> -EFIAPI
> -IsNodeInList (
> -  IN      CONST LIST_ENTRY      *List,
> -  IN      CONST LIST_ENTRY      *Node
> -  );
> -
> -/**
>    Worker function that returns a bit field from Operand.
> 
>    Returns the bitfield specified by the StartBit and the EndBit from Operand.
> --
> 2.12.2.windows.2