* [PATCH v7 0/1] Add function QuickSort into MdePkg/BaseLib
@ 2021-10-08 0:27 IanX Kuo
2021-10-08 0:27 ` [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo
0 siblings, 1 reply; 7+ messages in thread
From: IanX Kuo @ 2021-10-08 0:27 UTC (permalink / raw)
To: devel; +Cc: amy.chan, ray.ni, IanX Kuo
From: IanX Kuo <ianx.kuo@intel.com>
First change
1. MdePkg/BaseLib: Add QuickSort function
It need to seperate to second change
2. MdeModulePkg/SortLib: Use QuickSort instead of QuickSortWorker 3. CryptLib/CryptLib: Remove duplicate QuickSortWorker 4. CpuCacheInfoLib: Remove MdeModulePkg dependency
IanX Kuo (1):
MdePkg/BaseLib: Add QuickSort function on BaseLib
MdePkg/Include/Library/BaseLib.h | 49 ++++++++
MdePkg/Library/BaseLib/BaseLib.inf | 1 +
MdePkg/Library/BaseLib/QuickSort.c | 116 ++++++++++++++++++
.../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
4 files changed, 168 insertions(+), 1 deletion(-)
create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
--
2.30.0.windows.1
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
2021-10-08 0:27 [PATCH v7 0/1] Add function QuickSort into MdePkg/BaseLib IanX Kuo
@ 2021-10-08 0:27 ` IanX Kuo
2021-10-08 2:15 ` 回复: [edk2-devel] " gaoliming
0 siblings, 1 reply; 7+ messages in thread
From: IanX Kuo @ 2021-10-08 0:27 UTC (permalink / raw)
To: devel
Cc: amy.chan, ray.ni, IanX Kuo, Michael D Kinney, Liming Gao,
Zhiguang Liu
From: IanX Kuo <ianx.kuo@intel.com>
REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
Add QuickSort function into BaseLib
Cc: Ray Ni <ray.ni@intel.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
MdePkg/Include/Library/BaseLib.h | 49 ++++++++
MdePkg/Library/BaseLib/BaseLib.inf | 1 +
MdePkg/Library/BaseLib/QuickSort.c | 116 ++++++++++++++++++
.../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
4 files changed, 168 insertions(+), 1 deletion(-)
create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/BaseLib.h
index 2452c1d92e..0ae0f4e6af 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -2856,6 +2856,55 @@ RemoveEntryList (
//
// Math Services
//
+/**
+ Prototype for comparison function for any two element types.
+
+ @param[in] Buffer1 The pointer to first buffer.
+ @param[in] Buffer2 The pointer to second buffer.
+
+ @retval 0 Buffer1 equal to Buffer2.
+ @return <0 Buffer1 is less than Buffer2.
+ @return >0 Buffer1 is greater than Buffer2.
+**/
+typedef
+INTN
+(EFIAPI *BASE_SORT_COMPARE)(
+ IN CONST VOID *Buffer1,
+ IN CONST VOID *Buffer2
+ );
+
+/**
+ This function is identical to perform QuickSort,
+ except that is uses the pre-allocated buffer so the in place sorting does not need to
+ allocate and free buffers constantly.
+
+ Each element must be equal sized.
+
+ if BufferToSort is NULL, then ASSERT.
+ if CompareFunction is NULL, then ASSERT.
+ if BufferOneElement is NULL, then ASSERT.
+ if ElementSize is < 1, then ASSERT.
+
+ if Count is < 2 then perform no action.
+
+ @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
+ on return a buffer of sorted elements
+ @param[in] Count the number of elements in the buffer to sort
+ @param[in] ElementSize Size of an element in bytes
+ @param[in] CompareFunction The function to call to perform the comparison
+ of any 2 elements
+ @param[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.
+ It's used by QuickSort() for swapping in sorting.
+**/
+VOID
+EFIAPI
+QuickSort (
+ IN OUT VOID *BufferToSort,
+ IN CONST UINTN Count,
+ IN CONST UINTN ElementSize,
+ IN BASE_SORT_COMPARE CompareFunction,
+ OUT VOID *BufferOneElement
+ );
/**
Shifts a 64-bit integer left between 0 and 63 bits. The low bits are filled
diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/BaseLib.inf
index 6efa5315b6..cebda3b210 100644
--- a/MdePkg/Library/BaseLib/BaseLib.inf
+++ b/MdePkg/Library/BaseLib/BaseLib.inf
@@ -32,6 +32,7 @@
SwapBytes16.c
LongJump.c
SetJump.c
+ QuickSort.c
RShiftU64.c
RRotU64.c
RRotU32.c
diff --git a/MdePkg/Library/BaseLib/QuickSort.c b/MdePkg/Library/BaseLib/QuickSort.c
new file mode 100644
index 0000000000..a825c072b0
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,116 @@
+/** @file
+ Math worker functions.
+
+ Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
+ SPDX-License-Identifier: BSD-2-Clause-Patent
+
+**/
+
+#include "BaseLibInternals.h"
+
+/**
+ This function is identical to perform QuickSort,
+ except that is uses the pre-allocated buffer so the in place sorting does not need to
+ allocate and free buffers constantly.
+
+ Each element must be equal sized.
+
+ if BufferToSort is NULL, then ASSERT.
+ if CompareFunction is NULL, then ASSERT.
+ if BufferOneElement is NULL, then ASSERT.
+ if ElementSize is < 1, then ASSERT.
+
+ if Count is < 2 then perform no action.
+
+ @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
+ on return a buffer of sorted elements
+ @param[in] Count the number of elements in the buffer to sort
+ @param[in] ElementSize Size of an element in bytes
+ @param[in] CompareFunction The function to call to perform the comparison
+ of any 2 elements
+ @param[out] BufferOneElement Caller provided buffer whose size equals to ElementSize.
+ It's used by QuickSort() for swapping in sorting.
+**/
+VOID
+EFIAPI
+QuickSort (
+ IN OUT VOID *BufferToSort,
+ IN CONST UINTN Count,
+ IN CONST UINTN ElementSize,
+ IN BASE_SORT_COMPARE CompareFunction,
+ OUT VOID *BufferOneElement
+ )
+{
+ VOID *Pivot;
+ UINTN LoopCount;
+ UINTN NextSwapLocation;
+
+ ASSERT (BufferToSort != NULL);
+ ASSERT (CompareFunction != NULL);
+ ASSERT (BufferOneElement != NULL);
+ ASSERT (ElementSize >= 1);
+
+ if (Count < 2) {
+ return;
+ }
+
+ NextSwapLocation = 0;
+
+ //
+ // pick a pivot (we choose last element)
+ //
+ Pivot = ((UINT8*) BufferToSort + ((Count - 1) * ElementSize));
+
+ //
+ // Now get the pivot such that all on "left" are below it
+ // and everything "right" are above it
+ //
+ for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {
+ //
+ // if the element is less than or equal to the pivot
+ //
+ if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0){
+ //
+ // swap
+ //
+ CopyMem (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);
+ CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, ElementSize);
+
+ //
+ // increment NextSwapLocation
+ //
+ NextSwapLocation++;
+ }
+ }
+ //
+ // swap pivot to it's final position (NextSwapLocation)
+ //
+ CopyMem (BufferOneElement, Pivot, ElementSize);
+ CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), BufferOneElement, ElementSize);
+
+ //
+ // Now recurse on 2 partial lists. neither of these will have the 'pivot' element
+ // IE list is sorted left half, pivot element, sorted right half...
+ //
+ if (NextSwapLocation >= 2) {
+ QuickSort (
+ BufferToSort,
+ NextSwapLocation,
+ ElementSize,
+ CompareFunction,
+ BufferOneElement
+ );
+ }
+
+ if ((Count - NextSwapLocation - 1) >= 2) {
+ QuickSort (
+ (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
+ Count - NextSwapLocation - 1,
+ ElementSize,
+ CompareFunction,
+ BufferOneElement
+ );
+ }
+}
diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
index eae1a7158d..d09bd12bef 100644
--- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
+++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
@@ -1,7 +1,7 @@
## @file
# Base Library implementation for use with host based unit tests.
#
-# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>
+# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
# Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
# Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
# Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All rights reserved.<BR>
@@ -33,6 +33,7 @@
SwapBytes16.c
LongJump.c
SetJump.c
+ QuickSort.c
RShiftU64.c
RRotU64.c
RRotU32.c
--
2.30.0.windows.1
^ permalink raw reply related [flat|nested] 7+ messages in thread
* 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
2021-10-08 0:27 ` [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo
@ 2021-10-08 2:15 ` gaoliming
2021-10-08 15:46 ` Michael D Kinney
0 siblings, 1 reply; 7+ messages in thread
From: gaoliming @ 2021-10-08 2:15 UTC (permalink / raw)
To: devel, ianx.kuo
Cc: amy.chan, ray.ni, 'Michael D Kinney',
'Zhiguang Liu'
Kuo:
I suggest to move SORT_COMPARE definition from
MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h,
and then let SortLib.h include BaseLib.h.
Thanks
Liming
> -----邮件原件-----
> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo
> 发送时间: 2021年10月8日 8:27
> 收件人: devel@edk2.groups.io
> 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo
> <ianx.kuo@intel.com>; Michael D Kinney <michael.d.kinney@intel.com>;
> Liming Gao <gaoliming@byosoft.com.cn>; Zhiguang Liu
> <zhiguang.liu@intel.com>
> 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function
> on BaseLib
>
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Add QuickSort function into BaseLib
>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Michael D Kinney <michael.d.kinney@intel.com>
> Cc: Liming Gao <gaoliming@byosoft.com.cn>
> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
> MdePkg/Include/Library/BaseLib.h | 49 ++++++++
> MdePkg/Library/BaseLib/BaseLib.inf | 1 +
> MdePkg/Library/BaseLib/QuickSort.c | 116
> ++++++++++++++++++
> .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
> 4 files changed, 168 insertions(+), 1 deletion(-)
> create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
>
> diff --git a/MdePkg/Include/Library/BaseLib.h
> b/MdePkg/Include/Library/BaseLib.h
> index 2452c1d92e..0ae0f4e6af 100644
> --- a/MdePkg/Include/Library/BaseLib.h
> +++ b/MdePkg/Include/Library/BaseLib.h
> @@ -2856,6 +2856,55 @@ RemoveEntryList (
> //
>
> // Math Services
>
> //
>
> +/**
>
> + Prototype for comparison function for any two element types.
>
> +
>
> + @param[in] Buffer1 The pointer to first buffer.
>
> + @param[in] Buffer2 The pointer to second buffer.
>
> +
>
> + @retval 0 Buffer1 equal to Buffer2.
>
> + @return <0 Buffer1 is less than Buffer2.
>
> + @return >0 Buffer1 is greater than
> Buffer2.
>
> +**/
>
> +typedef
>
> +INTN
>
> +(EFIAPI *BASE_SORT_COMPARE)(
>
> + IN CONST VOID *Buffer1,
>
> + IN CONST VOID *Buffer2
>
> + );
>
> +
>
> +/**
>
> + This function is identical to perform QuickSort,
>
> + except that is uses the pre-allocated buffer so the in place sorting
does not
> need to
>
> + allocate and free buffers constantly.
>
> +
>
> + Each element must be equal sized.
>
> +
>
> + if BufferToSort is NULL, then ASSERT.
>
> + if CompareFunction is NULL, then ASSERT.
>
> + if BufferOneElement is NULL, then ASSERT.
>
> + if ElementSize is < 1, then ASSERT.
>
> +
>
> + if Count is < 2 then perform no action.
>
> +
>
> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
> elements
>
> + on return a buffer of sorted
> elements
>
> + @param[in] Count the number of elements in the
> buffer to sort
>
> + @param[in] ElementSize Size of an element in bytes
>
> + @param[in] CompareFunction The function to call to perform the
> comparison
>
> + of any 2 elements
>
> + @param[out] BufferOneElement Caller provided buffer whose size
> equals to ElementSize.
>
> + It's used by QuickSort() for
> swapping in sorting.
>
> +**/
>
> +VOID
>
> +EFIAPI
>
> +QuickSort (
>
> + IN OUT VOID *BufferToSort,
>
> + IN CONST UINTN Count,
>
> + IN CONST UINTN ElementSize,
>
> + IN BASE_SORT_COMPARE CompareFunction,
>
> + OUT VOID *BufferOneElement
>
> + );
>
>
>
> /**
>
> Shifts a 64-bit integer left between 0 and 63 bits. The low bits are
filled
>
> diff --git a/MdePkg/Library/BaseLib/BaseLib.inf
> b/MdePkg/Library/BaseLib/BaseLib.inf
> index 6efa5315b6..cebda3b210 100644
> --- a/MdePkg/Library/BaseLib/BaseLib.inf
> +++ b/MdePkg/Library/BaseLib/BaseLib.inf
> @@ -32,6 +32,7 @@
> SwapBytes16.c
>
> LongJump.c
>
> SetJump.c
>
> + QuickSort.c
>
> RShiftU64.c
>
> RRotU64.c
>
> RRotU32.c
>
> diff --git a/MdePkg/Library/BaseLib/QuickSort.c
> b/MdePkg/Library/BaseLib/QuickSort.c
> new file mode 100644
> index 0000000000..a825c072b0
> --- /dev/null
> +++ b/MdePkg/Library/BaseLib/QuickSort.c
> @@ -0,0 +1,116 @@
> +/** @file
>
> + Math worker functions.
>
> +
>
> + Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
>
> + SPDX-License-Identifier: BSD-2-Clause-Patent
>
> +
>
> +**/
>
> +
>
> +#include "BaseLibInternals.h"
>
> +
>
> +/**
>
> + This function is identical to perform QuickSort,
>
> + except that is uses the pre-allocated buffer so the in place sorting
does not
> need to
>
> + allocate and free buffers constantly.
>
> +
>
> + Each element must be equal sized.
>
> +
>
> + if BufferToSort is NULL, then ASSERT.
>
> + if CompareFunction is NULL, then ASSERT.
>
> + if BufferOneElement is NULL, then ASSERT.
>
> + if ElementSize is < 1, then ASSERT.
>
> +
>
> + if Count is < 2 then perform no action.
>
> +
>
> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
> elements
>
> + on return a buffer of sorted
> elements
>
> + @param[in] Count the number of elements in the
> buffer to sort
>
> + @param[in] ElementSize Size of an element in bytes
>
> + @param[in] CompareFunction The function to call to perform the
> comparison
>
> + of any 2 elements
>
> + @param[out] BufferOneElement Caller provided buffer whose size
> equals to ElementSize.
>
> + It's used by QuickSort() for
> swapping in sorting.
>
> +**/
>
> +VOID
>
> +EFIAPI
>
> +QuickSort (
>
> + IN OUT VOID *BufferToSort,
>
> + IN CONST UINTN Count,
>
> + IN CONST UINTN ElementSize,
>
> + IN BASE_SORT_COMPARE CompareFunction,
>
> + OUT VOID *BufferOneElement
>
> + )
>
> +{
>
> + VOID *Pivot;
>
> + UINTN LoopCount;
>
> + UINTN NextSwapLocation;
>
> +
>
> + ASSERT (BufferToSort != NULL);
>
> + ASSERT (CompareFunction != NULL);
>
> + ASSERT (BufferOneElement != NULL);
>
> + ASSERT (ElementSize >= 1);
>
> +
>
> + if (Count < 2) {
>
> + return;
>
> + }
>
> +
>
> + NextSwapLocation = 0;
>
> +
>
> + //
>
> + // pick a pivot (we choose last element)
>
> + //
>
> + Pivot = ((UINT8*) BufferToSort + ((Count - 1) * ElementSize));
>
> +
>
> + //
>
> + // Now get the pivot such that all on "left" are below it
>
> + // and everything "right" are above it
>
> + //
>
> + for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {
>
> + //
>
> + // if the element is less than or equal to the pivot
>
> + //
>
> + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) *
> ElementSize)), Pivot) <= 0){
>
> + //
>
> + // swap
>
> + //
>
> + CopyMem (BufferOneElement, (UINT8*) BufferToSort +
> (NextSwapLocation * ElementSize), ElementSize);
>
> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation *
> ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize),
> ElementSize);
>
> + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize),
> BufferOneElement, ElementSize);
>
> +
>
> + //
>
> + // increment NextSwapLocation
>
> + //
>
> + NextSwapLocation++;
>
> + }
>
> + }
>
> + //
>
> + // swap pivot to it's final position (NextSwapLocation)
>
> + //
>
> + CopyMem (BufferOneElement, Pivot, ElementSize);
>
> + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation *
> ElementSize), ElementSize);
>
> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize),
> BufferOneElement, ElementSize);
>
> +
>
> + //
>
> + // Now recurse on 2 partial lists. neither of these will have the
'pivot'
> element
>
> + // IE list is sorted left half, pivot element, sorted right half...
>
> + //
>
> + if (NextSwapLocation >= 2) {
>
> + QuickSort (
>
> + BufferToSort,
>
> + NextSwapLocation,
>
> + ElementSize,
>
> + CompareFunction,
>
> + BufferOneElement
>
> + );
>
> + }
>
> +
>
> + if ((Count - NextSwapLocation - 1) >= 2) {
>
> + QuickSort (
>
> + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
>
> + Count - NextSwapLocation - 1,
>
> + ElementSize,
>
> + CompareFunction,
>
> + BufferOneElement
>
> + );
>
> + }
>
> +}
>
> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> index eae1a7158d..d09bd12bef 100644
> --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> @@ -1,7 +1,7 @@
> ## @file
>
> # Base Library implementation for use with host based unit tests.
>
> #
>
> -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>
>
> +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
>
> # Portions copyright (c) 2008 - 2009, Apple Inc. All rights
reserved.<BR>
>
> # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
>
> # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All
> rights reserved.<BR>
>
> @@ -33,6 +33,7 @@
> SwapBytes16.c
>
> LongJump.c
>
> SetJump.c
>
> + QuickSort.c
>
> RShiftU64.c
>
> RRotU64.c
>
> RRotU32.c
>
> --
> 2.30.0.windows.1
>
>
>
> -=-=-=-=-=-=
> Groups.io Links: You receive all messages sent to this group.
> View/Reply Online (#81615): https://edk2.groups.io/g/devel/message/81615
> Mute This Topic: https://groups.io/mt/86159728/4905953
> Group Owner: devel+owner@edk2.groups.io
> Unsubscribe: https://edk2.groups.io/g/devel/unsub
> [gaoliming@byosoft.com.cn]
> -=-=-=-=-=-=
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
2021-10-08 2:15 ` 回复: [edk2-devel] " gaoliming
@ 2021-10-08 15:46 ` Michael D Kinney
2021-10-08 16:09 ` Marvin Häuser
0 siblings, 1 reply; 7+ messages in thread
From: Michael D Kinney @ 2021-10-08 15:46 UTC (permalink / raw)
To: devel@edk2.groups.io, gaoliming@byosoft.com.cn, Kuo, IanX,
Kinney, Michael D
Cc: Chan, Amy, Ni, Ray, Liu, Zhiguang
Hi Liming,
In general it is not a good idea to include a library include file from another library include file.
This becomes a hidden dependency.
Mike
> -----Original Message-----
> From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming
> Sent: Thursday, October 7, 2021 7:16 PM
> To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>
> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kinney, Michael D <michael.d.kinney@intel.com>; Liu,
> Zhiguang <zhiguang.liu@intel.com>
> Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
>
> Kuo:
> I suggest to move SORT_COMPARE definition from
> MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h,
> and then let SortLib.h include BaseLib.h.
>
> Thanks
> Liming
> > -----邮件原件-----
> > 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo
> > 发送时间: 2021年10月8日 8:27
> > 收件人: devel@edk2.groups.io
> > 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo
> > <ianx.kuo@intel.com>; Michael D Kinney <michael.d.kinney@intel.com>;
> > Liming Gao <gaoliming@byosoft.com.cn>; Zhiguang Liu
> > <zhiguang.liu@intel.com>
> > 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function
> > on BaseLib
> >
> > From: IanX Kuo <ianx.kuo@intel.com>
> >
> > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
> >
> > Add QuickSort function into BaseLib
> >
> > Cc: Ray Ni <ray.ni@intel.com>
> > Cc: Michael D Kinney <michael.d.kinney@intel.com>
> > Cc: Liming Gao <gaoliming@byosoft.com.cn>
> > Cc: Zhiguang Liu <zhiguang.liu@intel.com>
> > Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> > ---
> > MdePkg/Include/Library/BaseLib.h | 49 ++++++++
> > MdePkg/Library/BaseLib/BaseLib.inf | 1 +
> > MdePkg/Library/BaseLib/QuickSort.c | 116
> > ++++++++++++++++++
> > .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
> > 4 files changed, 168 insertions(+), 1 deletion(-)
> > create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
> >
> > diff --git a/MdePkg/Include/Library/BaseLib.h
> > b/MdePkg/Include/Library/BaseLib.h
> > index 2452c1d92e..0ae0f4e6af 100644
> > --- a/MdePkg/Include/Library/BaseLib.h
> > +++ b/MdePkg/Include/Library/BaseLib.h
> > @@ -2856,6 +2856,55 @@ RemoveEntryList (
> > //
> >
> > // Math Services
> >
> > //
> >
> > +/**
> >
> > + Prototype for comparison function for any two element types.
> >
> > +
> >
> > + @param[in] Buffer1 The pointer to first buffer.
> >
> > + @param[in] Buffer2 The pointer to second buffer.
> >
> > +
> >
> > + @retval 0 Buffer1 equal to Buffer2.
> >
> > + @return <0 Buffer1 is less than Buffer2.
> >
> > + @return >0 Buffer1 is greater than
> > Buffer2.
> >
> > +**/
> >
> > +typedef
> >
> > +INTN
> >
> > +(EFIAPI *BASE_SORT_COMPARE)(
> >
> > + IN CONST VOID *Buffer1,
> >
> > + IN CONST VOID *Buffer2
> >
> > + );
> >
> > +
> >
> > +/**
> >
> > + This function is identical to perform QuickSort,
> >
> > + except that is uses the pre-allocated buffer so the in place sorting
> does not
> > need to
> >
> > + allocate and free buffers constantly.
> >
> > +
> >
> > + Each element must be equal sized.
> >
> > +
> >
> > + if BufferToSort is NULL, then ASSERT.
> >
> > + if CompareFunction is NULL, then ASSERT.
> >
> > + if BufferOneElement is NULL, then ASSERT.
> >
> > + if ElementSize is < 1, then ASSERT.
> >
> > +
> >
> > + if Count is < 2 then perform no action.
> >
> > +
> >
> > + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
> > elements
> >
> > + on return a buffer of sorted
> > elements
> >
> > + @param[in] Count the number of elements in the
> > buffer to sort
> >
> > + @param[in] ElementSize Size of an element in bytes
> >
> > + @param[in] CompareFunction The function to call to perform the
> > comparison
> >
> > + of any 2 elements
> >
> > + @param[out] BufferOneElement Caller provided buffer whose size
> > equals to ElementSize.
> >
> > + It's used by QuickSort() for
> > swapping in sorting.
> >
> > +**/
> >
> > +VOID
> >
> > +EFIAPI
> >
> > +QuickSort (
> >
> > + IN OUT VOID *BufferToSort,
> >
> > + IN CONST UINTN Count,
> >
> > + IN CONST UINTN ElementSize,
> >
> > + IN BASE_SORT_COMPARE CompareFunction,
> >
> > + OUT VOID *BufferOneElement
> >
> > + );
> >
> >
> >
> > /**
> >
> > Shifts a 64-bit integer left between 0 and 63 bits. The low bits are
> filled
> >
> > diff --git a/MdePkg/Library/BaseLib/BaseLib.inf
> > b/MdePkg/Library/BaseLib/BaseLib.inf
> > index 6efa5315b6..cebda3b210 100644
> > --- a/MdePkg/Library/BaseLib/BaseLib.inf
> > +++ b/MdePkg/Library/BaseLib/BaseLib.inf
> > @@ -32,6 +32,7 @@
> > SwapBytes16.c
> >
> > LongJump.c
> >
> > SetJump.c
> >
> > + QuickSort.c
> >
> > RShiftU64.c
> >
> > RRotU64.c
> >
> > RRotU32.c
> >
> > diff --git a/MdePkg/Library/BaseLib/QuickSort.c
> > b/MdePkg/Library/BaseLib/QuickSort.c
> > new file mode 100644
> > index 0000000000..a825c072b0
> > --- /dev/null
> > +++ b/MdePkg/Library/BaseLib/QuickSort.c
> > @@ -0,0 +1,116 @@
> > +/** @file
> >
> > + Math worker functions.
> >
> > +
> >
> > + Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
> >
> > + SPDX-License-Identifier: BSD-2-Clause-Patent
> >
> > +
> >
> > +**/
> >
> > +
> >
> > +#include "BaseLibInternals.h"
> >
> > +
> >
> > +/**
> >
> > + This function is identical to perform QuickSort,
> >
> > + except that is uses the pre-allocated buffer so the in place sorting
> does not
> > need to
> >
> > + allocate and free buffers constantly.
> >
> > +
> >
> > + Each element must be equal sized.
> >
> > +
> >
> > + if BufferToSort is NULL, then ASSERT.
> >
> > + if CompareFunction is NULL, then ASSERT.
> >
> > + if BufferOneElement is NULL, then ASSERT.
> >
> > + if ElementSize is < 1, then ASSERT.
> >
> > +
> >
> > + if Count is < 2 then perform no action.
> >
> > +
> >
> > + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
> > elements
> >
> > + on return a buffer of sorted
> > elements
> >
> > + @param[in] Count the number of elements in the
> > buffer to sort
> >
> > + @param[in] ElementSize Size of an element in bytes
> >
> > + @param[in] CompareFunction The function to call to perform the
> > comparison
> >
> > + of any 2 elements
> >
> > + @param[out] BufferOneElement Caller provided buffer whose size
> > equals to ElementSize.
> >
> > + It's used by QuickSort() for
> > swapping in sorting.
> >
> > +**/
> >
> > +VOID
> >
> > +EFIAPI
> >
> > +QuickSort (
> >
> > + IN OUT VOID *BufferToSort,
> >
> > + IN CONST UINTN Count,
> >
> > + IN CONST UINTN ElementSize,
> >
> > + IN BASE_SORT_COMPARE CompareFunction,
> >
> > + OUT VOID *BufferOneElement
> >
> > + )
> >
> > +{
> >
> > + VOID *Pivot;
> >
> > + UINTN LoopCount;
> >
> > + UINTN NextSwapLocation;
> >
> > +
> >
> > + ASSERT (BufferToSort != NULL);
> >
> > + ASSERT (CompareFunction != NULL);
> >
> > + ASSERT (BufferOneElement != NULL);
> >
> > + ASSERT (ElementSize >= 1);
> >
> > +
> >
> > + if (Count < 2) {
> >
> > + return;
> >
> > + }
> >
> > +
> >
> > + NextSwapLocation = 0;
> >
> > +
> >
> > + //
> >
> > + // pick a pivot (we choose last element)
> >
> > + //
> >
> > + Pivot = ((UINT8*) BufferToSort + ((Count - 1) * ElementSize));
> >
> > +
> >
> > + //
> >
> > + // Now get the pivot such that all on "left" are below it
> >
> > + // and everything "right" are above it
> >
> > + //
> >
> > + for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {
> >
> > + //
> >
> > + // if the element is less than or equal to the pivot
> >
> > + //
> >
> > + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) *
> > ElementSize)), Pivot) <= 0){
> >
> > + //
> >
> > + // swap
> >
> > + //
> >
> > + CopyMem (BufferOneElement, (UINT8*) BufferToSort +
> > (NextSwapLocation * ElementSize), ElementSize);
> >
> > + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation *
> > ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize),
> > ElementSize);
> >
> > + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize),
> > BufferOneElement, ElementSize);
> >
> > +
> >
> > + //
> >
> > + // increment NextSwapLocation
> >
> > + //
> >
> > + NextSwapLocation++;
> >
> > + }
> >
> > + }
> >
> > + //
> >
> > + // swap pivot to it's final position (NextSwapLocation)
> >
> > + //
> >
> > + CopyMem (BufferOneElement, Pivot, ElementSize);
> >
> > + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation *
> > ElementSize), ElementSize);
> >
> > + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize),
> > BufferOneElement, ElementSize);
> >
> > +
> >
> > + //
> >
> > + // Now recurse on 2 partial lists. neither of these will have the
> 'pivot'
> > element
> >
> > + // IE list is sorted left half, pivot element, sorted right half...
> >
> > + //
> >
> > + if (NextSwapLocation >= 2) {
> >
> > + QuickSort (
> >
> > + BufferToSort,
> >
> > + NextSwapLocation,
> >
> > + ElementSize,
> >
> > + CompareFunction,
> >
> > + BufferOneElement
> >
> > + );
> >
> > + }
> >
> > +
> >
> > + if ((Count - NextSwapLocation - 1) >= 2) {
> >
> > + QuickSort (
> >
> > + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
> >
> > + Count - NextSwapLocation - 1,
> >
> > + ElementSize,
> >
> > + CompareFunction,
> >
> > + BufferOneElement
> >
> > + );
> >
> > + }
> >
> > +}
> >
> > diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> > b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> > index eae1a7158d..d09bd12bef 100644
> > --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> > +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> > @@ -1,7 +1,7 @@
> > ## @file
> >
> > # Base Library implementation for use with host based unit tests.
> >
> > #
> >
> > -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>
> >
> > +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
> >
> > # Portions copyright (c) 2008 - 2009, Apple Inc. All rights
> reserved.<BR>
> >
> > # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
> >
> > # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All
> > rights reserved.<BR>
> >
> > @@ -33,6 +33,7 @@
> > SwapBytes16.c
> >
> > LongJump.c
> >
> > SetJump.c
> >
> > + QuickSort.c
> >
> > RShiftU64.c
> >
> > RRotU64.c
> >
> > RRotU32.c
> >
> > --
> > 2.30.0.windows.1
> >
> >
> >
> > -=-=-=-=-=-=
> > Groups.io Links: You receive all messages sent to this group.
> > View/Reply Online (#81615): https://edk2.groups.io/g/devel/message/81615
> > Mute This Topic: https://groups.io/mt/86159728/4905953
> > Group Owner: devel+owner@edk2.groups.io
> > Unsubscribe: https://edk2.groups.io/g/devel/unsub
> > [gaoliming@byosoft.com.cn]
> > -=-=-=-=-=-=
> >
>
>
>
>
>
>
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
2021-10-08 15:46 ` Michael D Kinney
@ 2021-10-08 16:09 ` Marvin Häuser
2021-10-11 1:21 ` 回复: " gaoliming
0 siblings, 1 reply; 7+ messages in thread
From: Marvin Häuser @ 2021-10-08 16:09 UTC (permalink / raw)
To: devel, michael.d.kinney, gaoliming@byosoft.com.cn, Kuo, IanX
Cc: Chan, Amy, Ni, Ray, Liu, Zhiguang
Hey all,
I also don't think it makes much logical sense. They are distinct APIs
in separate libraries that happen to take a function with the same
prototype.
I think the patches look good now, thanks!
Best regards,
Marvin
On 08/10/2021 17:46, Michael D Kinney wrote:
> Hi Liming,
>
> In general it is not a good idea to include a library include file from another library include file.
>
> This becomes a hidden dependency.
>
> Mike
>
>> -----Original Message-----
>> From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming
>> Sent: Thursday, October 7, 2021 7:16 PM
>> To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>
>> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kinney, Michael D <michael.d.kinney@intel.com>; Liu,
>> Zhiguang <zhiguang.liu@intel.com>
>> Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
>>
>> Kuo:
>> I suggest to move SORT_COMPARE definition from
>> MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h,
>> and then let SortLib.h include BaseLib.h.
>>
>> Thanks
>> Liming
>>> -----邮件原件-----
>>> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo
>>> 发送时间: 2021年10月8日 8:27
>>> 收件人: devel@edk2.groups.io
>>> 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo
>>> <ianx.kuo@intel.com>; Michael D Kinney <michael.d.kinney@intel.com>;
>>> Liming Gao <gaoliming@byosoft.com.cn>; Zhiguang Liu
>>> <zhiguang.liu@intel.com>
>>> 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function
>>> on BaseLib
>>>
>>> From: IanX Kuo <ianx.kuo@intel.com>
>>>
>>> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>>>
>>> Add QuickSort function into BaseLib
>>>
>>> Cc: Ray Ni <ray.ni@intel.com>
>>> Cc: Michael D Kinney <michael.d.kinney@intel.com>
>>> Cc: Liming Gao <gaoliming@byosoft.com.cn>
>>> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
>>> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
>>> ---
>>> MdePkg/Include/Library/BaseLib.h | 49 ++++++++
>>> MdePkg/Library/BaseLib/BaseLib.inf | 1 +
>>> MdePkg/Library/BaseLib/QuickSort.c | 116
>>> ++++++++++++++++++
>>> .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
>>> 4 files changed, 168 insertions(+), 1 deletion(-)
>>> create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
>>>
>>> diff --git a/MdePkg/Include/Library/BaseLib.h
>>> b/MdePkg/Include/Library/BaseLib.h
>>> index 2452c1d92e..0ae0f4e6af 100644
>>> --- a/MdePkg/Include/Library/BaseLib.h
>>> +++ b/MdePkg/Include/Library/BaseLib.h
>>> @@ -2856,6 +2856,55 @@ RemoveEntryList (
>>> //
>>>
>>> // Math Services
>>>
>>> //
>>>
>>> +/**
>>>
>>> + Prototype for comparison function for any two element types.
>>>
>>> +
>>>
>>> + @param[in] Buffer1 The pointer to first buffer.
>>>
>>> + @param[in] Buffer2 The pointer to second buffer.
>>>
>>> +
>>>
>>> + @retval 0 Buffer1 equal to Buffer2.
>>>
>>> + @return <0 Buffer1 is less than Buffer2.
>>>
>>> + @return >0 Buffer1 is greater than
>>> Buffer2.
>>>
>>> +**/
>>>
>>> +typedef
>>>
>>> +INTN
>>>
>>> +(EFIAPI *BASE_SORT_COMPARE)(
>>>
>>> + IN CONST VOID *Buffer1,
>>>
>>> + IN CONST VOID *Buffer2
>>>
>>> + );
>>>
>>> +
>>>
>>> +/**
>>>
>>> + This function is identical to perform QuickSort,
>>>
>>> + except that is uses the pre-allocated buffer so the in place sorting
>> does not
>>> need to
>>>
>>> + allocate and free buffers constantly.
>>>
>>> +
>>>
>>> + Each element must be equal sized.
>>>
>>> +
>>>
>>> + if BufferToSort is NULL, then ASSERT.
>>>
>>> + if CompareFunction is NULL, then ASSERT.
>>>
>>> + if BufferOneElement is NULL, then ASSERT.
>>>
>>> + if ElementSize is < 1, then ASSERT.
>>>
>>> +
>>>
>>> + if Count is < 2 then perform no action.
>>>
>>> +
>>>
>>> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
>>> elements
>>>
>>> + on return a buffer of sorted
>>> elements
>>>
>>> + @param[in] Count the number of elements in the
>>> buffer to sort
>>>
>>> + @param[in] ElementSize Size of an element in bytes
>>>
>>> + @param[in] CompareFunction The function to call to perform the
>>> comparison
>>>
>>> + of any 2 elements
>>>
>>> + @param[out] BufferOneElement Caller provided buffer whose size
>>> equals to ElementSize.
>>>
>>> + It's used by QuickSort() for
>>> swapping in sorting.
>>>
>>> +**/
>>>
>>> +VOID
>>>
>>> +EFIAPI
>>>
>>> +QuickSort (
>>>
>>> + IN OUT VOID *BufferToSort,
>>>
>>> + IN CONST UINTN Count,
>>>
>>> + IN CONST UINTN ElementSize,
>>>
>>> + IN BASE_SORT_COMPARE CompareFunction,
>>>
>>> + OUT VOID *BufferOneElement
>>>
>>> + );
>>>
>>>
>>>
>>> /**
>>>
>>> Shifts a 64-bit integer left between 0 and 63 bits. The low bits are
>> filled
>>> diff --git a/MdePkg/Library/BaseLib/BaseLib.inf
>>> b/MdePkg/Library/BaseLib/BaseLib.inf
>>> index 6efa5315b6..cebda3b210 100644
>>> --- a/MdePkg/Library/BaseLib/BaseLib.inf
>>> +++ b/MdePkg/Library/BaseLib/BaseLib.inf
>>> @@ -32,6 +32,7 @@
>>> SwapBytes16.c
>>>
>>> LongJump.c
>>>
>>> SetJump.c
>>>
>>> + QuickSort.c
>>>
>>> RShiftU64.c
>>>
>>> RRotU64.c
>>>
>>> RRotU32.c
>>>
>>> diff --git a/MdePkg/Library/BaseLib/QuickSort.c
>>> b/MdePkg/Library/BaseLib/QuickSort.c
>>> new file mode 100644
>>> index 0000000000..a825c072b0
>>> --- /dev/null
>>> +++ b/MdePkg/Library/BaseLib/QuickSort.c
>>> @@ -0,0 +1,116 @@
>>> +/** @file
>>>
>>> + Math worker functions.
>>>
>>> +
>>>
>>> + Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
>>>
>>> + SPDX-License-Identifier: BSD-2-Clause-Patent
>>>
>>> +
>>>
>>> +**/
>>>
>>> +
>>>
>>> +#include "BaseLibInternals.h"
>>>
>>> +
>>>
>>> +/**
>>>
>>> + This function is identical to perform QuickSort,
>>>
>>> + except that is uses the pre-allocated buffer so the in place sorting
>> does not
>>> need to
>>>
>>> + allocate and free buffers constantly.
>>>
>>> +
>>>
>>> + Each element must be equal sized.
>>>
>>> +
>>>
>>> + if BufferToSort is NULL, then ASSERT.
>>>
>>> + if CompareFunction is NULL, then ASSERT.
>>>
>>> + if BufferOneElement is NULL, then ASSERT.
>>>
>>> + if ElementSize is < 1, then ASSERT.
>>>
>>> +
>>>
>>> + if Count is < 2 then perform no action.
>>>
>>> +
>>>
>>> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
>>> elements
>>>
>>> + on return a buffer of sorted
>>> elements
>>>
>>> + @param[in] Count the number of elements in the
>>> buffer to sort
>>>
>>> + @param[in] ElementSize Size of an element in bytes
>>>
>>> + @param[in] CompareFunction The function to call to perform the
>>> comparison
>>>
>>> + of any 2 elements
>>>
>>> + @param[out] BufferOneElement Caller provided buffer whose size
>>> equals to ElementSize.
>>>
>>> + It's used by QuickSort() for
>>> swapping in sorting.
>>>
>>> +**/
>>>
>>> +VOID
>>>
>>> +EFIAPI
>>>
>>> +QuickSort (
>>>
>>> + IN OUT VOID *BufferToSort,
>>>
>>> + IN CONST UINTN Count,
>>>
>>> + IN CONST UINTN ElementSize,
>>>
>>> + IN BASE_SORT_COMPARE CompareFunction,
>>>
>>> + OUT VOID *BufferOneElement
>>>
>>> + )
>>>
>>> +{
>>>
>>> + VOID *Pivot;
>>>
>>> + UINTN LoopCount;
>>>
>>> + UINTN NextSwapLocation;
>>>
>>> +
>>>
>>> + ASSERT (BufferToSort != NULL);
>>>
>>> + ASSERT (CompareFunction != NULL);
>>>
>>> + ASSERT (BufferOneElement != NULL);
>>>
>>> + ASSERT (ElementSize >= 1);
>>>
>>> +
>>>
>>> + if (Count < 2) {
>>>
>>> + return;
>>>
>>> + }
>>>
>>> +
>>>
>>> + NextSwapLocation = 0;
>>>
>>> +
>>>
>>> + //
>>>
>>> + // pick a pivot (we choose last element)
>>>
>>> + //
>>>
>>> + Pivot = ((UINT8*) BufferToSort + ((Count - 1) * ElementSize));
>>>
>>> +
>>>
>>> + //
>>>
>>> + // Now get the pivot such that all on "left" are below it
>>>
>>> + // and everything "right" are above it
>>>
>>> + //
>>>
>>> + for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {
>>>
>>> + //
>>>
>>> + // if the element is less than or equal to the pivot
>>>
>>> + //
>>>
>>> + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) *
>>> ElementSize)), Pivot) <= 0){
>>>
>>> + //
>>>
>>> + // swap
>>>
>>> + //
>>>
>>> + CopyMem (BufferOneElement, (UINT8*) BufferToSort +
>>> (NextSwapLocation * ElementSize), ElementSize);
>>>
>>> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation *
>>> ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize),
>>> ElementSize);
>>>
>>> + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize),
>>> BufferOneElement, ElementSize);
>>>
>>> +
>>>
>>> + //
>>>
>>> + // increment NextSwapLocation
>>>
>>> + //
>>>
>>> + NextSwapLocation++;
>>>
>>> + }
>>>
>>> + }
>>>
>>> + //
>>>
>>> + // swap pivot to it's final position (NextSwapLocation)
>>>
>>> + //
>>>
>>> + CopyMem (BufferOneElement, Pivot, ElementSize);
>>>
>>> + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation *
>>> ElementSize), ElementSize);
>>>
>>> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize),
>>> BufferOneElement, ElementSize);
>>>
>>> +
>>>
>>> + //
>>>
>>> + // Now recurse on 2 partial lists. neither of these will have the
>> 'pivot'
>>> element
>>>
>>> + // IE list is sorted left half, pivot element, sorted right half...
>>>
>>> + //
>>>
>>> + if (NextSwapLocation >= 2) {
>>>
>>> + QuickSort (
>>>
>>> + BufferToSort,
>>>
>>> + NextSwapLocation,
>>>
>>> + ElementSize,
>>>
>>> + CompareFunction,
>>>
>>> + BufferOneElement
>>>
>>> + );
>>>
>>> + }
>>>
>>> +
>>>
>>> + if ((Count - NextSwapLocation - 1) >= 2) {
>>>
>>> + QuickSort (
>>>
>>> + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
>>>
>>> + Count - NextSwapLocation - 1,
>>>
>>> + ElementSize,
>>>
>>> + CompareFunction,
>>>
>>> + BufferOneElement
>>>
>>> + );
>>>
>>> + }
>>>
>>> +}
>>>
>>> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
>>> b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
>>> index eae1a7158d..d09bd12bef 100644
>>> --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
>>> +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
>>> @@ -1,7 +1,7 @@
>>> ## @file
>>>
>>> # Base Library implementation for use with host based unit tests.
>>>
>>> #
>>>
>>> -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>
>>>
>>> +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
>>>
>>> # Portions copyright (c) 2008 - 2009, Apple Inc. All rights
>> reserved.<BR>
>>> # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
>>>
>>> # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All
>>> rights reserved.<BR>
>>>
>>> @@ -33,6 +33,7 @@
>>> SwapBytes16.c
>>>
>>> LongJump.c
>>>
>>> SetJump.c
>>>
>>> + QuickSort.c
>>>
>>> RShiftU64.c
>>>
>>> RRotU64.c
>>>
>>> RRotU32.c
>>>
>>> --
>>> 2.30.0.windows.1
>>>
>>>
>>>
>>> -=-=-=-=-=-=
>>> Groups.io Links: You receive all messages sent to this group.
>>> View/Reply Online (#81615): https://edk2.groups.io/g/devel/message/81615
>>> Mute This Topic: https://groups.io/mt/86159728/4905953
>>> Group Owner: devel+owner@edk2.groups.io
>>> Unsubscribe: https://edk2.groups.io/g/devel/unsub
>>> [gaoliming@byosoft.com.cn]
>>> -=-=-=-=-=-=
>>>
>>
>>
>>
>>
>>
>>
>
>
>
>
>
^ permalink raw reply [flat|nested] 7+ messages in thread
* 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
2021-10-08 16:09 ` Marvin Häuser
@ 2021-10-11 1:21 ` gaoliming
2021-10-12 0:09 ` IanX Kuo
0 siblings, 1 reply; 7+ messages in thread
From: gaoliming @ 2021-10-11 1:21 UTC (permalink / raw)
To: 'Marvin Häuser', devel, michael.d.kinney,
'Kuo, IanX'
Cc: 'Chan, Amy', 'Ni, Ray', 'Liu, Zhiguang'
Michael and Marvin:
I understand your concern. I want to reduce the duplicated definition for the same function. I will not keep my idea if you are both OK to define BASE_SORT_COMPARE and SORT_COMPARE.
Thanks
Liming
> -----邮件原件-----
> 发件人: Marvin Häuser <mhaeuser@posteo.de>
> 发送时间: 2021年10月9日 0:09
> 收件人: devel@edk2.groups.io; michael.d.kinney@intel.com;
> gaoliming@byosoft.com.cn; Kuo, IanX <ianx.kuo@intel.com>
> 抄送: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Liu,
> Zhiguang <zhiguang.liu@intel.com>
> 主题: Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort
> function on BaseLib
>
> Hey all,
>
> I also don't think it makes much logical sense. They are distinct APIs
> in separate libraries that happen to take a function with the same
> prototype.
>
> I think the patches look good now, thanks!
>
> Best regards,
> Marvin
>
> On 08/10/2021 17:46, Michael D Kinney wrote:
> > Hi Liming,
> >
> > In general it is not a good idea to include a library include file from another
> library include file.
> >
> > This becomes a hidden dependency.
> >
> > Mike
> >
> >> -----Original Message-----
> >> From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of
> gaoliming
> >> Sent: Thursday, October 7, 2021 7:16 PM
> >> To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>
> >> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kinney,
> Michael D <michael.d.kinney@intel.com>; Liu,
> >> Zhiguang <zhiguang.liu@intel.com>
> >> Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add
> QuickSort function on BaseLib
> >>
> >> Kuo:
> >> I suggest to move SORT_COMPARE definition from
> >> MdeModulePkg\Include\Library\SortLib.h to
> MdePkg\Include\Library\BaseLib.h,
> >> and then let SortLib.h include BaseLib.h.
> >>
> >> Thanks
> >> Liming
> >>> -----邮件原件-----
> >>> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo
> >>> 发送时间: 2021年10月8日 8:27
> >>> 收件人: devel@edk2.groups.io
> >>> 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo
> >>> <ianx.kuo@intel.com>; Michael D Kinney <michael.d.kinney@intel.com>;
> >>> Liming Gao <gaoliming@byosoft.com.cn>; Zhiguang Liu
> >>> <zhiguang.liu@intel.com>
> >>> 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort
> function
> >>> on BaseLib
> >>>
> >>> From: IanX Kuo <ianx.kuo@intel.com>
> >>>
> >>> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
> >>>
> >>> Add QuickSort function into BaseLib
> >>>
> >>> Cc: Ray Ni <ray.ni@intel.com>
> >>> Cc: Michael D Kinney <michael.d.kinney@intel.com>
> >>> Cc: Liming Gao <gaoliming@byosoft.com.cn>
> >>> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
> >>> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> >>> ---
> >>> MdePkg/Include/Library/BaseLib.h | 49 ++++++++
> >>> MdePkg/Library/BaseLib/BaseLib.inf | 1 +
> >>> MdePkg/Library/BaseLib/QuickSort.c | 116
> >>> ++++++++++++++++++
> >>> .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
> >>> 4 files changed, 168 insertions(+), 1 deletion(-)
> >>> create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
> >>>
> >>> diff --git a/MdePkg/Include/Library/BaseLib.h
> >>> b/MdePkg/Include/Library/BaseLib.h
> >>> index 2452c1d92e..0ae0f4e6af 100644
> >>> --- a/MdePkg/Include/Library/BaseLib.h
> >>> +++ b/MdePkg/Include/Library/BaseLib.h
> >>> @@ -2856,6 +2856,55 @@ RemoveEntryList (
> >>> //
> >>>
> >>> // Math Services
> >>>
> >>> //
> >>>
> >>> +/**
> >>>
> >>> + Prototype for comparison function for any two element types.
> >>>
> >>> +
> >>>
> >>> + @param[in] Buffer1 The pointer to first buffer.
> >>>
> >>> + @param[in] Buffer2 The pointer to second
> buffer.
> >>>
> >>> +
> >>>
> >>> + @retval 0 Buffer1 equal to Buffer2.
> >>>
> >>> + @return <0 Buffer1 is less than
> Buffer2.
> >>>
> >>> + @return >0 Buffer1 is greater than
> >>> Buffer2.
> >>>
> >>> +**/
> >>>
> >>> +typedef
> >>>
> >>> +INTN
> >>>
> >>> +(EFIAPI *BASE_SORT_COMPARE)(
> >>>
> >>> + IN CONST VOID *Buffer1,
> >>>
> >>> + IN CONST VOID *Buffer2
> >>>
> >>> + );
> >>>
> >>> +
> >>>
> >>> +/**
> >>>
> >>> + This function is identical to perform QuickSort,
> >>>
> >>> + except that is uses the pre-allocated buffer so the in place sorting
> >> does not
> >>> need to
> >>>
> >>> + allocate and free buffers constantly.
> >>>
> >>> +
> >>>
> >>> + Each element must be equal sized.
> >>>
> >>> +
> >>>
> >>> + if BufferToSort is NULL, then ASSERT.
> >>>
> >>> + if CompareFunction is NULL, then ASSERT.
> >>>
> >>> + if BufferOneElement is NULL, then ASSERT.
> >>>
> >>> + if ElementSize is < 1, then ASSERT.
> >>>
> >>> +
> >>>
> >>> + if Count is < 2 then perform no action.
> >>>
> >>> +
> >>>
> >>> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
> >>> elements
> >>>
> >>> + on return a buffer of sorted
> >>> elements
> >>>
> >>> + @param[in] Count the number of elements in the
> >>> buffer to sort
> >>>
> >>> + @param[in] ElementSize Size of an element in bytes
> >>>
> >>> + @param[in] CompareFunction The function to call to perform
> the
> >>> comparison
> >>>
> >>> + of any 2 elements
> >>>
> >>> + @param[out] BufferOneElement Caller provided buffer whose size
> >>> equals to ElementSize.
> >>>
> >>> + It's used by QuickSort() for
> >>> swapping in sorting.
> >>>
> >>> +**/
> >>>
> >>> +VOID
> >>>
> >>> +EFIAPI
> >>>
> >>> +QuickSort (
> >>>
> >>> + IN OUT VOID *BufferToSort,
> >>>
> >>> + IN CONST UINTN Count,
> >>>
> >>> + IN CONST UINTN ElementSize,
> >>>
> >>> + IN BASE_SORT_COMPARE CompareFunction,
> >>>
> >>> + OUT VOID *BufferOneElement
> >>>
> >>> + );
> >>>
> >>>
> >>>
> >>> /**
> >>>
> >>> Shifts a 64-bit integer left between 0 and 63 bits. The low bits are
> >> filled
> >>> diff --git a/MdePkg/Library/BaseLib/BaseLib.inf
> >>> b/MdePkg/Library/BaseLib/BaseLib.inf
> >>> index 6efa5315b6..cebda3b210 100644
> >>> --- a/MdePkg/Library/BaseLib/BaseLib.inf
> >>> +++ b/MdePkg/Library/BaseLib/BaseLib.inf
> >>> @@ -32,6 +32,7 @@
> >>> SwapBytes16.c
> >>>
> >>> LongJump.c
> >>>
> >>> SetJump.c
> >>>
> >>> + QuickSort.c
> >>>
> >>> RShiftU64.c
> >>>
> >>> RRotU64.c
> >>>
> >>> RRotU32.c
> >>>
> >>> diff --git a/MdePkg/Library/BaseLib/QuickSort.c
> >>> b/MdePkg/Library/BaseLib/QuickSort.c
> >>> new file mode 100644
> >>> index 0000000000..a825c072b0
> >>> --- /dev/null
> >>> +++ b/MdePkg/Library/BaseLib/QuickSort.c
> >>> @@ -0,0 +1,116 @@
> >>> +/** @file
> >>>
> >>> + Math worker functions.
> >>>
> >>> +
> >>>
> >>> + Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
> >>>
> >>> + SPDX-License-Identifier: BSD-2-Clause-Patent
> >>>
> >>> +
> >>>
> >>> +**/
> >>>
> >>> +
> >>>
> >>> +#include "BaseLibInternals.h"
> >>>
> >>> +
> >>>
> >>> +/**
> >>>
> >>> + This function is identical to perform QuickSort,
> >>>
> >>> + except that is uses the pre-allocated buffer so the in place sorting
> >> does not
> >>> need to
> >>>
> >>> + allocate and free buffers constantly.
> >>>
> >>> +
> >>>
> >>> + Each element must be equal sized.
> >>>
> >>> +
> >>>
> >>> + if BufferToSort is NULL, then ASSERT.
> >>>
> >>> + if CompareFunction is NULL, then ASSERT.
> >>>
> >>> + if BufferOneElement is NULL, then ASSERT.
> >>>
> >>> + if ElementSize is < 1, then ASSERT.
> >>>
> >>> +
> >>>
> >>> + if Count is < 2 then perform no action.
> >>>
> >>> +
> >>>
> >>> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
> >>> elements
> >>>
> >>> + on return a buffer of sorted
> >>> elements
> >>>
> >>> + @param[in] Count the number of elements in the
> >>> buffer to sort
> >>>
> >>> + @param[in] ElementSize Size of an element in bytes
> >>>
> >>> + @param[in] CompareFunction The function to call to perform
> the
> >>> comparison
> >>>
> >>> + of any 2 elements
> >>>
> >>> + @param[out] BufferOneElement Caller provided buffer whose size
> >>> equals to ElementSize.
> >>>
> >>> + It's used by QuickSort() for
> >>> swapping in sorting.
> >>>
> >>> +**/
> >>>
> >>> +VOID
> >>>
> >>> +EFIAPI
> >>>
> >>> +QuickSort (
> >>>
> >>> + IN OUT VOID *BufferToSort,
> >>>
> >>> + IN CONST UINTN Count,
> >>>
> >>> + IN CONST UINTN ElementSize,
> >>>
> >>> + IN BASE_SORT_COMPARE CompareFunction,
> >>>
> >>> + OUT VOID *BufferOneElement
> >>>
> >>> + )
> >>>
> >>> +{
> >>>
> >>> + VOID *Pivot;
> >>>
> >>> + UINTN LoopCount;
> >>>
> >>> + UINTN NextSwapLocation;
> >>>
> >>> +
> >>>
> >>> + ASSERT (BufferToSort != NULL);
> >>>
> >>> + ASSERT (CompareFunction != NULL);
> >>>
> >>> + ASSERT (BufferOneElement != NULL);
> >>>
> >>> + ASSERT (ElementSize >= 1);
> >>>
> >>> +
> >>>
> >>> + if (Count < 2) {
> >>>
> >>> + return;
> >>>
> >>> + }
> >>>
> >>> +
> >>>
> >>> + NextSwapLocation = 0;
> >>>
> >>> +
> >>>
> >>> + //
> >>>
> >>> + // pick a pivot (we choose last element)
> >>>
> >>> + //
> >>>
> >>> + Pivot = ((UINT8*) BufferToSort + ((Count - 1) * ElementSize));
> >>>
> >>> +
> >>>
> >>> + //
> >>>
> >>> + // Now get the pivot such that all on "left" are below it
> >>>
> >>> + // and everything "right" are above it
> >>>
> >>> + //
> >>>
> >>> + for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {
> >>>
> >>> + //
> >>>
> >>> + // if the element is less than or equal to the pivot
> >>>
> >>> + //
> >>>
> >>> + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount)
> *
> >>> ElementSize)), Pivot) <= 0){
> >>>
> >>> + //
> >>>
> >>> + // swap
> >>>
> >>> + //
> >>>
> >>> + CopyMem (BufferOneElement, (UINT8*) BufferToSort +
> >>> (NextSwapLocation * ElementSize), ElementSize);
> >>>
> >>> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation *
> >>> ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize),
> >>> ElementSize);
> >>>
> >>> + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize),
> >>> BufferOneElement, ElementSize);
> >>>
> >>> +
> >>>
> >>> + //
> >>>
> >>> + // increment NextSwapLocation
> >>>
> >>> + //
> >>>
> >>> + NextSwapLocation++;
> >>>
> >>> + }
> >>>
> >>> + }
> >>>
> >>> + //
> >>>
> >>> + // swap pivot to it's final position (NextSwapLocation)
> >>>
> >>> + //
> >>>
> >>> + CopyMem (BufferOneElement, Pivot, ElementSize);
> >>>
> >>> + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation *
> >>> ElementSize), ElementSize);
> >>>
> >>> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation *
> ElementSize),
> >>> BufferOneElement, ElementSize);
> >>>
> >>> +
> >>>
> >>> + //
> >>>
> >>> + // Now recurse on 2 partial lists. neither of these will have the
> >> 'pivot'
> >>> element
> >>>
> >>> + // IE list is sorted left half, pivot element, sorted right half...
> >>>
> >>> + //
> >>>
> >>> + if (NextSwapLocation >= 2) {
> >>>
> >>> + QuickSort (
> >>>
> >>> + BufferToSort,
> >>>
> >>> + NextSwapLocation,
> >>>
> >>> + ElementSize,
> >>>
> >>> + CompareFunction,
> >>>
> >>> + BufferOneElement
> >>>
> >>> + );
> >>>
> >>> + }
> >>>
> >>> +
> >>>
> >>> + if ((Count - NextSwapLocation - 1) >= 2) {
> >>>
> >>> + QuickSort (
> >>>
> >>> + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
> >>>
> >>> + Count - NextSwapLocation - 1,
> >>>
> >>> + ElementSize,
> >>>
> >>> + CompareFunction,
> >>>
> >>> + BufferOneElement
> >>>
> >>> + );
> >>>
> >>> + }
> >>>
> >>> +}
> >>>
> >>> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> >>> b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> >>> index eae1a7158d..d09bd12bef 100644
> >>> --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> >>> +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> >>> @@ -1,7 +1,7 @@
> >>> ## @file
> >>>
> >>> # Base Library implementation for use with host based unit tests.
> >>>
> >>> #
> >>>
> >>> -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>
> >>>
> >>> +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
> >>>
> >>> # Portions copyright (c) 2008 - 2009, Apple Inc. All rights
> >> reserved.<BR>
> >>> # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights
> reserved.<BR>
> >>>
> >>> # Copyright (c) 2020, Hewlett Packard Enterprise Development LP.
> All
> >>> rights reserved.<BR>
> >>>
> >>> @@ -33,6 +33,7 @@
> >>> SwapBytes16.c
> >>>
> >>> LongJump.c
> >>>
> >>> SetJump.c
> >>>
> >>> + QuickSort.c
> >>>
> >>> RShiftU64.c
> >>>
> >>> RRotU64.c
> >>>
> >>> RRotU32.c
> >>>
> >>> --
> >>> 2.30.0.windows.1
> >>>
> >>>
> >>>
> >>> -=-=-=-=-=-=
> >>> Groups.io Links: You receive all messages sent to this group.
> >>> View/Reply Online (#81615):
> https://edk2.groups.io/g/devel/message/81615
> >>> Mute This Topic: https://groups.io/mt/86159728/4905953
> >>> Group Owner: devel+owner@edk2.groups.io
> >>> Unsubscribe: https://edk2.groups.io/g/devel/unsub
> >>> [gaoliming@byosoft.com.cn]
> >>> -=-=-=-=-=-=
> >>>
> >>
> >>
> >>
> >>
> >>
> >>
> >
> >
> >
> >
> >
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
2021-10-11 1:21 ` 回复: " gaoliming
@ 2021-10-12 0:09 ` IanX Kuo
0 siblings, 0 replies; 7+ messages in thread
From: IanX Kuo @ 2021-10-12 0:09 UTC (permalink / raw)
To: devel@edk2.groups.io, gaoliming@byosoft.com.cn,
'Marvin Häuser', Kinney, Michael D
Cc: Chan, Amy, Ni, Ray, Liu, Zhiguang
I send Patch v9, have anyone free can help me for the reviewed by.
Patch v8 is "move SORT_COMPARE definition from MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h, and then let SortLib.h include BaseLib.h."
Patch v9 is rollback to Patch v7.
Thanks,
Ian Kuo
-----Original Message-----
From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming
Sent: Monday, October 11, 2021 9:21 AM
To: 'Marvin Häuser' <mhaeuser@posteo.de>; devel@edk2.groups.io; Kinney, Michael D <michael.d.kinney@intel.com>; Kuo, IanX <ianx.kuo@intel.com>
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Liu, Zhiguang <zhiguang.liu@intel.com>
Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib
Michael and Marvin:
I understand your concern. I want to reduce the duplicated definition for the same function. I will not keep my idea if you are both OK to define BASE_SORT_COMPARE and SORT_COMPARE.
Thanks
Liming
> -----邮件原件-----
> 发件人: Marvin Häuser <mhaeuser@posteo.de>
> 发送时间: 2021年10月9日 0:09
> 收件人: devel@edk2.groups.io; michael.d.kinney@intel.com;
> gaoliming@byosoft.com.cn; Kuo, IanX <ianx.kuo@intel.com>
> 抄送: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Liu,
> Zhiguang <zhiguang.liu@intel.com>
> 主题: Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort
> function on BaseLib
>
> Hey all,
>
> I also don't think it makes much logical sense. They are distinct APIs
> in separate libraries that happen to take a function with the same
> prototype.
>
> I think the patches look good now, thanks!
>
> Best regards,
> Marvin
>
> On 08/10/2021 17:46, Michael D Kinney wrote:
> > Hi Liming,
> >
> > In general it is not a good idea to include a library include file
> > from another
> library include file.
> >
> > This becomes a hidden dependency.
> >
> > Mike
> >
> >> -----Original Message-----
> >> From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of
> gaoliming
> >> Sent: Thursday, October 7, 2021 7:16 PM
> >> To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>
> >> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>;
> >> Kinney,
> Michael D <michael.d.kinney@intel.com>; Liu,
> >> Zhiguang <zhiguang.liu@intel.com>
> >> Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add
> QuickSort function on BaseLib
> >>
> >> Kuo:
> >> I suggest to move SORT_COMPARE definition from
> >> MdeModulePkg\Include\Library\SortLib.h to
> MdePkg\Include\Library\BaseLib.h,
> >> and then let SortLib.h include BaseLib.h.
> >>
> >> Thanks
> >> Liming
> >>> -----邮件原件-----
> >>> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo
> >>> 发送时间: 2021年10月8日 8:27
> >>> 收件人: devel@edk2.groups.io
> >>> 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo
> >>> <ianx.kuo@intel.com>; Michael D Kinney
> >>> <michael.d.kinney@intel.com>; Liming Gao
> >>> <gaoliming@byosoft.com.cn>; Zhiguang Liu <zhiguang.liu@intel.com>
> >>> 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort
> function
> >>> on BaseLib
> >>>
> >>> From: IanX Kuo <ianx.kuo@intel.com>
> >>>
> >>> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
> >>>
> >>> Add QuickSort function into BaseLib
> >>>
> >>> Cc: Ray Ni <ray.ni@intel.com>
> >>> Cc: Michael D Kinney <michael.d.kinney@intel.com>
> >>> Cc: Liming Gao <gaoliming@byosoft.com.cn>
> >>> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
> >>> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> >>> ---
> >>> MdePkg/Include/Library/BaseLib.h | 49 ++++++++
> >>> MdePkg/Library/BaseLib/BaseLib.inf | 1 +
> >>> MdePkg/Library/BaseLib/QuickSort.c | 116
> >>> ++++++++++++++++++
> >>> .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
> >>> 4 files changed, 168 insertions(+), 1 deletion(-)
> >>> create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
> >>>
> >>> diff --git a/MdePkg/Include/Library/BaseLib.h
> >>> b/MdePkg/Include/Library/BaseLib.h
> >>> index 2452c1d92e..0ae0f4e6af 100644
> >>> --- a/MdePkg/Include/Library/BaseLib.h
> >>> +++ b/MdePkg/Include/Library/BaseLib.h
> >>> @@ -2856,6 +2856,55 @@ RemoveEntryList (
> >>> //
> >>>
> >>> // Math Services
> >>>
> >>> //
> >>>
> >>> +/**
> >>>
> >>> + Prototype for comparison function for any two element types.
> >>>
> >>> +
> >>>
> >>> + @param[in] Buffer1 The pointer to first buffer.
> >>>
> >>> + @param[in] Buffer2 The pointer to second
> buffer.
> >>>
> >>> +
> >>>
> >>> + @retval 0 Buffer1 equal to Buffer2.
> >>>
> >>> + @return <0 Buffer1 is less than
> Buffer2.
> >>>
> >>> + @return >0 Buffer1 is greater than
> >>> Buffer2.
> >>>
> >>> +**/
> >>>
> >>> +typedef
> >>>
> >>> +INTN
> >>>
> >>> +(EFIAPI *BASE_SORT_COMPARE)(
> >>>
> >>> + IN CONST VOID *Buffer1,
> >>>
> >>> + IN CONST VOID *Buffer2
> >>>
> >>> + );
> >>>
> >>> +
> >>>
> >>> +/**
> >>>
> >>> + This function is identical to perform QuickSort,
> >>>
> >>> + except that is uses the pre-allocated buffer so the in place
> >>> + sorting
> >> does not
> >>> need to
> >>>
> >>> + allocate and free buffers constantly.
> >>>
> >>> +
> >>>
> >>> + Each element must be equal sized.
> >>>
> >>> +
> >>>
> >>> + if BufferToSort is NULL, then ASSERT.
> >>>
> >>> + if CompareFunction is NULL, then ASSERT.
> >>>
> >>> + if BufferOneElement is NULL, then ASSERT.
> >>>
> >>> + if ElementSize is < 1, then ASSERT.
> >>>
> >>> +
> >>>
> >>> + if Count is < 2 then perform no action.
> >>>
> >>> +
> >>>
> >>> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
> >>> elements
> >>>
> >>> + on return a buffer of sorted
> >>> elements
> >>>
> >>> + @param[in] Count the number of elements in the
> >>> buffer to sort
> >>>
> >>> + @param[in] ElementSize Size of an element in bytes
> >>>
> >>> + @param[in] CompareFunction The function to call to perform
> the
> >>> comparison
> >>>
> >>> + of any 2 elements
> >>>
> >>> + @param[out] BufferOneElement Caller provided buffer whose size
> >>> equals to ElementSize.
> >>>
> >>> + It's used by QuickSort() for
> >>> swapping in sorting.
> >>>
> >>> +**/
> >>>
> >>> +VOID
> >>>
> >>> +EFIAPI
> >>>
> >>> +QuickSort (
> >>>
> >>> + IN OUT VOID *BufferToSort,
> >>>
> >>> + IN CONST UINTN Count,
> >>>
> >>> + IN CONST UINTN ElementSize,
> >>>
> >>> + IN BASE_SORT_COMPARE CompareFunction,
> >>>
> >>> + OUT VOID *BufferOneElement
> >>>
> >>> + );
> >>>
> >>>
> >>>
> >>> /**
> >>>
> >>> Shifts a 64-bit integer left between 0 and 63 bits. The low
> >>> bits are
> >> filled
> >>> diff --git a/MdePkg/Library/BaseLib/BaseLib.inf
> >>> b/MdePkg/Library/BaseLib/BaseLib.inf
> >>> index 6efa5315b6..cebda3b210 100644
> >>> --- a/MdePkg/Library/BaseLib/BaseLib.inf
> >>> +++ b/MdePkg/Library/BaseLib/BaseLib.inf
> >>> @@ -32,6 +32,7 @@
> >>> SwapBytes16.c
> >>>
> >>> LongJump.c
> >>>
> >>> SetJump.c
> >>>
> >>> + QuickSort.c
> >>>
> >>> RShiftU64.c
> >>>
> >>> RRotU64.c
> >>>
> >>> RRotU32.c
> >>>
> >>> diff --git a/MdePkg/Library/BaseLib/QuickSort.c
> >>> b/MdePkg/Library/BaseLib/QuickSort.c
> >>> new file mode 100644
> >>> index 0000000000..a825c072b0
> >>> --- /dev/null
> >>> +++ b/MdePkg/Library/BaseLib/QuickSort.c
> >>> @@ -0,0 +1,116 @@
> >>> +/** @file
> >>>
> >>> + Math worker functions.
> >>>
> >>> +
> >>>
> >>> + Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
> >>>
> >>> + SPDX-License-Identifier: BSD-2-Clause-Patent
> >>>
> >>> +
> >>>
> >>> +**/
> >>>
> >>> +
> >>>
> >>> +#include "BaseLibInternals.h"
> >>>
> >>> +
> >>>
> >>> +/**
> >>>
> >>> + This function is identical to perform QuickSort,
> >>>
> >>> + except that is uses the pre-allocated buffer so the in place
> >>> + sorting
> >> does not
> >>> need to
> >>>
> >>> + allocate and free buffers constantly.
> >>>
> >>> +
> >>>
> >>> + Each element must be equal sized.
> >>>
> >>> +
> >>>
> >>> + if BufferToSort is NULL, then ASSERT.
> >>>
> >>> + if CompareFunction is NULL, then ASSERT.
> >>>
> >>> + if BufferOneElement is NULL, then ASSERT.
> >>>
> >>> + if ElementSize is < 1, then ASSERT.
> >>>
> >>> +
> >>>
> >>> + if Count is < 2 then perform no action.
> >>>
> >>> +
> >>>
> >>> + @param[in, out] BufferToSort on call a Buffer of (possibly sorted)
> >>> elements
> >>>
> >>> + on return a buffer of sorted
> >>> elements
> >>>
> >>> + @param[in] Count the number of elements in the
> >>> buffer to sort
> >>>
> >>> + @param[in] ElementSize Size of an element in bytes
> >>>
> >>> + @param[in] CompareFunction The function to call to perform
> the
> >>> comparison
> >>>
> >>> + of any 2 elements
> >>>
> >>> + @param[out] BufferOneElement Caller provided buffer whose size
> >>> equals to ElementSize.
> >>>
> >>> + It's used by QuickSort() for
> >>> swapping in sorting.
> >>>
> >>> +**/
> >>>
> >>> +VOID
> >>>
> >>> +EFIAPI
> >>>
> >>> +QuickSort (
> >>>
> >>> + IN OUT VOID *BufferToSort,
> >>>
> >>> + IN CONST UINTN Count,
> >>>
> >>> + IN CONST UINTN ElementSize,
> >>>
> >>> + IN BASE_SORT_COMPARE CompareFunction,
> >>>
> >>> + OUT VOID *BufferOneElement
> >>>
> >>> + )
> >>>
> >>> +{
> >>>
> >>> + VOID *Pivot;
> >>>
> >>> + UINTN LoopCount;
> >>>
> >>> + UINTN NextSwapLocation;
> >>>
> >>> +
> >>>
> >>> + ASSERT (BufferToSort != NULL);
> >>>
> >>> + ASSERT (CompareFunction != NULL);
> >>>
> >>> + ASSERT (BufferOneElement != NULL);
> >>>
> >>> + ASSERT (ElementSize >= 1);
> >>>
> >>> +
> >>>
> >>> + if (Count < 2) {
> >>>
> >>> + return;
> >>>
> >>> + }
> >>>
> >>> +
> >>>
> >>> + NextSwapLocation = 0;
> >>>
> >>> +
> >>>
> >>> + //
> >>>
> >>> + // pick a pivot (we choose last element)
> >>>
> >>> + //
> >>>
> >>> + Pivot = ((UINT8*) BufferToSort + ((Count - 1) * ElementSize));
> >>>
> >>> +
> >>>
> >>> + //
> >>>
> >>> + // Now get the pivot such that all on "left" are below it
> >>>
> >>> + // and everything "right" are above it
> >>>
> >>> + //
> >>>
> >>> + for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {
> >>>
> >>> + //
> >>>
> >>> + // if the element is less than or equal to the pivot
> >>>
> >>> + //
> >>>
> >>> + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort +
> >>> + ((LoopCount)
> *
> >>> ElementSize)), Pivot) <= 0){
> >>>
> >>> + //
> >>>
> >>> + // swap
> >>>
> >>> + //
> >>>
> >>> + CopyMem (BufferOneElement, (UINT8*) BufferToSort +
> >>> (NextSwapLocation * ElementSize), ElementSize);
> >>>
> >>> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation *
> >>> ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize),
> >>> ElementSize);
> >>>
> >>> + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize),
> >>> BufferOneElement, ElementSize);
> >>>
> >>> +
> >>>
> >>> + //
> >>>
> >>> + // increment NextSwapLocation
> >>>
> >>> + //
> >>>
> >>> + NextSwapLocation++;
> >>>
> >>> + }
> >>>
> >>> + }
> >>>
> >>> + //
> >>>
> >>> + // swap pivot to it's final position (NextSwapLocation)
> >>>
> >>> + //
> >>>
> >>> + CopyMem (BufferOneElement, Pivot, ElementSize);
> >>>
> >>> + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation *
> >>> ElementSize), ElementSize);
> >>>
> >>> + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation *
> ElementSize),
> >>> BufferOneElement, ElementSize);
> >>>
> >>> +
> >>>
> >>> + //
> >>>
> >>> + // Now recurse on 2 partial lists. neither of these will have
> >>> + the
> >> 'pivot'
> >>> element
> >>>
> >>> + // IE list is sorted left half, pivot element, sorted right half...
> >>>
> >>> + //
> >>>
> >>> + if (NextSwapLocation >= 2) {
> >>>
> >>> + QuickSort (
> >>>
> >>> + BufferToSort,
> >>>
> >>> + NextSwapLocation,
> >>>
> >>> + ElementSize,
> >>>
> >>> + CompareFunction,
> >>>
> >>> + BufferOneElement
> >>>
> >>> + );
> >>>
> >>> + }
> >>>
> >>> +
> >>>
> >>> + if ((Count - NextSwapLocation - 1) >= 2) {
> >>>
> >>> + QuickSort (
> >>>
> >>> + (UINT8 *)BufferToSort + (NextSwapLocation + 1) *
> >>> + ElementSize,
> >>>
> >>> + Count - NextSwapLocation - 1,
> >>>
> >>> + ElementSize,
> >>>
> >>> + CompareFunction,
> >>>
> >>> + BufferOneElement
> >>>
> >>> + );
> >>>
> >>> + }
> >>>
> >>> +}
> >>>
> >>> diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> >>> b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> >>> index eae1a7158d..d09bd12bef 100644
> >>> --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> >>> +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
> >>> @@ -1,7 +1,7 @@
> >>> ## @file
> >>>
> >>> # Base Library implementation for use with host based unit tests.
> >>>
> >>> #
> >>>
> >>> -# Copyright (c) 2007 - 2020, Intel Corporation. All rights
> >>> reserved.<BR>
> >>>
> >>> +# Copyright (c) 2007 - 2021, Intel Corporation. All rights
> >>> +reserved.<BR>
> >>>
> >>> # Portions copyright (c) 2008 - 2009, Apple Inc. All rights
> >> reserved.<BR>
> >>> # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights
> reserved.<BR>
> >>>
> >>> # Copyright (c) 2020, Hewlett Packard Enterprise Development LP.
> All
> >>> rights reserved.<BR>
> >>>
> >>> @@ -33,6 +33,7 @@
> >>> SwapBytes16.c
> >>>
> >>> LongJump.c
> >>>
> >>> SetJump.c
> >>>
> >>> + QuickSort.c
> >>>
> >>> RShiftU64.c
> >>>
> >>> RRotU64.c
> >>>
> >>> RRotU32.c
> >>>
> >>> --
> >>> 2.30.0.windows.1
> >>>
> >>>
> >>>
> >>> -=-=-=-=-=-=
> >>> Groups.io Links: You receive all messages sent to this group.
> >>> View/Reply Online (#81615):
> https://edk2.groups.io/g/devel/message/81615
> >>> Mute This Topic: https://groups.io/mt/86159728/4905953
> >>> Group Owner: devel+owner@edk2.groups.io
> >>> Unsubscribe: https://edk2.groups.io/g/devel/unsub
> >>> [gaoliming@byosoft.com.cn]
> >>> -=-=-=-=-=-=
> >>>
> >>
> >>
> >>
> >>
> >>
> >>
> >
> >
> >
> >
> >
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2021-10-12 0:09 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2021-10-08 0:27 [PATCH v7 0/1] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-08 0:27 ` [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-08 2:15 ` 回复: [edk2-devel] " gaoliming
2021-10-08 15:46 ` Michael D Kinney
2021-10-08 16:09 ` Marvin Häuser
2021-10-11 1:21 ` 回复: " gaoliming
2021-10-12 0:09 ` IanX Kuo
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox