DynamicTablesPkg: Add code for finding duplicate values in arrays
authorKrzysztof Koch <krzysztof.koch@arm.com>
Tue, 9 Apr 2019 09:41:40 +0000 (10:41 +0100)
committerSami Mujawar <sami.mujawar@arm.com>
Mon, 10 Jun 2019 19:44:31 +0000 (20:44 +0100)
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>
DynamicTablesPkg/Include/Library/TableHelperLib.h
DynamicTablesPkg/Library/Common/TableHelperLib/TableHelper.c

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