From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail.byosoft.com.cn (mail.byosoft.com.cn [58.240.74.242]) by mx.groups.io with SMTP id smtpd.web11.2443.1634694582879832640 for ; Tue, 19 Oct 2021 18:49:45 -0700 Authentication-Results: mx.groups.io; dkim=missing; spf=none, err=permanent DNS error (domain: byosoft.com.cn, ip: 58.240.74.242, mailfrom: gaoliming@byosoft.com.cn) Received: from DESKTOPS6D0PVI ([58.246.60.130]) (envelope-sender ) by 192.168.6.13 with ESMTP for ; Wed, 20 Oct 2021 09:49:39 +0800 X-WM-Sender: gaoliming@byosoft.com.cn X-Originating-IP: 58.246.60.130 X-WM-AuthFlag: YES X-WM-AuthUser: gaoliming@byosoft.com.cn From: "gaoliming" To: "'Kuo, IanX'" , Cc: "'Chan, Amy'" , "'Ni, Ray'" , "'Wang, Jian J'" References: <20211018042127.1306-1-ianx.kuo@intel.com> <16AF0531824632DE.13161@groups.io> In-Reply-To: Subject: =?UTF-8?B?5Zue5aSNOiBbZWRrMi1kZXZlbF0gW1BBVENIIHY2IDEvM10gTWRlTW9kdWxlUGtnL1NvcnRMaWI6IEFkZCBRdWlja1NvcnQgZnVuY3Rpb24gb24gQmFzZUxpYg==?= Date: Wed, 20 Oct 2021 09:49:40 +0800 Message-ID: <009001d7c554$bef39c40$3cdad4c0$@byosoft.com.cn> MIME-Version: 1.0 X-Mailer: Microsoft Outlook 16.0 Thread-Index: AQEvo8GjOr34C4Y0BPxZCEsUCzue2wLR2hj5AxP+0oWs/DMQEA== Content-Type: text/plain; charset="gb2312" Content-Transfer-Encoding: quoted-printable Content-Language: zh-cn What new change is made in new version patch? Thanks Liming > -----=D3=CA=BC=FE=D4=AD=BC=FE----- > =B7=A2=BC=FE=C8=CB: Kuo, IanX > =B7=A2=CB=CD=CA=B1=BC=E4: 2021=C4=EA10=D4=C219=C8=D5 10:09 > =CA=D5=BC=FE=C8=CB: devel@edk2.groups.io; Kuo, IanX = ; Liming Gao > > =B3=AD=CB=CD: Chan, Amy ; Ni, Ray = ; Wang, > Jian J > =D6=F7=CC=E2: RE: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: = Add > QuickSort function on BaseLib >=20 > @Liming Gao >=20 > Sorry to bother you. May I get your help for review by again ? >=20 > Thanks, > Ian Kuo >=20 > -----Original Message----- > From: 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 ; Ni, Ray ; Kuo, = IanX > ; Wang, Jian J ; Liming Gao > > Subject: [edk2-devel] [PATCH v6 1/3] MdeModulePkg/SortLib: Add = QuickSort > function on BaseLib >=20 > From: IanX Kuo >=20 > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675 >=20 > Use QuickSort instead of QuickSortWorker >=20 > Cc: Ray Ni > Cc: Jian J Wang > Cc: Liming Gao > Signed-off-by: IanX Kuo > --- > .../Library/BaseSortLib/BaseSortLib.c | 115 +---------------- > .../Library/UefiSortLib/UefiSortLib.c | 116 = +----------------- > 2 files changed, 8 insertions(+), 223 deletions(-) >=20 > 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.
+ Copyright (c) 2009 - = 2021, Intel > Corporation. All rights reserved.
SPDX-License-Identifier: > BSD-2-Clause-Patent **/@@ -13,114 +13,6 @@ > #include #include > -/**- 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 !=3D NULL);- > ASSERT(CompareFunction !=3D NULL);- ASSERT(Buffer !=3D NULL);-- if > ( Count < 2- || ElementSize < 1- ){- return;- }-- > NextSwapLocation =3D 0;-- //- // pick a pivot (we choose last = element)- > //- Pivot =3D ((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 =3D 0- ; LoopCount < = Count > -1- ; LoopCount++- ){- //- // if the element is less = than > the pivot- //- if > = (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize) > ),Pivot) <=3D 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 >=3D 2) {- > QuickSortWorker(- BufferToSort,- NextSwapLocation,- > ElementSize,- CompareFunction,- Buffer);- }-- if ((Count - > NextSwapLocation - 1) >=3D 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 =3D AllocateZeroPool(ElementSize); ASSERT(Buffer !=3D = 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.
+ Copyright (c) 2009 - = 2021, Intel > Corporation. All rights reserved.
SPDX-License-Identifier: > BSD-2-Clause-Patent **/@@ -29,115 +29,6 @@ STATIC > EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation =3D 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 !=3D NULL);- > ASSERT(CompareFunction !=3D NULL);- ASSERT(Buffer !=3D NULL);-- if > ( Count < 2- || ElementSize < 1- ){- return;- }-- > NextSwapLocation =3D 0;-- //- // pick a pivot (we choose last = element)- > //- Pivot =3D ((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 =3D 0- ; LoopCount < = Count > -1- ; LoopCount++- ){- //- // if the element is less = than > the pivot- //- if > = (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize) > ),Pivot) <=3D 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 >=3D 2) {- > QuickSortWorker(- BufferToSort,- NextSwapLocation,- > ElementSize,- CompareFunction,- Buffer);- }-- if ((Count - > NextSwapLocation - 1) >=3D 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 =3D AllocateZeroPool(ElementSize); ASSERT(Buffer !=3D = NULL); - > QuickSortWorker(+ QuickSort ( BufferToSort, Count, > ElementSize, CompareFunction,- Buffer);+ Buffer+ ); > FreePool(Buffer); return;-- > 2.30.0.windows.1 >=20 >=20 >=20 > -=3D-=3D-=3D-=3D-=3D-=3D > 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] > -=3D-=3D-=3D-=3D-=3D-=3D >=20