From: Krzysztof Koch <krzysztof.koch@arm.com>
Date: Tue, 9 Apr 2019 09:41:40 +0000 (+0100)
Subject: DynamicTablesPkg: Add code for finding duplicate values in arrays
X-Git-Tag: edk2-stable201908~433
X-Git-Url: https://git.proxmox.com/?p=mirror_edk2.git;a=commitdiff_plain;h=c1b53091f60fb301a71238e6ef38834d48757d96;ds=sidebyside

DynamicTablesPkg: Add code for finding duplicate values in arrays

Added generic function for detecting duplicate values in an array.

Also defined a function prototype to test if two objects are equal.
The prototype is used as an argument to the 'FindDuplicateValues'
function.

Signed-off-by: Krzysztof Koch <krzysztof.koch@arm.com>
Reviewed-by: Alexei Fedorov <Alexei.Fedorov@arm.com>
Reviewed-by: Sami Mujawar <sami.mujawar@arm.com>
---

diff --git a/DynamicTablesPkg/Include/Library/TableHelperLib.h b/DynamicTablesPkg/Include/Library/TableHelperLib.h
index 9c5b383541..e4a8dfa046 100644
--- a/DynamicTablesPkg/Include/Library/TableHelperLib.h
+++ b/DynamicTablesPkg/Include/Library/TableHelperLib.h
@@ -4,6 +4,9 @@
 
   SPDX-License-Identifier: BSD-2-Clause-Patent
 
+  @par Glossary:
+    - PFN   - Pointer to a Function
+
 **/
 
 #ifndef TABLE_HELPER_LIB_H_
@@ -59,4 +62,49 @@ AddAcpiHeader (
   IN      CONST UINT32                                        Length
   );
 
+/**
+  Function prototype for testing if two arbitrary objects are equal.
+
+  @param [in] Object1           Pointer to the first object to compare.
+  @param [in] Object2           Pointer to the second object to compare.
+  @param [in] Index1            Index of Object1. This value is optional and
+                                can be ignored by the specified implementation.
+  @param [in] Index2            Index of Object2. This value is optional and
+                                can be ignored by the specified implementation.
+
+  @retval TRUE                  Object1 and Object2 are equal.
+  @retval FALSE                 Object1 and Object2 are NOT equal.
+**/
+typedef
+BOOLEAN
+(EFIAPI *PFN_IS_EQUAL)(
+  IN CONST  VOID            * Object1,
+  IN CONST  VOID            * Object2,
+  IN        UINTN             Index1 OPTIONAL,
+  IN        UINTN             Index2 OPTIONAL
+  );
+
+/**
+  Test and report if a duplicate entry exists in the given array of comparable
+  elements.
+
+  @param [in] Array                 Array of elements to test for duplicates.
+  @param [in] Count                 Number of elements in Array.
+  @param [in] ElementSize           Size of an element in bytes
+  @param [in] EqualTestFunction     The function to call to check if any two
+                                    elements are equal.
+
+  @retval TRUE                      A duplicate element was found or one of
+                                    the input arguments is invalid.
+  @retval FALSE                     Every element in Array is unique.
+**/
+BOOLEAN
+EFIAPI
+FindDuplicateValue (
+  IN  CONST VOID          * Array,
+  IN  CONST UINTN           Count,
+  IN  CONST UINTN           ElementSize,
+  IN        PFN_IS_EQUAL    EqualTestFunction
+  );
+
 #endif // TABLE_HELPER_LIB_H_
diff --git a/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c b/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c
index 3938302b6d..fc6cf3b088 100644
--- a/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c
+++ b/DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c
@@ -13,6 +13,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
 // Module specific include files.
 #include <AcpiTableGenerator.h>
 #include <ConfigurationManagerObject.h>
+#include <Library/TableHelperLib.h>
 #include <Protocol/ConfigurationManagerProtocol.h>
 
 /** The GetCgfMgrInfo function gets the CM_STD_OBJ_CONFIGURATION_MANAGER_INFO
@@ -180,3 +181,66 @@ AddAcpiHeader (
 error_handler:
   return Status;
 }
+
+/**
+  Test and report if a duplicate entry exists in the given array of comparable
+  elements.
+
+  @param [in] Array                 Array of elements to test for duplicates.
+  @param [in] Count                 Number of elements in Array.
+  @param [in] ElementSize           Size of an element in bytes
+  @param [in] EqualTestFunction     The function to call to check if any two
+                                    elements are equal.
+
+  @retval TRUE                      A duplicate element was found or one of
+                                    the input arguments is invalid.
+  @retval FALSE                     Every element in Array is unique.
+**/
+BOOLEAN
+EFIAPI
+FindDuplicateValue (
+  IN  CONST VOID          * Array,
+  IN  CONST UINTN           Count,
+  IN  CONST UINTN           ElementSize,
+  IN        PFN_IS_EQUAL    EqualTestFunction
+  )
+{
+  UINTN         Index1;
+  UINTN         Index2;
+  UINT8       * Element1;
+  UINT8       * Element2;
+
+  if (Array == NULL) {
+    DEBUG ((DEBUG_ERROR, "ERROR: FindDuplicateValues: Array is NULL.\n"));
+    return TRUE;
+  }
+
+  if (ElementSize == 0) {
+    DEBUG ((DEBUG_ERROR, "ERROR: FindDuplicateValues: ElementSize is 0.\n"));
+    return TRUE;
+  }
+
+  if (EqualTestFunction == NULL) {
+    DEBUG ((
+      DEBUG_ERROR,
+      "ERROR: FindDuplicateValues: EqualTestFunction is NULL.\n"
+      ));
+    return TRUE;
+  }
+
+  if (Count < 2) {
+    return FALSE;
+  }
+
+  for (Index1 = 0; Index1 < Count - 1; Index1++) {
+    for (Index2 = Index1 + 1; Index2 < Count; Index2++) {
+      Element1 = (UINT8*)Array + (Index1 * ElementSize);
+      Element2 = (UINT8*)Array + (Index2 * ElementSize);
+
+      if (EqualTestFunction (Element1, Element2, Index1, Index2)) {
+        return TRUE;
+      }
+    }
+  }
+  return FALSE;
+}