[PATCH v1 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 | 117 +----------------
.../Library/UefiSortLib/UefiSortLib.c | 118 +-----------------
2 files changed, 10 insertions(+), 225 deletions(-)

diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/=
Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec..b33339ac7c 100644
--- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
+++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
@@ -1,7 +1,7 @@
/** @file=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
+ (SORT_COMPARE) CompareFunction,=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..151a5a9ac3 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
+ (SORT_COMPARE) CompareFunction,=0D
+ Buffer=0D
+ );=0D
=0D
FreePool(Buffer);=0D
return;=0D
--=20
2.30.0.windows.1


Marvin Häuser
 

Good day Ianx,

On 15.10.21 16:33, IanX Kuo wrote:
From: IanX Kuo <ianx.kuo@intel.com>

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

Use QuickSort instead of QuickSortWorker

Cc: Ray Ni <ray.ni@intel.com>
Cc: Jian J Wang <jian.j.wang@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
.../Library/BaseSortLib/BaseSortLib.c | 117 +----------------
.../Library/UefiSortLib/UefiSortLib.c | 118 +-----------------
2 files changed, 10 insertions(+), 225 deletions(-)

diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
index a12c7bc0ec..b33339ac7c 100644
--- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
+++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c
@@ -1,7 +1,7 @@
/** @file
Library used for sorting routines.
- Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>
+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
SPDX-License-Identifier: BSD-2-Clause-Patent
**/
@@ -13,114 +13,6 @@
#include <Library/MemoryAllocationLib.h>
#include <Library/SortLib.h>
-/**
- Worker function for QuickSorting. This function is identical to PerformQuickSort,
- except that is uses the pre-allocated buffer so the in place sorting does not need to
- allocate and free buffers constantly.
-
- Each element must be equal sized.
-
- if BufferToSort is NULL, then ASSERT.
- if CompareFunction is NULL, then ASSERT.
- if Buffer is NULL, then ASSERT.
-
- if Count is < 2 then perform no action.
- if Size is < 1 then perform no action.
-
- @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
- on return a buffer of sorted elements
- @param[in] Count the number of elements in the buffer to sort
- @param[in] ElementSize Size of an element in bytes
- @param[in] CompareFunction The function to call to perform the comparison
- of any 2 elements
- @param[in] Buffer Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-QuickSortWorker (
- IN OUT VOID *BufferToSort,
- IN CONST UINTN Count,
- IN CONST UINTN ElementSize,
- IN SORT_COMPARE CompareFunction,
- IN VOID *Buffer
- )
-{
- VOID *Pivot;
- UINTN LoopCount;
- UINTN NextSwapLocation;
-
- ASSERT(BufferToSort != NULL);
- ASSERT(CompareFunction != NULL);
- ASSERT(Buffer != NULL);
-
- if ( Count < 2
- || ElementSize < 1
- ){
- return;
- }
-
- NextSwapLocation = 0;
-
- //
- // pick a pivot (we choose last element)
- //
- Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));
-
- //
- // Now get the pivot such that all on "left" are below it
- // and everything "right" are above it
- //
- for ( LoopCount = 0
- ; LoopCount < Count -1
- ; LoopCount++
- ){
- //
- // if the element is less than the pivot
- //
- if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
- //
- // swap
- //
- CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
-
- //
- // increment NextSwapLocation
- //
- NextSwapLocation++;
- }
- }
- //
- // swap pivot to it's final position (NextSwapLocaiton)
- //
- CopyMem (Buffer, Pivot, ElementSize);
- CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
- //
- // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
- // IE list is sorted left half, pivot element, sorted right half...
- //
- if (NextSwapLocation >= 2) {
- QuickSortWorker(
- BufferToSort,
- NextSwapLocation,
- ElementSize,
- CompareFunction,
- Buffer);
- }
-
- if ((Count - NextSwapLocation - 1) >= 2) {
- QuickSortWorker(
- (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
- Count - NextSwapLocation - 1,
- ElementSize,
- CompareFunction,
- Buffer);
- }
- return;
-}
/**
Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
@@ -156,12 +48,13 @@ PerformQuickSort (
Buffer = AllocateZeroPool(ElementSize);
ASSERT(Buffer != NULL);
- QuickSortWorker(
+ QuickSort (
BufferToSort,
Count,
ElementSize,
- CompareFunction,
- Buffer);
+ (SORT_COMPARE) CompareFunction,
CLANGPDB and GCC5 do not need this cast; I cannot easily test MSVC right now. Does it compile fine for you with the cast dropped? Dropping the cast gives us compile-time checking for actual type-compatibility.

+ Buffer
+ );
FreePool(Buffer);
return;
diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
index 46dc443638..151a5a9ac3 100644
--- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
+++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c
@@ -1,7 +1,7 @@
/** @file
Library used for sorting routines.
- Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>
+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
SPDX-License-Identifier: BSD-2-Clause-Patent
**/
@@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation = NULL;
} \
}
-/**
- Worker function for QuickSorting. This function is identical to PerformQuickSort,
- except that is uses the pre-allocated buffer so the in place sorting does not need to
- allocate and free buffers constantly.
-
- Each element must be equal sized.
-
- if BufferToSort is NULL, then ASSERT.
- if CompareFunction is NULL, then ASSERT.
- if Buffer is NULL, then ASSERT.
-
- if Count is < 2 then perform no action.
- if Size is < 1 then perform no action.
-
- @param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements
- on return a buffer of sorted elements
- @param[in] Count the number of elements in the buffer to sort
- @param[in] ElementSize Size of an element in bytes
- @param[in] CompareFunction The function to call to perform the comparison
- of any 2 elements
- @param[in] Buffer Buffer of size ElementSize for use in swapping
-**/
-VOID
-EFIAPI
-QuickSortWorker (
- IN OUT VOID *BufferToSort,
- IN CONST UINTN Count,
- IN CONST UINTN ElementSize,
- IN SORT_COMPARE CompareFunction,
- IN VOID *Buffer
- )
-{
- VOID *Pivot;
- UINTN LoopCount;
- UINTN NextSwapLocation;
-
- ASSERT(BufferToSort != NULL);
- ASSERT(CompareFunction != NULL);
- ASSERT(Buffer != NULL);
-
- if ( Count < 2
- || ElementSize < 1
- ){
- return;
- }
-
- NextSwapLocation = 0;
-
- //
- // pick a pivot (we choose last element)
- //
- Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));
-
- //
- // Now get the pivot such that all on "left" are below it
- // and everything "right" are above it
- //
- for ( LoopCount = 0
- ; LoopCount < Count -1
- ; LoopCount++
- ){
- //
- // if the element is less than the pivot
- //
- if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
- //
- // swap
- //
- CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
-
- //
- // increment NextSwapLocation
- //
- NextSwapLocation++;
- }
- }
- //
- // swap pivot to it's final position (NextSwapLocaiton)
- //
- CopyMem (Buffer, Pivot, ElementSize);
- CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
- CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
-
- //
- // Now recurse on 2 paritial lists. neither of these will have the 'pivot' element
- // IE list is sorted left half, pivot element, sorted right half...
- //
- if (NextSwapLocation >= 2) {
- QuickSortWorker(
- BufferToSort,
- NextSwapLocation,
- ElementSize,
- CompareFunction,
- Buffer);
- }
-
- if ((Count - NextSwapLocation - 1) >= 2) {
- QuickSortWorker(
- (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
- Count - NextSwapLocation - 1,
- ElementSize,
- CompareFunction,
- Buffer);
- }
-
- return;
-}
/**
Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
@@ -173,12 +64,13 @@ PerformQuickSort (
Buffer = AllocateZeroPool(ElementSize);
ASSERT(Buffer != NULL);
- QuickSortWorker(
+ QuickSort (
BufferToSort,
Count,
ElementSize,
- CompareFunction,
- Buffer);
+ (SORT_COMPARE) CompareFunction,
See above.

Best regards,
Marvin

+ Buffer
+ );
FreePool(Buffer);
return;


IanX Kuo
 

@Marvin Häuser

Thank to catch it. I dropped it on my patch v2.

Compiler

Status

Linux GCC5 (gcc 10.2.0/9.3.0/8.4.0/7.5.0/5.5.0/5.4.0)

Pass

Windows CLANGPDB (clang 12.0.0), Linux CLANGPDB (clang 12.0.0)

Pass

Windows MSVC (VS2015/VS2017/VS2019)

Pass

Mac XCODE5 (clang 11.0.0)

Pass

 

 

Thanks,
Ian Kuo

-----Original Message-----
From: Marvin Häuser <mhaeuser@...>
Sent: Saturday, October 16, 2021 3:11 AM
To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@...>
Cc: Chan, Amy <amy.chan@...>; Ni, Ray <ray.ni@...>; Wang, Jian J <jian.j.wang@...>; Liming Gao <gaoliming@...>
Subject: Re: [edk2-devel] [PATCH v1 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib

 

Good day Ianx,

 

On 15.10.21 16:33, IanX Kuo wrote:

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

> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675

> Use QuickSort instead of QuickSortWorker

> Cc: Ray Ni <ray.ni@...>

> Cc: Jian J Wang <jian.j.wang@...>

> Cc: Liming Gao <gaoliming@...>

> Signed-off-by: IanX Kuo <ianx.kuo@...>

> ---

>   .../Library/BaseSortLib/BaseSortLib.c         | 117 +----------------

>   .../Library/UefiSortLib/UefiSortLib.c         | 118 +-----------------

>   2 files changed, 10 insertions(+), 225 deletions(-)

> diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c

> b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c

> index a12c7bc0ec..b33339ac7c 100644

> --- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c

> +++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c

> @@ -1,7 +1,7 @@

>   /** @file

>     Library used for sorting routines.

>  

> -  Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved.

> <BR>

> +  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.

> + <BR>

>     SPDX-License-Identifier: BSD-2-Clause-Patent

>  

>   **/

> @@ -13,114 +13,6 @@

>   #include <Library/MemoryAllocationLib.h>

>   #include <Library/SortLib.h>

>  

> -/**

> -  Worker function for QuickSorting.  This function is identical to

> PerformQuickSort,

> -  except that is uses the pre-allocated buffer so the in place

> sorting does not need to

> -  allocate and free buffers constantly.

> -

> -  Each element must be equal sized.

> -

> -  if BufferToSort is NULL, then ASSERT.

> -  if CompareFunction is NULL, then ASSERT.

> -  if Buffer is NULL, then ASSERT.

> -

> -  if Count is < 2 then perform no action.

> -  if Size is < 1 then perform no action.

> -

> -  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements

> -                                 on return a buffer of sorted elements

> -  @param[in] Count               the number of elements in the buffer to sort

> -  @param[in] ElementSize         Size of an element in bytes

> -  @param[in] CompareFunction     The function to call to perform the comparison

> -                                 of any 2 elements

> -  @param[in] Buffer              Buffer of size ElementSize for use in swapping

> -**/

> -VOID

> -EFIAPI

> -QuickSortWorker (

> -  IN OUT VOID                           *BufferToSort,

> -  IN CONST UINTN                        Count,

> -  IN CONST UINTN                        ElementSize,

> -  IN       SORT_COMPARE                 CompareFunction,

> -  IN VOID                               *Buffer

> -  )

> -{

> -  VOID        *Pivot;

> -  UINTN       LoopCount;

> -  UINTN       NextSwapLocation;

> -

> -  ASSERT(BufferToSort     != NULL);

> -  ASSERT(CompareFunction  != NULL);

> -  ASSERT(Buffer  != NULL);

> -

> -  if ( Count < 2

> -    || ElementSize  < 1

> -   ){

> -    return;

> -  }

> -

> -  NextSwapLocation = 0;

> -

> -  //

> -  // pick a pivot (we choose last element)

> -  //

> -  Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));

> -

> -  //

> -  // Now get the pivot such that all on "left" are below it

> -  // and everything "right" are above it

> -  //

> -  for ( LoopCount = 0

> -      ; LoopCount < Count -1

> -      ; LoopCount++

> -     ){

> -    //

> -    // if the element is less than the pivot

> -    //

> -    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){

> -      //

> -      // swap

> -      //

> -      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);

> -      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);

> -      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);

> -

> -      //

> -      // increment NextSwapLocation

> -      //

> -      NextSwapLocation++;

> -    }

> -  }

> -  //

> -  // swap pivot to it's final position (NextSwapLocaiton)

> -  //

> -  CopyMem (Buffer, Pivot, ElementSize);

> -  CopyMem (Pivot,

> (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);

> -  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize),

> Buffer, ElementSize);

> -

> -  //

> -  // Now recurse on 2 paritial lists.  neither of these will have the

> 'pivot' element

> -  // IE list is sorted left half, pivot element, sorted right half...

> -  //

> -  if (NextSwapLocation >= 2) {

> -    QuickSortWorker(

> -      BufferToSort,

> -      NextSwapLocation,

> -      ElementSize,

> -      CompareFunction,

> -      Buffer);

> -  }

> -

> -  if ((Count - NextSwapLocation - 1) >= 2) {

> -    QuickSortWorker(

> -      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,

> -      Count - NextSwapLocation - 1,

> -      ElementSize,

> -      CompareFunction,

> -      Buffer);

> -  }

> -  return;

> -}

