回复: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib


gaoliming
 

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]
-=-=-=-=-=-=