[PATCH v2 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib


IanX Kuo
 

From: IanX Kuo <ianx.kuo@intel.com>

REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675

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=0D
Library used for sorting routines.=0D
=0D
- Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>=
=0D
+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>=
=0D
SPDX-License-Identifier: BSD-2-Clause-Patent=0D
=0D
**/=0D
@@ -13,114 +13,6 @@
#include <Library/MemoryAllocationLib.h>=0D
#include <Library/SortLib.h>=0D
=0D
-/**=0D
- Worker function for QuickSorting. This function is identical to Perform=
QuickSort,=0D
- except that is uses the pre-allocated buffer so the in place sorting doe=
s not need to=0D
- allocate and free buffers constantly.=0D
-=0D
- Each element must be equal sized.=0D
-=0D
- if BufferToSort is NULL, then ASSERT.=0D
- if CompareFunction is NULL, then ASSERT.=0D
- if Buffer is NULL, then ASSERT.=0D
-=0D
- if Count is < 2 then perform no action.=0D
- if Size is < 1 then perform no action.=0D
-=0D
- @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele=
ments=0D
- on return a buffer of sorted elements=0D
- @param[in] Count the number of elements in the buffer to s=
ort=0D
- @param[in] ElementSize Size of an element in bytes=0D
- @param[in] CompareFunction The function to call to perform the compa=
rison=0D
- of any 2 elements=0D
- @param[in] Buffer Buffer of size ElementSize for use in swa=
pping=0D
-**/=0D
-VOID=0D
-EFIAPI=0D
-QuickSortWorker (=0D
- IN OUT VOID *BufferToSort,=0D
- IN CONST UINTN Count,=0D
- IN CONST UINTN ElementSize,=0D
- IN SORT_COMPARE CompareFunction,=0D
- IN VOID *Buffer=0D
- )=0D
-{=0D
- VOID *Pivot;=0D
- UINTN LoopCount;=0D
- UINTN NextSwapLocation;=0D
-=0D
- ASSERT(BufferToSort !=3D NULL);=0D
- ASSERT(CompareFunction !=3D NULL);=0D
- ASSERT(Buffer !=3D NULL);=0D
-=0D
- if ( Count < 2=0D
- || ElementSize < 1=0D
- ){=0D
- return;=0D
- }=0D
-=0D
- NextSwapLocation =3D 0;=0D
-=0D
- //=0D
- // pick a pivot (we choose last element)=0D
- //=0D
- Pivot =3D ((UINT8*)BufferToSort+((Count-1)*ElementSize));=0D
-=0D
- //=0D
- // Now get the pivot such that all on "left" are below it=0D
- // and everything "right" are above it=0D
- //=0D
- for ( LoopCount =3D 0=0D
- ; LoopCount < Count -1=0D
- ; LoopCount++=0D
- ){=0D
- //=0D
- // if the element is less than the pivot=0D
- //=0D
- if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementS=
ize)),Pivot) <=3D 0){=0D
- //=0D
- // swap=0D
- //=0D
- CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize)=
, ElementSize);=0D
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8=
*)BufferToSort+((LoopCount)*ElementSize), ElementSize);=0D
- CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, Ele=
mentSize);=0D
-=0D
- //=0D
- // increment NextSwapLocation=0D
- //=0D
- NextSwapLocation++;=0D
- }=0D
- }=0D
- //=0D
- // swap pivot to it's final position (NextSwapLocaiton)=0D
- //=0D
- CopyMem (Buffer, Pivot, ElementSize);=0D
- CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Ele=
mentSize);=0D
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, El=
ementSize);=0D
-=0D
- //=0D
- // Now recurse on 2 paritial lists. neither of these will have the 'piv=
ot' element=0D
- // IE list is sorted left half, pivot element, sorted right half...=0D
- //=0D
- if (NextSwapLocation >=3D 2) {=0D
- QuickSortWorker(=0D
- BufferToSort,=0D
- NextSwapLocation,=0D
- ElementSize,=0D
- CompareFunction,=0D
- Buffer);=0D
- }=0D
-=0D
- if ((Count - NextSwapLocation - 1) >=3D 2) {=0D
- QuickSortWorker(=0D
- (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,=0D
- Count - NextSwapLocation - 1,=0D
- ElementSize,=0D
- CompareFunction,=0D
- Buffer);=0D
- }=0D
- return;=0D
-}=0D
/**=0D
Function to perform a Quick Sort alogrithm on a buffer of comparable ele=
ments.=0D
=0D
@@ -156,12 +48,13 @@ PerformQuickSort (
Buffer =3D AllocateZeroPool(ElementSize);=0D
ASSERT(Buffer !=3D NULL);=0D
=0D
- QuickSortWorker(=0D
+ QuickSort (=0D
BufferToSort,=0D
Count,=0D
ElementSize,=0D
CompareFunction,=0D
- Buffer);=0D
+ Buffer=0D
+ );=0D
=0D
FreePool(Buffer);=0D
return;=0D
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=0D
Library used for sorting routines.=0D
=0D
- Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>=
=0D
+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>=
=0D
SPDX-License-Identifier: BSD-2-Clause-Patent=0D
=0D
**/=0D
@@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollat=
ion =3D NULL;
} \=0D
}=0D
=0D
-/**=0D
- Worker function for QuickSorting. This function is identical to Perform=
QuickSort,=0D
- except that is uses the pre-allocated buffer so the in place sorting doe=
s not need to=0D
- allocate and free buffers constantly.=0D
-=0D
- Each element must be equal sized.=0D
-=0D
- if BufferToSort is NULL, then ASSERT.=0D
- if CompareFunction is NULL, then ASSERT.=0D
- if Buffer is NULL, then ASSERT.=0D
-=0D
- if Count is < 2 then perform no action.=0D
- if Size is < 1 then perform no action.=0D
-=0D
- @param[in, out] BufferToSort on call a Buffer of (possibly sorted) ele=
ments=0D
- on return a buffer of sorted elements=0D
- @param[in] Count the number of elements in the buffer to s=
ort=0D
- @param[in] ElementSize Size of an element in bytes=0D
- @param[in] CompareFunction The function to call to perform the compa=
rison=0D
- of any 2 elements=0D
- @param[in] Buffer Buffer of size ElementSize for use in swa=
pping=0D
-**/=0D
-VOID=0D
-EFIAPI=0D
-QuickSortWorker (=0D
- IN OUT VOID *BufferToSort,=0D
- IN CONST UINTN Count,=0D
- IN CONST UINTN ElementSize,=0D
- IN SORT_COMPARE CompareFunction,=0D
- IN VOID *Buffer=0D
- )=0D
-{=0D
- VOID *Pivot;=0D
- UINTN LoopCount;=0D
- UINTN NextSwapLocation;=0D
-=0D
- ASSERT(BufferToSort !=3D NULL);=0D
- ASSERT(CompareFunction !=3D NULL);=0D
- ASSERT(Buffer !=3D NULL);=0D
-=0D
- if ( Count < 2=0D
- || ElementSize < 1=0D
- ){=0D
- return;=0D
- }=0D
-=0D
- NextSwapLocation =3D 0;=0D
-=0D
- //=0D
- // pick a pivot (we choose last element)=0D
- //=0D
- Pivot =3D ((UINT8*)BufferToSort+((Count-1)*ElementSize));=0D
-=0D
- //=0D
- // Now get the pivot such that all on "left" are below it=0D
- // and everything "right" are above it=0D
- //=0D
- for ( LoopCount =3D 0=0D
- ; LoopCount < Count -1=0D
- ; LoopCount++=0D
- ){=0D
- //=0D
- // if the element is less than the pivot=0D
- //=0D
- if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementS=
ize)),Pivot) <=3D 0){=0D
- //=0D
- // swap=0D
- //=0D
- CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize)=
, ElementSize);=0D
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8=
*)BufferToSort+((LoopCount)*ElementSize), ElementSize);=0D
- CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, Ele=
mentSize);=0D
-=0D
- //=0D
- // increment NextSwapLocation=0D
- //=0D
- NextSwapLocation++;=0D
- }=0D
- }=0D
- //=0D
- // swap pivot to it's final position (NextSwapLocaiton)=0D
- //=0D
- CopyMem (Buffer, Pivot, ElementSize);=0D
- CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Ele=
mentSize);=0D
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, El=
ementSize);=0D
-=0D
- //=0D
- // Now recurse on 2 paritial lists. neither of these will have the 'piv=
ot' element=0D
- // IE list is sorted left half, pivot element, sorted right half...=0D
- //=0D
- if (NextSwapLocation >=3D 2) {=0D
- QuickSortWorker(=0D
- BufferToSort,=0D
- NextSwapLocation,=0D
- ElementSize,=0D
- CompareFunction,=0D
- Buffer);=0D
- }=0D
-=0D
- if ((Count - NextSwapLocation - 1) >=3D 2) {=0D
- QuickSortWorker(=0D
- (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,=0D
- Count - NextSwapLocation - 1,=0D
- ElementSize,=0D
- CompareFunction,=0D
- Buffer);=0D
- }=0D
-=0D
- return;=0D
-}=0D
/**=0D
Function to perform a Quick Sort alogrithm on a buffer of comparable ele=
ments.=0D
=0D
@@ -173,12 +64,13 @@ PerformQuickSort (
Buffer =3D AllocateZeroPool(ElementSize);=0D
ASSERT(Buffer !=3D NULL);=0D
=0D
- QuickSortWorker(=0D
+ QuickSort (=0D
BufferToSort,=0D
Count,=0D
ElementSize,=0D
CompareFunction,=0D
- Buffer);=0D
+ Buffer=0D
+ );=0D
=0D
FreePool(Buffer);=0D
return;=0D
--=20
2.30.0.windows.1