* [PATCH v3 0/3] Add function QuickSort into MdePkg/BaseLib
@ 2021-10-16 22:34 IanX Kuo
2021-10-16 22:34 ` [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
` (2 more replies)
0 siblings, 3 replies; 10+ messages in thread
From: IanX Kuo @ 2021-10-16 22:34 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
1-1: Drop cast (V2)
2. CryptLib/CryptLib: Remove duplicate QuickSortWorker
2-1: Drop cast (V3)
3. CpuCacheInfoLib: Remove MdeModulePkg dependency
3-1: Drop cast (V2)
3-2: Add runtime check (V2)
3-3: Drop assert check (V3)
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 | 115 +----------------
.../Library/UefiSortLib/UefiSortLib.c | 116 +-----------------
.../Library/CpuCacheInfoLib/CpuCacheInfoLib.c | 8 +-
.../CpuCacheInfoLib/DxeCpuCacheInfoLib.inf | 2 -
.../CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 -
.../CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 -
7 files changed, 17 insertions(+), 319 deletions(-)
--
2.30.0.windows.1
^ permalink raw reply [flat|nested] 10+ messages in thread
* [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
2021-10-16 22:34 [PATCH v3 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
@ 2021-10-16 22:34 ` IanX Kuo
2021-10-18 1:58 ` IanX Kuo
2021-10-18 2:50 ` 回复: [edk2-devel] " gaoliming
2021-10-16 22:34 ` [PATCH v3 2/3] CryptoPkg/CryptLib: " IanX Kuo
2021-10-16 22:34 ` [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2 siblings, 2 replies; 10+ messages in thread
From: IanX Kuo @ 2021-10-16 22:34 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 | 115 +----------------
.../Library/UefiSortLib/UefiSortLib.c | 116 +-----------------
2 files changed, 8 insertions(+), 223 deletions(-)
diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec..0903943ee4 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);
+ Buffer
+ );
FreePool(Buffer);
return;
diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
index 46dc443638..29d8735c22 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);
+ Buffer
+ );
FreePool(Buffer);
return;
--
2.30.0.windows.1
^ permalink raw reply related [flat|nested] 10+ messages in thread
* [PATCH v3 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
2021-10-16 22:34 [PATCH v3 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-16 22:34 ` [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
@ 2021-10-16 22:34 ` IanX Kuo
2021-10-17 2:23 ` Yao, Jiewen
2021-10-16 22:34 ` [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2 siblings, 1 reply; 10+ messages in thread
From: IanX Kuo @ 2021-10-16 22:34 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..33ff0fcdb6 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, compare, Buffer);
free (Buffer);
return;
--
2.30.0.windows.1
^ permalink raw reply related [flat|nested] 10+ messages in thread
* [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
2021-10-16 22:34 [PATCH v3 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-16 22:34 ` [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-16 22:34 ` [PATCH v3 2/3] CryptoPkg/CryptLib: " IanX Kuo
@ 2021-10-16 22:34 ` IanX Kuo
2021-10-18 1:57 ` IanX Kuo
2021-10-18 3:42 ` Ni, Ray
2 siblings, 2 replies; 10+ messages in thread
From: IanX Kuo @ 2021-10-16 22:34 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 | 8 +++++++-
UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf | 2 --
.../Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 -
UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 --
4 files changed, 7 insertions(+), 6 deletions(-)
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
index c0077d6770..c7c72f68eb 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,12 @@ 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));
+ if (QuickSortBuffer == NULL) {
+ return EFI_OUT_OF_RESOURCES;
+ }
+
+ QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), 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] 10+ messages in thread
* Re: [PATCH v3 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
2021-10-16 22:34 ` [PATCH v3 2/3] CryptoPkg/CryptLib: " IanX Kuo
@ 2021-10-17 2:23 ` Yao, Jiewen
0 siblings, 0 replies; 10+ messages in thread
From: Yao, Jiewen @ 2021-10-17 2:23 UTC (permalink / raw)
To: Kuo, IanX, devel@edk2.groups.io
Cc: Chan, Amy, Ni, Ray, Wang, Jian J, Lu, XiaoyuX, Jiang, Guomin
Acked-by: Jiewen Yao <Jiewen.yao@intel.com>
> -----Original Message-----
> From: Kuo, IanX <ianx.kuo@intel.com>
> Sent: Sunday, October 17, 2021 6:34 AM
> To: devel@edk2.groups.io
> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kuo, IanX
> <ianx.kuo@intel.com>; Yao, Jiewen <jiewen.yao@intel.com>; Wang, Jian J
> <jian.j.wang@intel.com>; Lu, XiaoyuX <xiaoyux.lu@intel.com>; Jiang, Guomin
> <guomin.jiang@intel.com>
> Subject: [PATCH v3 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
>
> 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..33ff0fcdb6 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, compare, Buffer);
>
>
>
> free (Buffer);
>
> return;
>
> --
> 2.30.0.windows.1
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
2021-10-16 22:34 ` [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
@ 2021-10-18 1:57 ` IanX Kuo
2021-10-18 3:42 ` Ni, Ray
1 sibling, 0 replies; 10+ messages in thread
From: IanX Kuo @ 2021-10-18 1:57 UTC (permalink / raw)
To: devel@edk2.groups.io, Ni, Ray, Dong, Eric, Kumar, Rahul1; +Cc: Chan, Amy
@Dong, Eric, @Ni, Ray or @Kumar, Rahul1
Sorry to bother you.
May I get one of your approval for this patch ?
Thanks,
Ian Kuo
-----Original Message-----
From: Kuo, IanX <ianx.kuo@intel.com>
Sent: Sunday, October 17, 2021 6:34 AM
To: devel@edk2.groups.io
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kuo, IanX <ianx.kuo@intel.com>; Dong, Eric <eric.dong@intel.com>; Kumar, Rahul1 <rahul1.kumar@intel.com>
Subject: [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
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 | 8 +++++++-
UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf | 2 --
.../Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 -
UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 --
4 files changed, 7 insertions(+), 6 deletions(-)
diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c
index c0077d6770..c7c72f68eb 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,12 @@ 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));
+ if (QuickSortBuffer == NULL) {
+ return EFI_OUT_OF_RESOURCES;
+ }
+
+ QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), 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] 10+ messages in thread
* Re: [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
2021-10-16 22:34 ` [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
@ 2021-10-18 1:58 ` IanX Kuo
2021-10-18 2:50 ` 回复: [edk2-devel] " gaoliming
1 sibling, 0 replies; 10+ messages in thread
From: IanX Kuo @ 2021-10-18 1:58 UTC (permalink / raw)
To: devel@edk2.groups.io, Wang, Jian J, Liming Gao; +Cc: Chan, Amy, Ni, Ray
@Liming Gao or @Wang, Jian J
Sorry to bother you.
May I get one of your help to review the code change from maintainer side ?
Thanks,
Ian Kuo
-----Original Message-----
From: Kuo, IanX <ianx.kuo@intel.com>
Sent: Sunday, October 17, 2021 6:34 AM
To: devel@edk2.groups.io
Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kuo, IanX <ianx.kuo@intel.com>; Wang, Jian J <jian.j.wang@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>
Subject: [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
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 | 115 +----------------
.../Library/UefiSortLib/UefiSortLib.c | 116 +-----------------
2 files changed, 8 insertions(+), 223 deletions(-)
diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec..0903943ee4 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);
+ Buffer
+ );
FreePool(Buffer);
return;
diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
index 46dc443638..29d8735c22 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);
+ Buffer
+ );
FreePool(Buffer);
return;
--
2.30.0.windows.1
^ permalink raw reply related [flat|nested] 10+ messages in thread
* 回复: [edk2-devel] [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
2021-10-16 22:34 ` [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-18 1:58 ` IanX Kuo
@ 2021-10-18 2:50 ` gaoliming
1 sibling, 0 replies; 10+ messages in thread
From: gaoliming @ 2021-10-18 2:50 UTC (permalink / raw)
To: devel, ianx.kuo; +Cc: amy.chan, ray.ni, 'Jian J Wang'
Reviewed-by: Liming Gao <gaoliming@byosoft.com.cn>
> -----邮件原件-----
> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo
> 发送时间: 2021年10月17日 6:34
> 收件人: devel@edk2.groups.io
> 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo
> <ianx.kuo@intel.com>; Jian J Wang <jian.j.wang@intel.com>; Liming Gao
> <gaoliming@byosoft.com.cn>
> 主题: [edk2-devel] [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort
> function on BaseLib
>
> 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 | 115 +----------------
> .../Library/UefiSortLib/UefiSortLib.c | 116 +-----------------
> 2 files changed, 8 insertions(+), 223 deletions(-)
>
> diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
> b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
> index a12c7bc0ec..0903943ee4 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);
>
> + Buffer
>
> + );
>
>
>
> FreePool(Buffer);
>
> return;
>
> diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
> b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
> index 46dc443638..29d8735c22 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);
>
> + Buffer
>
> + );
>
>
>
> FreePool(Buffer);
>
> return;
>
> --
> 2.30.0.windows.1
>
>
>
> -=-=-=-=-=-=
> Groups.io Links: You receive all messages sent to this group.
> View/Reply Online (#82182): https://edk2.groups.io/g/devel/message/82182
> Mute This Topic: https://groups.io/mt/86381252/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] 10+ messages in thread
* Re: [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
2021-10-16 22:34 ` [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2021-10-18 1:57 ` IanX Kuo
@ 2021-10-18 3:42 ` Ni, Ray
2021-10-18 3:57 ` IanX Kuo
1 sibling, 1 reply; 10+ messages in thread
From: Ni, Ray @ 2021-10-18 3:42 UTC (permalink / raw)
To: Kuo, IanX, devel@edk2.groups.io; +Cc: Chan, Amy, Dong, Eric, Kumar, Rahul1
Ian,
Thanks for cleaning up the code to remove MdeModulePkg dependency.
Minor comments below:
UINTN NextIndex;
+ VOID *QuickSortBuffer;
1. Can you use local variable? "CPU_CACHE_INFO SortBuffer".
- PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare);
+ QuickSortBuffer = AllocateZeroPool (sizeof (*LocalCacheInfo));
+ if (QuickSortBuffer == NULL) {
+ return EFI_OUT_OF_RESOURCES;
+ }
2. With #1 change, you can avoid "calling AllocateZeroPool() and checking pointer".
+ QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), CpuCacheInfoCompare, QuickSortBuffer);
3. Just pass "&SortBuffer" as the last parameter.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
2021-10-18 3:42 ` Ni, Ray
@ 2021-10-18 3:57 ` IanX Kuo
0 siblings, 0 replies; 10+ messages in thread
From: IanX Kuo @ 2021-10-18 3:57 UTC (permalink / raw)
To: Ni, Ray, devel@edk2.groups.io; +Cc: Chan, Amy, Dong, Eric, Kumar, Rahul1
Thanks for the comment.
It will be taken care by V5 patch.
Thanks,
Ian Kuo
-----Original Message-----
From: Ni, Ray <ray.ni@intel.com>
Sent: Monday, October 18, 2021 11:42 AM
To: Kuo, IanX <ianx.kuo@intel.com>; devel@edk2.groups.io
Cc: Chan, Amy <amy.chan@intel.com>; Dong, Eric <eric.dong@intel.com>; Kumar, Rahul1 <rahul1.kumar@intel.com>
Subject: RE: [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
Ian,
Thanks for cleaning up the code to remove MdeModulePkg dependency.
Minor comments below:
UINTN NextIndex;
+ VOID *QuickSortBuffer;
1. Can you use local variable? "CPU_CACHE_INFO SortBuffer".
- PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare);
+ QuickSortBuffer = AllocateZeroPool (sizeof (*LocalCacheInfo));
+ if (QuickSortBuffer == NULL) {
+ return EFI_OUT_OF_RESOURCES;
+ }
2. With #1 change, you can avoid "calling AllocateZeroPool() and checking pointer".
+ QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), CpuCacheInfoCompare, QuickSortBuffer);
3. Just pass "&SortBuffer" as the last parameter.
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2021-10-18 3:57 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2021-10-16 22:34 [PATCH v3 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-16 22:34 ` [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-18 1:58 ` IanX Kuo
2021-10-18 2:50 ` 回复: [edk2-devel] " gaoliming
2021-10-16 22:34 ` [PATCH v3 2/3] CryptoPkg/CryptLib: " IanX Kuo
2021-10-17 2:23 ` Yao, Jiewen
2021-10-16 22:34 ` [PATCH v3 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2021-10-18 1:57 ` IanX Kuo
2021-10-18 3:42 ` Ni, Ray
2021-10-18 3:57 ` IanX Kuo
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox