* [PATCH v6 0/3] Add function QuickSort into MdePkg/BaseLib
@ 2021-10-18 4:21 IanX Kuo
2021-10-18 4:21 ` [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
` (4 more replies)
0 siblings, 5 replies; 11+ messages in thread
From: IanX Kuo @ 2021-10-18 4:21 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)
2-2: Add cast (BASE_SORT_COMPARE) to prevent incompatible types (V6)
'function': incompatible types - from 'int (__cdecl *)(const void *,const void *)' to 'BASE_SORT_COMPARE'
3. CpuCacheInfoLib: Remove MdeModulePkg dependency
3-1: Drop cast (V2)
3-2: Add runtime check (V2)
3-3: Drop assert check (V3)
3-4: Remove allocate pool (V4)
3-5: Rename QuickSortBuffer to SortBuffer (V5)
3-6: Add cast (VOID*) cast to prevent incompatible types (V6)
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 | 3 +-
.../CpuCacheInfoLib/DxeCpuCacheInfoLib.inf | 2 -
.../CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 -
.../CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 -
7 files changed, 12 insertions(+), 319 deletions(-)
--
2.30.0.windows.1
^ permalink raw reply [flat|nested] 11+ messages in thread* [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib 2021-10-18 4:21 [PATCH v6 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo @ 2021-10-18 4:21 ` IanX Kuo 2021-10-20 3:20 ` Wang, Jian J 2021-10-18 4:21 ` [PATCH v6 2/3] CryptoPkg/CryptLib: " IanX Kuo ` (3 subsequent siblings) 4 siblings, 1 reply; 11+ messages in thread From: IanX Kuo @ 2021-10-18 4:21 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] 11+ messages in thread
* Re: [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib 2021-10-18 4:21 ` [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo @ 2021-10-20 3:20 ` Wang, Jian J 0 siblings, 0 replies; 11+ messages in thread From: Wang, Jian J @ 2021-10-20 3:20 UTC (permalink / raw) To: Kuo, IanX, devel@edk2.groups.io; +Cc: Chan, Amy, Ni, Ray, Liming Gao Reviewed-by: Jian J Wang <jian.j.wang@intel.com> Regards, Jian > -----Original Message----- > From: Kuo, IanX <ianx.kuo@intel.com> > Sent: Monday, October 18, 2021 12:21 PM > 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 v6 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 [flat|nested] 11+ messages in thread
* [PATCH v6 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib 2021-10-18 4:21 [PATCH v6 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo 2021-10-18 4:21 ` [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo @ 2021-10-18 4:21 ` IanX Kuo 2021-10-21 11:06 ` Guomin Jiang 2021-10-18 4:21 ` [PATCH v6 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo ` (2 subsequent siblings) 4 siblings, 1 reply; 11+ messages in thread From: IanX Kuo @ 2021-10-18 4:21 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] 11+ messages in thread
* Re: [PATCH v6 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib 2021-10-18 4:21 ` [PATCH v6 2/3] CryptoPkg/CryptLib: " IanX Kuo @ 2021-10-21 11:06 ` Guomin Jiang 0 siblings, 0 replies; 11+ messages in thread From: Guomin Jiang @ 2021-10-21 11:06 UTC (permalink / raw) To: Kuo, IanX, devel@edk2.groups.io Cc: Chan, Amy, Ni, Ray, Yao, Jiewen, Wang, Jian J, Lu, XiaoyuX Reviewed-by: Guomin Jiang <guomin.jiang@intel.com> > -----Original Message----- > From: Kuo, IanX <ianx.kuo@intel.com> > Sent: Monday, October 18, 2021 12:21 PM > 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 v6 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..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 [flat|nested] 11+ messages in thread
* [PATCH v6 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib 2021-10-18 4:21 [PATCH v6 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo 2021-10-18 4:21 ` [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo 2021-10-18 4:21 ` [PATCH v6 2/3] CryptoPkg/CryptLib: " IanX Kuo @ 2021-10-18 4:21 ` IanX Kuo 2021-10-19 1:59 ` Ni, Ray [not found] ` <16AF0531A156CE70.24927@groups.io> [not found] ` <16AF0531824632DE.13161@groups.io> 4 siblings, 1 reply; 11+ messages in thread From: IanX Kuo @ 2021-10-18 4:21 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 | 3 ++- UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf | 2 -- UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 - UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 -- 4 files changed, 2 insertions(+), 6 deletions(-) diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c index c0077d6770..f4fcee39e9 100644 --- a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c @@ -282,6 +282,7 @@ CpuCacheInfoCollectCpuCacheInfoData ( UINTN LocalCacheInfoCount; UINTN Index; UINTN NextIndex; + CPU_CACHE_INFO SortBuffer; // // Get number of Packages and Package ID. @@ -369,7 +370,7 @@ CpuCacheInfoCollectCpuCacheInfoData ( // // Sort LocalCacheInfo array by CPU package ID, core type, cache level and cache type. // - PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare); + QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), CpuCacheInfoCompare, (VOID*) &SortBuffer); 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] 11+ messages in thread
* Re: [PATCH v6 3/3] UefiCpuPkg/CpuCacheInfoLib: Add QuickSort function on BaseLib 2021-10-18 4:21 ` [PATCH v6 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo @ 2021-10-19 1:59 ` Ni, Ray 0 siblings, 0 replies; 11+ messages in thread From: Ni, Ray @ 2021-10-19 1:59 UTC (permalink / raw) To: Kuo, IanX, devel@edk2.groups.io; +Cc: Chan, Amy, Dong, Eric, Kumar, Rahul1 Reviewed-by: Ray Ni <ray.ni@intel.com> -----Original Message----- From: Kuo, IanX <ianx.kuo@intel.com> Sent: Monday, October 18, 2021 12:21 PM 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 v6 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 | 3 ++- UefiCpuPkg/Library/CpuCacheInfoLib/DxeCpuCacheInfoLib.inf | 2 -- UefiCpuPkg/Library/CpuCacheInfoLib/InternalCpuCacheInfoLib.h | 1 - UefiCpuPkg/Library/CpuCacheInfoLib/PeiCpuCacheInfoLib.inf | 2 -- 4 files changed, 2 insertions(+), 6 deletions(-) diff --git a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c index c0077d6770..f4fcee39e9 100644 --- a/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c +++ b/UefiCpuPkg/Library/CpuCacheInfoLib/CpuCacheInfoLib.c @@ -282,6 +282,7 @@ CpuCacheInfoCollectCpuCacheInfoData ( UINTN LocalCacheInfoCount; UINTN Index; UINTN NextIndex; + CPU_CACHE_INFO SortBuffer; // // Get number of Packages and Package ID. @@ -369,7 +370,7 @@ CpuCacheInfoCollectCpuCacheInfoData ( // // Sort LocalCacheInfo array by CPU package ID, core type, cache level and cache type. // - PerformQuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), (SORT_COMPARE) CpuCacheInfoCompare); + QuickSort (LocalCacheInfo, LocalCacheInfoCount, sizeof (*LocalCacheInfo), CpuCacheInfoCompare, (VOID*) &SortBuffer); 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] 11+ messages in thread
[parent not found: <16AF0531A156CE70.24927@groups.io>]
* Re: [edk2-devel] [PATCH v6 2/3] CryptoPkg/CryptLib: Add QuickSort function on BaseLib [not found] ` <16AF0531A156CE70.24927@groups.io> @ 2021-10-19 2:08 ` IanX Kuo 0 siblings, 0 replies; 11+ messages in thread From: IanX Kuo @ 2021-10-19 2:08 UTC (permalink / raw) To: devel@edk2.groups.io, Kuo, IanX, Yao, Jiewen, Jiang, Guomin Cc: Chan, Amy, Ni, Ray, Wang, Jian J, Lu, XiaoyuX @Yao, Jiewen and @Jiang, Guomin Sorry to bother you. May I get your help for review-by ? Thanks, Ian Kuo -----Original Message----- From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of IanX Kuo Sent: Monday, October 18, 2021 12:21 PM 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: [edk2-devel] [PATCH v6 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..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 -=-=-=-=-=-= Groups.io Links: You receive all messages sent to this group. View/Reply Online (#82206): https://edk2.groups.io/g/devel/message/82206 Mute This Topic: https://groups.io/mt/86406845/4830160 Group Owner: devel+owner@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [ianx.kuo@intel.com] -=-=-=-=-=-= ^ permalink raw reply related [flat|nested] 11+ messages in thread
[parent not found: <16AF0531824632DE.13161@groups.io>]
* Re: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib [not found] ` <16AF0531824632DE.13161@groups.io> @ 2021-10-19 2:09 ` IanX Kuo 2021-10-20 1:49 ` 回复: " gaoliming 0 siblings, 1 reply; 11+ messages in thread From: IanX Kuo @ 2021-10-19 2:09 UTC (permalink / raw) To: devel@edk2.groups.io, Kuo, IanX, Liming Gao Cc: Chan, Amy, Ni, Ray, Wang, Jian J @Liming Gao Sorry to bother you. May I get your help for review by again ? Thanks, Ian Kuo -----Original Message----- From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of IanX Kuo Sent: Monday, October 18, 2021 12:21 PM 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: [edk2-devel] [PATCH v6 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 (#82204): https://edk2.groups.io/g/devel/message/82204 Mute This Topic: https://groups.io/mt/86406843/4830160 Group Owner: devel+owner@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [ianx.kuo@intel.com] -=-=-=-=-=-= ^ permalink raw reply related [flat|nested] 11+ messages in thread
* 回复: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib 2021-10-19 2:09 ` [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: " IanX Kuo @ 2021-10-20 1:49 ` gaoliming 2021-10-20 5:45 ` IanX Kuo 0 siblings, 1 reply; 11+ messages in thread From: gaoliming @ 2021-10-20 1:49 UTC (permalink / raw) To: 'Kuo, IanX', devel Cc: 'Chan, Amy', 'Ni, Ray', 'Wang, Jian J' What new change is made in new version patch? Thanks Liming > -----邮件原件----- > 发件人: Kuo, IanX <ianx.kuo@intel.com> > 发送时间: 2021年10月19日 10:09 > 收件人: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>; Liming Gao > <gaoliming@byosoft.com.cn> > 抄送: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Wang, > Jian J <jian.j.wang@intel.com> > 主题: RE: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add > QuickSort function on BaseLib > > @Liming Gao > > Sorry to bother you. May I get your help for review by again ? > > Thanks, > Ian Kuo > > -----Original Message----- > From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of IanX Kuo > Sent: Monday, October 18, 2021 12:21 PM > 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: [edk2-devel] [PATCH v6 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 (#82204): https://edk2.groups.io/g/devel/message/82204 > Mute This Topic: https://groups.io/mt/86406843/4830160 > Group Owner: devel+owner@edk2.groups.io > Unsubscribe: https://edk2.groups.io/g/devel/unsub [ianx.kuo@intel.com] > -=-=-=-=-=-= > ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib 2021-10-20 1:49 ` 回复: " gaoliming @ 2021-10-20 5:45 ` IanX Kuo 0 siblings, 0 replies; 11+ messages in thread From: IanX Kuo @ 2021-10-20 5:45 UTC (permalink / raw) To: devel@edk2.groups.io, gaoliming@byosoft.com.cn Cc: Chan, Amy, Ni, Ray, Wang, Jian J Hi Liming The change "PATCH v6 1/3" is the same with "PATCH v3 1/3". The difference between "v3 to v6" is on "PATCH v6 3/3" Thanks, Ian Kuo -----Original Message----- From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming Sent: Wednesday, October 20, 2021 9:50 AM To: Kuo, IanX <ianx.kuo@intel.com>; devel@edk2.groups.io Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Wang, Jian J <jian.j.wang@intel.com> Subject: 回复: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib What new change is made in new version patch? Thanks Liming > -----邮件原件----- > 发件人: Kuo, IanX <ianx.kuo@intel.com> > 发送时间: 2021年10月19日 10:09 > 收件人: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com>; Liming Gao > <gaoliming@byosoft.com.cn> > 抄送: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Wang, > Jian J <jian.j.wang@intel.com> > 主题: RE: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add > QuickSort function on BaseLib > > @Liming Gao > > Sorry to bother you. May I get your help for review by again ? > > Thanks, > Ian Kuo > > -----Original Message----- > From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of IanX > Kuo > Sent: Monday, October 18, 2021 12:21 PM > 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: [edk2-devel] [PATCH v6 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 (#82204): > https://edk2.groups.io/g/devel/message/82204 > Mute This Topic: https://groups.io/mt/86406843/4830160 > Group Owner: devel+owner@edk2.groups.io > Unsubscribe: https://edk2.groups.io/g/devel/unsub [ianx.kuo@intel.com] > -=-=-=-=-=-= > ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2021-10-21 11:06 UTC | newest]
Thread overview: 11+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2021-10-18 4:21 [PATCH v6 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-18 4:21 ` [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-20 3:20 ` Wang, Jian J
2021-10-18 4:21 ` [PATCH v6 2/3] CryptoPkg/CryptLib: " IanX Kuo
2021-10-21 11:06 ` Guomin Jiang
2021-10-18 4:21 ` [PATCH v6 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2021-10-19 1:59 ` Ni, Ray
[not found] ` <16AF0531A156CE70.24927@groups.io>
2021-10-19 2:08 ` [edk2-devel] [PATCH v6 2/3] CryptoPkg/CryptLib: " IanX Kuo
[not found] ` <16AF0531824632DE.13161@groups.io>
2021-10-19 2:09 ` [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: " IanX Kuo
2021-10-20 1:49 ` 回复: " gaoliming
2021-10-20 5:45 ` IanX Kuo
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox