From: "Krzysztof Koch" <krzysztof.koch@arm.com>
To: <devel@edk2.groups.io>
Cc: <leif.lindholm@linaro.org>, <Sami.Mujawar@arm.com>,
<Alexei.Fedorov@arm.com>, <Matteo.Carlini@arm.com>,
<Stephanie.Hughes-Fitt@arm.com>, <nd@arm.com>
Subject: [PATCH v1 1/3] DynamicTablesPkg: Add code for finding duplicate values in arrays
Date: Thu, 16 May 2019 11:11:31 +0100 [thread overview]
Message-ID: <20190516101133.34912-2-krzysztof.koch@arm.com> (raw)
In-Reply-To: <20190516101133.34912-1-krzysztof.koch@arm.com>
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>
---
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)'
next prev parent reply other threads:[~2019-05-16 10:11 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-05-16 10:11 [PATCH v1 0/3] Detect duplicate field values in ACPI tables Krzysztof Koch
2019-05-16 10:11 ` Krzysztof Koch [this message]
2019-05-16 10:11 ` [PATCH v1 2/3] DynamicTablesPkg: Test for duplicate UIDs in MADT generator Krzysztof Koch
2019-05-16 10:11 ` [PATCH v1 3/3] DynamicTablesPkg: Test for duplicate GT Block frame numbers Krzysztof Koch
2019-06-03 10:56 ` [edk2-devel] [PATCH v1 0/3] Detect duplicate field values in ACPI tables Alexei.Fedorov
2019-06-10 19:46 ` Sami Mujawar
2019-06-10 19:53 ` Sami Mujawar
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190516101133.34912-2-krzysztof.koch@arm.com \
--to=devel@edk2.groups.io \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox