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


gaoliming
 

Reviewed-by: Liming Gao <gaoliming@byosoft.com.cn>

-----邮件原件-----
发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo
发送时间: 2021年10月17日 6:34
收件人: devel@edk2.groups.io
抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo
<ianx.kuo@intel.com>; Jian J Wang <jian.j.wang@intel.com>; Liming Gao
<gaoliming@byosoft.com.cn>
主题: [edk2-devel] [PATCH v3 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 (#82182): https://edk2.groups.io/g/devel/message/82182
Mute This Topic: https://groups.io/mt/86381252/4905953
Group Owner: devel+owner@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub
[gaoliming@byosoft.com.cn]
-=-=-=-=-=-=

Join devel@edk2.groups.io to automatically receive all group messages.