From: "gaoliming" <gaoliming@byosoft.com.cn>
To: "'Kuo, IanX'" <ianx.kuo@intel.com>, <devel@edk2.groups.io>
Cc: "'Chan, Amy'" <amy.chan@intel.com>,
"'Ni, Ray'" <ray.ni@intel.com>,
"'Wang, Jian J'" <jian.j.wang@intel.com>
Subject: 回复: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib
Date: Wed, 20 Oct 2021 09:49:40 +0800 [thread overview]
Message-ID: <009001d7c554$bef39c40$3cdad4c0$@byosoft.com.cn> (raw)
In-Reply-To: <PH0PR11MB517433BEB66189B3504A8E848EBD9@PH0PR11MB5174.namprd11.prod.outlook.com>
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]
> -=-=-=-=-=-=
>
next prev parent reply other threads:[~2021-10-20 1:49 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-10-18 4:21 [PATCH v6 0/3] Add function QuickSort into MdePkg/BaseLib IanX Kuo
2021-10-18 4:21 ` [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib IanX Kuo
2021-10-20 3:20 ` Wang, Jian J
2021-10-18 4:21 ` [PATCH v6 2/3] CryptoPkg/CryptLib: " IanX Kuo
2021-10-21 11:06 ` Guomin Jiang
2021-10-18 4:21 ` [PATCH v6 3/3] UefiCpuPkg/CpuCacheInfoLib: " IanX Kuo
2021-10-19 1:59 ` Ni, Ray
[not found] ` <16AF0531A156CE70.24927@groups.io>
2021-10-19 2:08 ` [edk2-devel] [PATCH v6 2/3] CryptoPkg/CryptLib: " IanX Kuo
[not found] ` <16AF0531824632DE.13161@groups.io>
2021-10-19 2:09 ` [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: " IanX Kuo
2021-10-20 1:49 ` gaoliming [this message]
2021-10-20 5:45 ` IanX Kuo
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-list from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='009001d7c554$bef39c40$3cdad4c0$@byosoft.com.cn' \
--to=devel@edk2.groups.io \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox