* [PATCH v1 0/3] Add function QuickSort into MdePkg/BaseLib
@ 2021-10-15 14:33 IanX Kuo
2021-10-15 14:33 ` [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
` (2 more replies)
0 siblings, 3 replies; 7+ messages in thread
From: IanX Kuo @ 2021-10-15 14:33 UTC (permalink / raw)
To: devel; +Cc: amy.chan, ray.ni, IanX Kuo
From: IanX Kuo <ianx.kuo@intel.com>
1. MdeModulePkg/SortLib: Use QuickSort instead of QuickSortWorker
2. CryptLib/CryptLib: Remove duplicate QuickSortWorker
3. CpuCacheInfoLib: Remove MdeModulePkg dependency
IanX Kuo (3):
MdeModulePkg/SortLib: Add QuickSort function on BaseLib
CryptoPkg/CryptLib: Add QuickSort function on BaseLib
UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
.../Library/BaseCryptLib/SysCall/CrtWrapper.c | 92 +-------------
.../Library/BaseSortLib/BaseSortLib.c | 117 +----------------
.../Library/UefiSortLib/UefiSortLib.c | 118 +-----------------
.../Library/CpuCacheInfoLib/CpuCacheInfoLib.c | 5 +-
.../CpuCacheInfoLib/DxeCpuCacheInfoLib.inf | 2 -
.../CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 -
.../CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 -
7 files changed, 16 insertions(+), 321 deletions(-)
--
2.30.0.windows.1
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
2021-10-15 14:33 [PATCH v1 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
@ 2021-10-15 14:33 ` IanX Kuo
2021-10-15 19:11 ` [edk2-devel] " Marvin Häuser
2021-10-15 14:33 ` [PATCH v1 2/3] CryptoPkg/CryptLib: " IanX Kuo
2021-10-15 14:33 ` [PATCH v1 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2 siblings, 1 reply; 7+ messages in thread
From: IanX Kuo @ 2021-10-15 14:33 UTC (permalink / raw)
To: devel; +Cc: amy.chan, ray.ni, IanX Kuo, Jian J Wang, Liming Gao
From: IanX Kuo <ianx.kuo@intel.com>
REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
Use QuickSort instead of QuickSortWorker
Cc: Ray Ni <ray.ni@intel.com>
Cc: Jian J Wang <jian.j.wang@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
.../Library/BaseSortLib/BaseSortLib.c | 117 +----------------
.../Library/UefiSortLib/UefiSortLib.c | 118 +-----------------
2 files changed, 10 insertions(+), 225 deletions(-)
diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec..b33339ac7c 100644
--- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
+++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
@@ -1,7 +1,7 @@
/** @file
Library used for sorting routines.
- Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>
+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
SPDX-License-Identifier: BSD-2-Clause-Patent
**/
@@ -13,114 +13,6 @@
#include <Library/MemoryAllocationLib.h>
#include <Library/SortLib.h>
-/**
- Worker function for QuickSorting. This function is identical to PerformQuickSort,
- 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 Buffer is NULL, then ASSERT.
-
- if Count is < 2 then perform no action.
- if Size is < 1 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[in] Buffer Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-QuickSortWorker (
- IN OUT VOID *BufferToSort,
- IN CONST UINTN Count,
- IN CONST UINTN ElementSize,
- IN SORT_COMPARE CompareFunction,
- IN VOID *Buffer
- )
-{
- VOID *Pivot;
- UINTN LoopCount;
- UINTN NextSwapLocation;
-
- ASSERT(BufferToSort != NULL);
- ASSERT(CompareFunction != NULL);
- ASSERT(Buffer != NULL);
-
- if ( Count < 2
- || ElementSize < 1
- ){
- 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 the pivot
- //
- if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
- //
- // swap
- //
- CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
-
- //
- // increment NextSwapLocation
- //
- NextSwapLocation++;
- }
- }
- //
- // swap pivot to it's final position (NextSwapLocaiton)
- //
- CopyMem (Buffer, Pivot, ElementSize);
- CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
- //
- // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
- // IE list is sorted left half, pivot element, sorted right half...
- //
- if (NextSwapLocation >= 2) {
- QuickSortWorker(
- BufferToSort,
- NextSwapLocation,
- ElementSize,
- CompareFunction,
- Buffer);
- }
-
- if ((Count - NextSwapLocation - 1) >= 2) {
- QuickSortWorker(
- (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
- Count - NextSwapLocation - 1,
- ElementSize,
- CompareFunction,
- Buffer);
- }
- return;
-}
/**
Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
@@ -156,12 +48,13 @@ PerformQuickSort (
Buffer = AllocateZeroPool(ElementSize);
ASSERT(Buffer != NULL);
- QuickSortWorker(
+ QuickSort (
BufferToSort,
Count,
ElementSize,
- CompareFunction,
- Buffer);
+ (SORT_COMPARE) CompareFunction,
+ Buffer
+ );
FreePool(Buffer);
return;
diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
index 46dc443638..151a5a9ac3 100644
--- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
+++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
@@ -1,7 +1,7 @@
/** @file
Library used for sorting routines.
- Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>
+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
SPDX-License-Identifier: BSD-2-Clause-Patent
**/
@@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation = NULL;
} \
}
-/**
- Worker function for QuickSorting. This function is identical to PerformQuickSort,
- 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 Buffer is NULL, then ASSERT.
-
- if Count is < 2 then perform no action.
- if Size is < 1 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[in] Buffer Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-QuickSortWorker (
- IN OUT VOID *BufferToSort,
- IN CONST UINTN Count,
- IN CONST UINTN ElementSize,
- IN SORT_COMPARE CompareFunction,
- IN VOID *Buffer
- )
-{
- VOID *Pivot;
- UINTN LoopCount;
- UINTN NextSwapLocation;
-
- ASSERT(BufferToSort != NULL);
- ASSERT(CompareFunction != NULL);
- ASSERT(Buffer != NULL);
-
- if ( Count < 2
- || ElementSize < 1
- ){
- 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 the pivot
- //
- if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
- //
- // swap
- //
- CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
-
- //
- // increment NextSwapLocation
- //
- NextSwapLocation++;
- }
- }
- //
- // swap pivot to it's final position (NextSwapLocaiton)
- //
- CopyMem (Buffer, Pivot, ElementSize);
- CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
- //
- // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
- // IE list is sorted left half, pivot element, sorted right half...
- //
- if (NextSwapLocation >= 2) {
- QuickSortWorker(
- BufferToSort,
- NextSwapLocation,
- ElementSize,
- CompareFunction,
- Buffer);
- }
-
- if ((Count - NextSwapLocation - 1) >= 2) {
- QuickSortWorker(
- (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
- Count - NextSwapLocation - 1,
- ElementSize,
- CompareFunction,
- Buffer);
- }
-
- return;
-}
/**
Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
@@ -173,12 +64,13 @@ PerformQuickSort (
Buffer = AllocateZeroPool(ElementSize);
ASSERT(Buffer != NULL);
- QuickSortWorker(
+ QuickSort (
BufferToSort,
Count,
ElementSize,
- CompareFunction,
- Buffer);
+ (SORT_COMPARE) CompareFunction,
+ Buffer
+ );
FreePool(Buffer);
return;
--
2.30.0.windows.1
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH v1 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
2021-10-15 14:33 [PATCH v1 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-15 14:33 ` [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
@ 2021-10-15 14:33 ` IanX Kuo
2021-10-15 14:33 ` [PATCH v1 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2 siblings, 0 replies; 7+ messages in thread
From: IanX Kuo @ 2021-10-15 14:33 UTC (permalink / raw)
To: devel
Cc: amy.chan, ray.ni, IanX Kuo, Jiewen Yao, Jian J Wang, Xiaoyu Lu,
Guomin Jiang
From: IanX Kuo <ianx.kuo@intel.com>
REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
Use QuickSort instead of QuickSortWorker
Cc: Ray Ni <ray.ni@intel.com>
Cc: Jiewen Yao <jiewen.yao@intel.com>
Cc: Jian J Wang <jian.j.wang@intel.com>
Cc: Xiaoyu Lu <xiaoyux.lu@intel.com>
Cc: Guomin Jiang <guomin.jiang@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
.../Library/BaseCryptLib/SysCall/CrtWrapper.c | 92 +------------------
1 file changed, 2 insertions(+), 90 deletions(-)
diff --git a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
index 42235ab96a..b10edaae5b 100644
--- a/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
+++ b/CryptoPkg/Library/BaseCryptLib/SysCall/CrtWrapper.c
@@ -2,7 +2,7 @@
C Run-Time Libraries (CRT) Wrapper Implementation for OpenSSL-based
Cryptographic Library.
-Copyright (c) 2009 - 2017, Intel Corporation. All rights reserved.<BR>
+Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.<BR>
SPDX-License-Identifier: BSD-2-Clause-Patent
**/
@@ -22,91 +22,6 @@ int
IN VOID *Buffer2
);
-//
-// Duplicated from EDKII BaseSortLib for qsort() wrapper
-//
-STATIC
-VOID
-QuickSortWorker (
- IN OUT VOID *BufferToSort,
- IN CONST UINTN Count,
- IN CONST UINTN ElementSize,
- IN SORT_COMPARE CompareFunction,
- IN VOID *Buffer
- )
-{
- VOID *Pivot;
- UINTN LoopCount;
- UINTN NextSwapLocation;
-
- ASSERT(BufferToSort != NULL);
- ASSERT(CompareFunction != NULL);
- ASSERT(Buffer != NULL);
-
- if (Count < 2 || ElementSize < 1) {
- 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 the pivot
- //
- if (CompareFunction ((VOID *)((UINT8 *)BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0) {
- //
- // Swap
- //
- CopyMem (Buffer, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
- CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), (UINT8 *)BufferToSort + ((LoopCount) * ElementSize), ElementSize);
- CopyMem ((UINT8 *)BufferToSort + ((LoopCount) * ElementSize), Buffer, ElementSize);
-
- //
- // Increment NextSwapLocation
- //
- NextSwapLocation++;
- }
- }
- //
- // Swap pivot to its final position (NextSwapLocation)
- //
- CopyMem (Buffer, Pivot, ElementSize);
- CopyMem (Pivot, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
- CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), Buffer, 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...
- //
- QuickSortWorker (
- BufferToSort,
- NextSwapLocation,
- ElementSize,
- CompareFunction,
- Buffer
- );
-
- QuickSortWorker (
- (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
- Count - NextSwapLocation - 1,
- ElementSize,
- CompareFunction,
- Buffer
- );
-
- return;
-}
-
//---------------------------------------------------------
// Standard C Run-time Library Interface Wrapper
//---------------------------------------------------------
@@ -337,10 +252,7 @@ void qsort (void *base, size_t num, size_t width, int (*compare)(const void *, c
Buffer = malloc (width);
ASSERT (Buffer != NULL);
- //
- // Re-use PerformQuickSort() function Implementation in EDKII BaseSortLib.
- //
- QuickSortWorker (base, (UINTN)num, (UINTN)width, (SORT_COMPARE)compare, Buffer);
+ QuickSort (base, (UINTN)num, (UINTN)width, (BASE_SORT_COMPARE)compare, Buffer);
free (Buffer);
return;
--
2.30.0.windows.1
^ permalink raw reply related [flat|nested] 7+ messages in thread
* [PATCH v1 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
2021-10-15 14:33 [PATCH v1 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-15 14:33 ` [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-15 14:33 ` [PATCH v1 2/3] CryptoPkg/CryptLib: " IanX Kuo
@ 2021-10-15 14:33 ` IanX Kuo
2021-10-15 19:14 ` [edk2-devel] " Marvin Häuser
2 siblings, 1 reply; 7+ messages in thread
From: IanX Kuo @ 2021-10-15 14:33 UTC (permalink / raw)
To: devel; +Cc: amy.chan, ray.ni, IanX Kuo, Eric Dong, Rahul Kumar
From: IanX Kuo <ianx.kuo@intel.com>
REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
Remove MdeModulePkg dependency
Cc: Eric Dong <eric.dong@intel.com>
Cc: Ray Ni <ray.ni@intel.com>
Cc: Rahul Kumar <rahul1.kumar@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c | 5 ++++-
UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf | 2 --
UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 -
UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 --
4 files changed, 4 insertions(+), 6 deletions(-)
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
index c0077d6770..b5ed05bd43 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
@@ -282,6 +282,7 @@ CpuCacheInfoCollectCpuCacheInfoData (
UINTN LocalCacheInfoCount;
UINTN Index;
UINTN NextIndex;
+ VOID *QuickSortBuffer;
//
// Get number of Packages and Package ID.
@@ -369,7 +370,9 @@ CpuCacheInfoCollectCpuCacheInfoData (
//
// Sort LocalCacheInfo array by CPU package ID, core type, cache level and cache type.
//
- PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare);
+ QuickSortBuffer = AllocateZeroPool (sizeof (*LocalCacheInfo));
+ ASSERT (QuickSortBuffer != NULL);
+ QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (BASE_SORT_COMPARE) CpuCacheInfoCompare, QuickSortBuffer);
CopyMem (CacheInfo, LocalCacheInfo, sizeof (*CacheInfo) * LocalCacheInfoCount);
DEBUG_CODE (
CpuCacheInfoPrintCpuCacheInfoTable (CacheInfo, LocalCacheInfoCount);
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
index c3d3f1e799..fdd79970f9 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
@@ -25,7 +25,6 @@
[Packages]
MdePkg/MdePkg.dec
- MdeModulePkg/MdeModulePkg.dec
UefiCpuPkg/UefiCpuPkg.dec
[LibraryClasses]
@@ -34,7 +33,6 @@
BaseMemoryLib
MemoryAllocationLib
UefiBootServicesTableLib
- SortLib
[Protocols]
gEfiMpServiceProtocolGuid
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
index 26e1f46516..829a9f43ce 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
@@ -17,7 +17,6 @@
#include <Library/DebugLib.h>
#include <Library/BaseMemoryLib.h>
#include <Library/MemoryAllocationLib.h>
-#include <Library/SortLib.h>
#include <Library/CpuCacheInfoLib.h>
typedef union {
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
index 0864497849..c643fc89be 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
@@ -25,7 +25,6 @@
[Packages]
MdePkg/MdePkg.dec
- MdeModulePkg/MdeModulePkg.dec
UefiCpuPkg/UefiCpuPkg.dec
[LibraryClasses]
@@ -34,7 +33,6 @@
BaseMemoryLib
MemoryAllocationLib
PeiServicesTablePointerLib
- SortLib
[Ppis]
gEdkiiPeiMpServices2PpiGuid
--
2.30.0.windows.1
^ permalink raw reply related [flat|nested] 7+ messages in thread
* Re: [edk2-devel] [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
2021-10-15 14:33 ` [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
@ 2021-10-15 19:11 ` Marvin Häuser
2021-10-15 23:32 ` IanX Kuo
0 siblings, 1 reply; 7+ messages in thread
From: Marvin Häuser @ 2021-10-15 19:11 UTC (permalink / raw)
To: devel, ianx.kuo; +Cc: amy.chan, ray.ni, Jian J Wang, Liming Gao
Good day Ianx,
On 15.10.21 16:33, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Use QuickSort instead of QuickSortWorker
>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Jian J Wang <jian.j.wang@intel.com>
> Cc: Liming Gao <gaoliming@byosoft.com.cn>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
> .../Library/BaseSortLib/BaseSortLib.c | 117 +----------------
> .../Library/UefiSortLib/UefiSortLib.c | 118 +-----------------
> 2 files changed, 10 insertions(+), 225 deletions(-)
>
> diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
> index a12c7bc0ec..b33339ac7c 100644
> --- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
> +++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
> @@ -1,7 +1,7 @@
> /** @file
> Library used for sorting routines.
>
> - Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>
> + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
> SPDX-License-Identifier: BSD-2-Clause-Patent
>
> **/
> @@ -13,114 +13,6 @@
> #include <Library/MemoryAllocationLib.h>
> #include <Library/SortLib.h>
>
> -/**
> - Worker function for QuickSorting. This function is identical to PerformQuickSort,
> - 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 Buffer is NULL, then ASSERT.
> -
> - if Count is < 2 then perform no action.
> - if Size is < 1 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[in] Buffer Buffer of size ElementSize for use in swapping
> -**/
> -VOID
> -EFIAPI
> -QuickSortWorker (
> - IN OUT VOID *BufferToSort,
> - IN CONST UINTN Count,
> - IN CONST UINTN ElementSize,
> - IN SORT_COMPARE CompareFunction,
> - IN VOID *Buffer
> - )
> -{
> - VOID *Pivot;
> - UINTN LoopCount;
> - UINTN NextSwapLocation;
> -
> - ASSERT(BufferToSort != NULL);
> - ASSERT(CompareFunction != NULL);
> - ASSERT(Buffer != NULL);
> -
> - if ( Count < 2
> - || ElementSize < 1
> - ){
> - 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 the pivot
> - //
> - if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
> - //
> - // swap
> - //
> - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
> -
> - //
> - // increment NextSwapLocation
> - //
> - NextSwapLocation++;
> - }
> - }
> - //
> - // swap pivot to it's final position (NextSwapLocaiton)
> - //
> - CopyMem (Buffer, Pivot, ElementSize);
> - CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
> -
> - //
> - // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
> - // IE list is sorted left half, pivot element, sorted right half...
> - //
> - if (NextSwapLocation >= 2) {
> - QuickSortWorker(
> - BufferToSort,
> - NextSwapLocation,
> - ElementSize,
> - CompareFunction,
> - Buffer);
> - }
> -
> - if ((Count - NextSwapLocation - 1) >= 2) {
> - QuickSortWorker(
> - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
> - Count - NextSwapLocation - 1,
> - ElementSize,
> - CompareFunction,
> - Buffer);
> - }
> - return;
> -}
> /**
> Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
>
> @@ -156,12 +48,13 @@ PerformQuickSort (
> Buffer = AllocateZeroPool(ElementSize);
> ASSERT(Buffer != NULL);
>
> - QuickSortWorker(
> + QuickSort (
> BufferToSort,
> Count,
> ElementSize,
> - CompareFunction,
> - Buffer);
> + (SORT_COMPARE) CompareFunction,
CLANGPDB and GCC5 do not need this cast; I cannot easily test MSVC right
now. Does it compile fine for you with the cast dropped? Dropping the
cast gives us compile-time checking for actual type-compatibility.
> + Buffer
> + );
>
> FreePool(Buffer);
> return;
> diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
> index 46dc443638..151a5a9ac3 100644
> --- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
> +++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
> @@ -1,7 +1,7 @@
> /** @file
> Library used for sorting routines.
>
> - Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>
> + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
> SPDX-License-Identifier: BSD-2-Clause-Patent
>
> **/
> @@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation = NULL;
> } \
> }
>
> -/**
> - Worker function for QuickSorting. This function is identical to PerformQuickSort,
> - 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 Buffer is NULL, then ASSERT.
> -
> - if Count is < 2 then perform no action.
> - if Size is < 1 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[in] Buffer Buffer of size ElementSize for use in swapping
> -**/
> -VOID
> -EFIAPI
> -QuickSortWorker (
> - IN OUT VOID *BufferToSort,
> - IN CONST UINTN Count,
> - IN CONST UINTN ElementSize,
> - IN SORT_COMPARE CompareFunction,
> - IN VOID *Buffer
> - )
> -{
> - VOID *Pivot;
> - UINTN LoopCount;
> - UINTN NextSwapLocation;
> -
> - ASSERT(BufferToSort != NULL);
> - ASSERT(CompareFunction != NULL);
> - ASSERT(Buffer != NULL);
> -
> - if ( Count < 2
> - || ElementSize < 1
> - ){
> - 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 the pivot
> - //
> - if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
> - //
> - // swap
> - //
> - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
> -
> - //
> - // increment NextSwapLocation
> - //
> - NextSwapLocation++;
> - }
> - }
> - //
> - // swap pivot to it's final position (NextSwapLocaiton)
> - //
> - CopyMem (Buffer, Pivot, ElementSize);
> - CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
> -
> - //
> - // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
> - // IE list is sorted left half, pivot element, sorted right half...
> - //
> - if (NextSwapLocation >= 2) {
> - QuickSortWorker(
> - BufferToSort,
> - NextSwapLocation,
> - ElementSize,
> - CompareFunction,
> - Buffer);
> - }
> -
> - if ((Count - NextSwapLocation - 1) >= 2) {
> - QuickSortWorker(
> - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
> - Count - NextSwapLocation - 1,
> - ElementSize,
> - CompareFunction,
> - Buffer);
> - }
> -
> - return;
> -}
> /**
> Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
>
> @@ -173,12 +64,13 @@ PerformQuickSort (
> Buffer = AllocateZeroPool(ElementSize);
> ASSERT(Buffer != NULL);
>
> - QuickSortWorker(
> + QuickSort (
> BufferToSort,
> Count,
> ElementSize,
> - CompareFunction,
> - Buffer);
> + (SORT_COMPARE) CompareFunction,
See above.
Best regards,
Marvin
> + Buffer
> + );
>
> FreePool(Buffer);
> return;
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [edk2-devel] [PATCH v1 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
2021-10-15 14:33 ` [PATCH v1 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
@ 2021-10-15 19:14 ` Marvin Häuser
0 siblings, 0 replies; 7+ messages in thread
From: Marvin Häuser @ 2021-10-15 19:14 UTC (permalink / raw)
To: devel, ianx.kuo; +Cc: amy.chan, ray.ni, Eric Dong, Rahul Kumar
Good day Ianx,
On 15.10.21 16:33, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo@intel.com>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Remove MdeModulePkg dependency
>
> Cc: Eric Dong <eric.dong@intel.com>
> Cc: Ray Ni <ray.ni@intel.com>
> Cc: Rahul Kumar <rahul1.kumar@intel.com>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
> ---
> UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c | 5 ++++-
> UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf | 2 --
> UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 -
> UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 --
> 4 files changed, 4 insertions(+), 6 deletions(-)
>
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
> index c0077d6770..b5ed05bd43 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
> @@ -282,6 +282,7 @@ CpuCacheInfoCollectCpuCacheInfoData (
> UINTN LocalCacheInfoCount;
> UINTN Index;
> UINTN NextIndex;
> + VOID *QuickSortBuffer;
>
> //
> // Get number of Packages and Package ID.
> @@ -369,7 +370,9 @@ CpuCacheInfoCollectCpuCacheInfoData (
> //
> // Sort LocalCacheInfo array by CPU package ID, core type, cache level and cache type.
> //
> - PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare);
> + QuickSortBuffer = AllocateZeroPool (sizeof (*LocalCacheInfo));
> + ASSERT (QuickSortBuffer != NULL);
Dynamic allocations should always be handled with a proper runtime
check, but I think LocalCacheInfo is small enough to live on the stack
anyway, no?
Best regards,
Marvin
> + QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (BASE_SORT_COMPARE) CpuCacheInfoCompare, QuickSortBuffer);
> CopyMem (CacheInfo, LocalCacheInfo, sizeof (*CacheInfo) * LocalCacheInfoCount);
> DEBUG_CODE (
> CpuCacheInfoPrintCpuCacheInfoTable (CacheInfo, LocalCacheInfoCount);
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
> index c3d3f1e799..fdd79970f9 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf
> @@ -25,7 +25,6 @@
>
> [Packages]
> MdePkg/MdePkg.dec
> - MdeModulePkg/MdeModulePkg.dec
> UefiCpuPkg/UefiCpuPkg.dec
>
> [LibraryClasses]
> @@ -34,7 +33,6 @@
> BaseMemoryLib
> MemoryAllocationLib
> UefiBootServicesTableLib
> - SortLib
>
> [Protocols]
> gEfiMpServiceProtocolGuid
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
> index 26e1f46516..829a9f43ce 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
> @@ -17,7 +17,6 @@
> #include <Library/DebugLib.h>
> #include <Library/BaseMemoryLib.h>
> #include <Library/MemoryAllocationLib.h>
> -#include <Library/SortLib.h>
> #include <Library/CpuCacheInfoLib.h>
>
> typedef union {
> diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
> index 0864497849..c643fc89be 100644
> --- a/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
> +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf
> @@ -25,7 +25,6 @@
>
> [Packages]
> MdePkg/MdePkg.dec
> - MdeModulePkg/MdeModulePkg.dec
> UefiCpuPkg/UefiCpuPkg.dec
>
> [LibraryClasses]
> @@ -34,7 +33,6 @@
> BaseMemoryLib
> MemoryAllocationLib
> PeiServicesTablePointerLib
> - SortLib
>
> [Ppis]
> gEdkiiPeiMpServices2PpiGuid
^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [edk2-devel] [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
2021-10-15 19:11 ` [edk2-devel] " Marvin Häuser
@ 2021-10-15 23:32 ` IanX Kuo
0 siblings, 0 replies; 7+ messages in thread
From: IanX Kuo @ 2021-10-15 23:32 UTC (permalink / raw)
To: Marvin Häuser, devel@edk2.groups.io
Cc: Chan, Amy, Ni, Ray, Wang, Jian J, Liming Gao
[-- Attachment #1: Type: text/plain, Size: 12183 bytes --]
@Marvin Häuser<mailto:mhaeuser@posteo.de>
Thank to catch it. I dropped it on my patch v2.
Compiler
Status
Linux GCC5 (gcc 10.2.0/9.3.0/8.4.0/7.5.0/5.5.0/5.4.0)
Pass
Windows CLANGPDB (clang 12.0.0), Linux CLANGPDB (clang 12.0.0)
Pass
Windows MSVC (VS2015/VS2017/VS2019)
Pass
Mac XCODE5 (clang 11.0.0)
Pass
Thanks,
Ian Kuo
-----Original Message-----
From: Marvin Häuser <mhaeuser@posteo.de>
Sent: Saturday, October 16, 2021 3:11 AM
To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Wang, Jian J <jian.j.wang@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>
Subject: Re: [edk2-devel] [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
Good day Ianx,
On 15.10.21 16:33, IanX Kuo wrote:
> From: IanX Kuo <ianx.kuo@intel.com<mailto:ianx.kuo@intel.com>>
>
> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
>
> Use QuickSort instead of QuickSortWorker
>
> Cc: Ray Ni <ray.ni@intel.com<mailto:ray.ni@intel.com>>
> Cc: Jian J Wang <jian.j.wang@intel.com<mailto:jian.j.wang@intel.com>>
> Cc: Liming Gao <gaoliming@byosoft.com.cn<mailto:gaoliming@byosoft.com.cn>>
> Signed-off-by: IanX Kuo <ianx.kuo@intel.com<mailto:ianx.kuo@intel.com>>
> ---
> .../Library/BaseSortLib/BaseSortLib.c | 117 +----------------
> .../Library/UefiSortLib/UefiSortLib.c | 118 +-----------------
> 2 files changed, 10 insertions(+), 225 deletions(-)
>
> diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
> b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
> index a12c7bc0ec..b33339ac7c 100644
> --- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
> +++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
> @@ -1,7 +1,7 @@
> /** @file
> Library used for sorting routines.
>
> - Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved.
> <BR>
> + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
> + <BR>
> SPDX-License-Identifier: BSD-2-Clause-Patent
>
> **/
> @@ -13,114 +13,6 @@
> #include <Library/MemoryAllocationLib.h>
> #include <Library/SortLib.h>
>
> -/**
> - Worker function for QuickSorting. This function is identical to
> PerformQuickSort,
> - 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 Buffer is NULL, then ASSERT.
> -
> - if Count is < 2 then perform no action.
> - if Size is < 1 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[in] Buffer Buffer of size ElementSize for use in swapping
> -**/
> -VOID
> -EFIAPI
> -QuickSortWorker (
> - IN OUT VOID *BufferToSort,
> - IN CONST UINTN Count,
> - IN CONST UINTN ElementSize,
> - IN SORT_COMPARE CompareFunction,
> - IN VOID *Buffer
> - )
> -{
> - VOID *Pivot;
> - UINTN LoopCount;
> - UINTN NextSwapLocation;
> -
> - ASSERT(BufferToSort != NULL);
> - ASSERT(CompareFunction != NULL);
> - ASSERT(Buffer != NULL);
> -
> - if ( Count < 2
> - || ElementSize < 1
> - ){
> - 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 the pivot
> - //
> - if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
> - //
> - // swap
> - //
> - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
> -
> - //
> - // increment NextSwapLocation
> - //
> - NextSwapLocation++;
> - }
> - }
> - //
> - // swap pivot to it's final position (NextSwapLocaiton)
> - //
> - CopyMem (Buffer, Pivot, ElementSize);
> - CopyMem (Pivot,
> (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize),
> Buffer, ElementSize);
> -
> - //
> - // Now recurse on 2 paritial lists. neither of these will have the
> 'pivot' element
> - // IE list is sorted left half, pivot element, sorted right half...
> - //
> - if (NextSwapLocation >= 2) {
> - QuickSortWorker(
> - BufferToSort,
> - NextSwapLocation,
> - ElementSize,
> - CompareFunction,
> - Buffer);
> - }
> -
> - if ((Count - NextSwapLocation - 1) >= 2) {
> - QuickSortWorker(
> - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
> - Count - NextSwapLocation - 1,
> - ElementSize,
> - CompareFunction,
> - Buffer);
> - }
> - return;
> -}
> /**
> Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
>
> @@ -156,12 +48,13 @@ PerformQuickSort (
> Buffer = AllocateZeroPool(ElementSize);
> ASSERT(Buffer != NULL);
>
> - QuickSortWorker(
> + QuickSort (
> BufferToSort,
> Count,
> ElementSize,
> - CompareFunction,
> - Buffer);
> + (SORT_COMPARE) CompareFunction,
CLANGPDB and GCC5 do not need this cast; I cannot easily test MSVC right now. Does it compile fine for you with the cast dropped? Dropping the cast gives us compile-time checking for actual type-compatibility.
> + Buffer
> + );
>
> FreePool(Buffer);
> return;
> diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
> b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
> index 46dc443638..151a5a9ac3 100644
> --- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
> +++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
> @@ -1,7 +1,7 @@
> /** @file
> Library used for sorting routines.
>
> - Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved.
> <BR>
> + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
> + <BR>
> SPDX-License-Identifier: BSD-2-Clause-Patent
>
> **/
> @@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation = NULL;
> } \
> }
>
> -/**
> - Worker function for QuickSorting. This function is identical to
> PerformQuickSort,
> - 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 Buffer is NULL, then ASSERT.
> -
> - if Count is < 2 then perform no action.
> - if Size is < 1 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[in] Buffer Buffer of size ElementSize for use in swapping
> -**/
> -VOID
> -EFIAPI
> -QuickSortWorker (
> - IN OUT VOID *BufferToSort,
> - IN CONST UINTN Count,
> - IN CONST UINTN ElementSize,
> - IN SORT_COMPARE CompareFunction,
> - IN VOID *Buffer
> - )
> -{
> - VOID *Pivot;
> - UINTN LoopCount;
> - UINTN NextSwapLocation;
> -
> - ASSERT(BufferToSort != NULL);
> - ASSERT(CompareFunction != NULL);
> - ASSERT(Buffer != NULL);
> -
> - if ( Count < 2
> - || ElementSize < 1
> - ){
> - 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 the pivot
> - //
> - if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
> - //
> - // swap
> - //
> - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
> -
> - //
> - // increment NextSwapLocation
> - //
> - NextSwapLocation++;
> - }
> - }
> - //
> - // swap pivot to it's final position (NextSwapLocaiton)
> - //
> - CopyMem (Buffer, Pivot, ElementSize);
> - CopyMem (Pivot,
> (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
> - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize),
> Buffer, ElementSize);
> -
> - //
> - // Now recurse on 2 paritial lists. neither of these will have the
> 'pivot' element
> - // IE list is sorted left half, pivot element, sorted right half...
> - //
> - if (NextSwapLocation >= 2) {
> - QuickSortWorker(
> - BufferToSort,
> - NextSwapLocation,
> - ElementSize,
> - CompareFunction,
> - Buffer);
> - }
> -
> - if ((Count - NextSwapLocation - 1) >= 2) {
> - QuickSortWorker(
> - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
> - Count - NextSwapLocation - 1,
> - ElementSize,
> - CompareFunction,
> - Buffer);
> - }
> -
> - return;
> -}
> /**
> Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
>
> @@ -173,12 +64,13 @@ PerformQuickSort (
> Buffer = AllocateZeroPool(ElementSize);
> ASSERT(Buffer != NULL);
>
> - QuickSortWorker(
> + QuickSort (
> BufferToSort,
> Count,
> ElementSize,
> - CompareFunction,
> - Buffer);
> + (SORT_COMPARE) CompareFunction,
See above.
Best regards,
Marvin
> + Buffer
> + );
>
> FreePool(Buffer);
> return;
[-- Attachment #2: Type: text/html, Size: 36415 bytes --]
^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2021-10-15 23:32 UTC | newest]
Thread overview: 7+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2021-10-15 14:33 [PATCH v1 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-15 14:33 ` [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-15 19:11 ` [edk2-devel] " Marvin Häuser
2021-10-15 23:32 ` IanX Kuo
2021-10-15 14:33 ` [PATCH v1 2/3] CryptoPkg/CryptLib: " IanX Kuo
2021-10-15 14:33 ` [PATCH v1 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2021-10-15 19:14 ` [edk2-devel] " Marvin Häuser
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox