* [PATCH v4 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib
2021-10-04 4:46 [PATCH v4 0/4] Add function QuickSort into MdePkg/BaseLib IanX Kuo
@ 2021-10-04 4:46 ` IanX Kuo
2021-10-04 4:46 ` [PATCH v4 2/4] MdeModulePkg/SortLib: " IanX Kuo
` (2 subsequent siblings)
3 siblings, 0 replies; 5+ messages in thread
From: IanX Kuo @ 2021-10-04 4:46 UTC (permalink / raw)
To: devel
Cc: amy.chan, ray.ni, IanX Kuo, Michael D Kinney, Liming Gao,
Zhiguang Liu
From: IanX Kuo <ianx.kuo@intel.com>
REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675
Add QuickSort function into BaseLib
Cc: Ray Ni <ray.ni@intel.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
MdePkg/Include/Library/BaseLib.h | 49 ++++++++
MdePkg/Library/BaseLib/BaseLib.inf | 1 +
MdePkg/Library/BaseLib/QuickSort.c | 117 ++++++++++++++++++
.../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +-
4 files changed, 169 insertions(+), 1 deletion(-)
create mode 100644 MdePkg/Library/BaseLib/QuickSort.c
diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/BaseLib.h
index 2452c1d92e..2423169be4 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -13,6 +13,7 @@ SPDX-License-Identifier: BSD-2-Clause-Patent
#ifndef __BASE_LIB__
#define __BASE_LIB__
+#include <Uefi/UefiBaseType.h>
//
// Definitions for architecture-specific types
@@ -2856,6 +2857,54 @@ RemoveEntryList (
//
// Math Services
//
+/**
+ Prototype for comparison function for any two element types.
+
+ @param[in] Buffer1 The pointer to first buffer.
+ @param[in] Buffer2 The pointer to second buffer.
+
+ @retval 0 Buffer1 equal to Buffer2.
+ @return <0 Buffer1 is less than Buffer2.
+ @return >0 Buffer1 is greater than Buffer2.
+**/
+typedef
+INTN
+(EFIAPI *BASE_SORT_COMPARE)(
+ IN CONST VOID *Buffer1,
+ IN CONST VOID *Buffer2
+ );
+
+/**
+ Worker function for QuickSorting. This function is identical to perform QuickSort,
+ except that is uses the pre-allocated buffer so the in place sorting does not need to
+ allocate and free buffers constantly.
+
+ Each element must be equal sized.
+
+ if 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] BufferOneElement Caller provided buffer whose size equals to ElementSize.
+ It's used by QuickSort() for swapping in sorting.
+
+ @retval EFI_SUCCESS The quick sort is finished.
+ @retval EFI_INVALID_PARAMETER When BufferToSort is NULL, CompareFunction is NULL or Buffer is NULL
+**/
+EFI_STATUS
+EFIAPI
+QuickSort (
+ IN OUT VOID *BufferToSort,
+ IN CONST UINTN Count,
+ IN CONST UINTN ElementSize,
+ IN BASE_SORT_COMPARE CompareFunction,
+ IN VOID *BufferOneElement
+ );
/**
Shifts a 64-bit integer left between 0 and 63 bits. The low bits are filled
diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/BaseLib.inf
index 6efa5315b6..cebda3b210 100644
--- a/MdePkg/Library/BaseLib/BaseLib.inf
+++ b/MdePkg/Library/BaseLib/BaseLib.inf
@@ -32,6 +32,7 @@
SwapBytes16.c
LongJump.c
SetJump.c
+ QuickSort.c
RShiftU64.c
RRotU64.c
RRotU32.c
diff --git a/MdePkg/Library/BaseLib/QuickSort.c b/MdePkg/Library/BaseLib/QuickSort.c
new file mode 100644
index 0000000000..f95af9e238
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,117 @@
+/** @file
+ Math worker functions.
+
+ Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
+ SPDX-License-Identifier: BSD-2-Clause-Patent
+
+**/
+
+#include "BaseLibInternals.h"
+#include <Uefi/UefiBaseType.h>
+
+/**
+ Worker function for QuickSorting. This function is identical to perform QuickSort,
+ except that is uses the pre-allocated buffer so the in place sorting does not need to
+ allocate and free buffers constantly.
+
+ Each element must be equal sized.
+
+ if 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] BufferOneElement Caller provided buffer whose size equals to ElementSize.
+ It's used by QuickSort() for swapping in sorting.
+
+ @retval EFI_SUCCESS The quick sort is finished.
+ @retval EFI_INVALID_PARAMETER When BufferToSort is NULL, CompareFunction is NULL, or BufferOneElement is NULL
+
+**/
+EFI_STATUS
+EFIAPI
+QuickSort (
+ IN OUT VOID *BufferToSort,
+ IN CONST UINTN Count,
+ IN CONST UINTN ElementSize,
+ IN BASE_SORT_COMPARE CompareFunction,
+ IN VOID *BufferOneElement
+ )
+{
+ VOID *Pivot;
+ UINTN LoopCount;
+ UINTN NextSwapLocation;
+
+ if ((BufferToSort == NULL) || (CompareFunction == NULL) || (BufferOneElement == NULL)) {
+ return EFI_INVALID_PARAMETER;
+ }
+
+ if (Count < 2 || ElementSize < 1) {
+ return EFI_SUCCESS;
+ }
+
+ 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 (BufferOneElement, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize);
+ CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, ElementSize);
+
+ //
+ // increment NextSwapLocation
+ //
+ NextSwapLocation++;
+ }
+ }
+ //
+ // swap pivot to it's final position (NextSwapLocation)
+ //
+ CopyMem (BufferOneElement, Pivot, ElementSize);
+ CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
+ CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), BufferOneElement, ElementSize);
+
+ //
+ // Now recurse on 2 partial lists. neither of these will have the 'pivot' element
+ // IE list is sorted left half, pivot element, sorted right half...
+ //
+ if (NextSwapLocation >= 2) {
+ QuickSort (
+ BufferToSort,
+ NextSwapLocation,
+ ElementSize,
+ CompareFunction,
+ BufferOneElement
+ );
+ }
+
+ if ((Count - NextSwapLocation - 1) >= 2) {
+ QuickSort (
+ (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
+ Count - NextSwapLocation - 1,
+ ElementSize,
+ CompareFunction,
+ BufferOneElement
+ );
+ }
+ return EFI_SUCCESS;
+}
diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
index eae1a7158d..d09bd12bef 100644
--- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
+++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
@@ -1,7 +1,7 @@
## @file
# Base Library implementation for use with host based unit tests.
#
-# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.<BR>
+# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR>
# Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR>
# Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR>
# Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All rights reserved.<BR>
@@ -33,6 +33,7 @@
SwapBytes16.c
LongJump.c
SetJump.c
+ QuickSort.c
RShiftU64.c
RRotU64.c
RRotU32.c
--
2.30.0.windows.1
^ permalink raw reply related [flat|nested] 5+ messages in thread* [PATCH v4 2/4] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
2021-10-04 4:46 [PATCH v4 0/4] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-04 4:46 ` [PATCH v4 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo
@ 2021-10-04 4:46 ` IanX Kuo
2021-10-04 4:46 ` [PATCH v4 3/4] CryptoPkg/CryptLib: " IanX Kuo
2021-10-04 4:46 ` [PATCH v4 4/4] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
3 siblings, 0 replies; 5+ messages in thread
From: IanX Kuo @ 2021-10-04 4:46 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] 5+ messages in thread* [PATCH v4 3/4] CryptoPkg/CryptLib: Add QuickSort function on BaseLib
2021-10-04 4:46 [PATCH v4 0/4] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-04 4:46 ` [PATCH v4 1/4] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-04 4:46 ` [PATCH v4 2/4] MdeModulePkg/SortLib: " IanX Kuo
@ 2021-10-04 4:46 ` IanX Kuo
2021-10-04 4:46 ` [PATCH v4 4/4] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
3 siblings, 0 replies; 5+ messages in thread
From: IanX Kuo @ 2021-10-04 4:46 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..bdcd8ec278 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, (SORT_COMPARE)compare, Buffer);
free (Buffer);
return;
--
2.30.0.windows.1
^ permalink raw reply related [flat|nested] 5+ messages in thread* [PATCH v4 4/4] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib
2021-10-04 4:46 [PATCH v4 0/4] Add function QuickSort into MdePkg/BaseLib IanX Kuo
` (2 preceding siblings ...)
2021-10-04 4:46 ` [PATCH v4 3/4] CryptoPkg/CryptLib: " IanX Kuo
@ 2021-10-04 4:46 ` IanX Kuo
3 siblings, 0 replies; 5+ messages in thread
From: IanX Kuo @ 2021-10-04 4:46 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 | 2 --
UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 --
4 files changed, 4 insertions(+), 7 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..af60588e34 100644
--- a/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
+++ b/UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h
@@ -13,11 +13,9 @@
#include <Register/Cpuid.h>
#include <Ppi/MpServices2.h>
#include <Protocol/MpService.h>
-#include <Library/BaseLib.h>
#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] 5+ messages in thread