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/1787277
Group Owner: devel+owner@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [importer@patchew.org]
-=-=-=-=-=-=-=-=-=-=-=-
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
-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#82404): https://edk2.groups.io/g/devel/message/82404
Mute This Topic: https://groups.io/mt/86406843/1787277
Group Owner: devel+owner@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [importer@patchew.org]
-=-=-=-=-=-=-=-=-=-=-=-
© 2016 - 2026 Red Hat, Inc.