>   /**

>     Function to perform a Quick Sort alogrithm on a buffer of comparable elements.

>  

> @@ -156,12 +48,13 @@ PerformQuickSort (

>     Buffer = AllocateZeroPool(ElementSize);

>     ASSERT(Buffer != NULL);

>  

> -  QuickSortWorker(

> +  QuickSort (

>       BufferToSort,

>       Count,

>       ElementSize,

> -    CompareFunction,

> -    Buffer);

> +    (SORT_COMPARE) CompareFunction,

 

CLANGPDB and GCC5 do not need this cast; I cannot easily test MSVC right now. Does it compile fine for you with the cast dropped? Dropping the cast gives us compile-time checking for actual type-compatibility.

 

> +    Buffer

> +    );

>  

>     FreePool(Buffer);

>     return;

> diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c

> b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c

> index 46dc443638..151a5a9ac3 100644

> --- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c

> +++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c

> @@ -1,7 +1,7 @@

>   /** @file

>     Library used for sorting routines.

>  

> -  Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved.

> <BR>

> +  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.

> + <BR>

>     SPDX-License-Identifier: BSD-2-Clause-Patent

>  

>   **/

> @@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL   *mUnicodeCollation = NULL;

>     }                                   \

>   }

>  

> -/**

> -  Worker function for QuickSorting.  This function is identical to

> PerformQuickSort,

> -  except that is uses the pre-allocated buffer so the in place

> sorting does not need to

> -  allocate and free buffers constantly.

> -

> -  Each element must be equal sized.

> -

> -  if BufferToSort is NULL, then ASSERT.

> -  if CompareFunction is NULL, then ASSERT.

> -  if Buffer is NULL, then ASSERT.

> -

> -  if Count is < 2 then perform no action.

> -  if Size is < 1 then perform no action.

> -

> -  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements

> -                                 on return a buffer of sorted elements

> -  @param[in] Count               the number of elements in the buffer to sort

> -  @param[in] ElementSize         Size of an element in bytes

> -  @param[in] CompareFunction     The function to call to perform the comparison

> -                                 of any 2 elements

> -  @param[in] Buffer              Buffer of size ElementSize for use in swapping

> -**/

> -VOID

> -EFIAPI

> -QuickSortWorker (

> -  IN OUT VOID                           *BufferToSort,

> -  IN CONST UINTN                        Count,

> -  IN CONST UINTN                        ElementSize,

> -  IN       SORT_COMPARE                 CompareFunction,

> -  IN VOID                               *Buffer

> -  )

> -{

> -  VOID        *Pivot;

> -  UINTN       LoopCount;

> -  UINTN       NextSwapLocation;

> -

> -  ASSERT(BufferToSort     != NULL);

> -  ASSERT(CompareFunction  != NULL);

> -  ASSERT(Buffer  != NULL);

> -

> -  if ( Count < 2

> -    || ElementSize  < 1

> -   ){

> -    return;

> -  }

> -

> -  NextSwapLocation = 0;

> -

> -  //

> -  // pick a pivot (we choose last element)

> -  //

> -  Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));

> -

> -  //

> -  // Now get the pivot such that all on "left" are below it

> -  // and everything "right" are above it

> -  //

> -  for ( LoopCount = 0

> -      ; LoopCount < Count -1

> -      ; LoopCount++

> -     ){

> -    //

> -    // if the element is less than the pivot

> -    //

> -    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){

> -      //

> -      // swap

> -      //

> -      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);

> -      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);

> -      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);

> -

> -      //

> -      // increment NextSwapLocation

> -      //

> -      NextSwapLocation++;

> -    }

> -  }

> -  //

> -  // swap pivot to it's final position (NextSwapLocaiton)

> -  //

> -  CopyMem (Buffer, Pivot, ElementSize);

> -  CopyMem (Pivot,

> (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);

> -  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize),

> Buffer, ElementSize);

> -

> -  //

> -  // Now recurse on 2 paritial lists.  neither of these will have the

> 'pivot' element

> -  // IE list is sorted left half, pivot element, sorted right half...

> -  //

> -  if (NextSwapLocation >= 2) {

> -    QuickSortWorker(

> -      BufferToSort,

> -      NextSwapLocation,

> -      ElementSize,

> -      CompareFunction,

> -      Buffer);

> -  }

> -

> -  if ((Count - NextSwapLocation - 1) >= 2) {

> -    QuickSortWorker(

> -      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,

> -      Count - NextSwapLocation - 1,

> -      ElementSize,

> -      CompareFunction,

> -      Buffer);

> -  }

> -

> -  return;

> -}

>   /**

>     Function to perform a Quick Sort alogrithm on a buffer of comparable elements.

>  

> @@ -173,12 +64,13 @@ PerformQuickSort (

>     Buffer = AllocateZeroPool(ElementSize);

>     ASSERT(Buffer != NULL);

>  

> -  QuickSortWorker(

> +  QuickSort (

>       BufferToSort,

>       Count,

>       ElementSize,

> -    CompareFunction,

> -    Buffer);

> +    (SORT_COMPARE) CompareFunction,

 

See above.

 

Best regards,

Marvin

 

> +    Buffer

> +    );

>  

>     FreePool(Buffer);

>     return;