[edk2-devel] [PATCH v1 1/3] DynamicTablesPkg: Add code for finding duplicate values in arrays

[Krzysztof Koch]

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 at arm.com>
---
Notes:
    v1:
    - Add generic code for duplicate detection [Krzysztof]

 DynamicTablesPkg/Include/Library/TableHelperLib.h            | 48 +++++++++++++++
 DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c | 64 ++++++++++++++++++++
 2 files changed, 112 insertions(+)

diff --git a/DynamicTablesPkg/Include/Library/TableHelperLib.h b/DynamicTablesPkg/Include/Library/TableHelperLib.h
index 9c5b3835413f8768ef81ababa932c9f9be7ced82..e4a8dfa046bd97d89f0297ccad521f317bed5c36 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 3938302b6d770c5bed2bc6c55a51c96ea8316dff..fc6cf3b088da1f7ad89dd4356b414bede9e80575 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;
+}
--
'Guid(CE165669-3EF3-493F-B85D-6190EE5B9759)'



-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.

View/Reply Online (#40779): https://edk2.groups.io/g/devel/message/40779
Mute This Topic: https://groups.io/mt/31639037/1813853
Group Owner: devel+owner at edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub  [edk2-devel-archive at redhat.com]
-=-=-=-=-=-=-=-=-=-=-=-