From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-vs1-f51.google.com (mail-vs1-f51.google.com [209.85.217.51]) by mx.groups.io with SMTP id smtpd.web08.5749.1633482939795475331 for ; Tue, 05 Oct 2021 18:15:40 -0700 Authentication-Results: mx.groups.io; dkim=pass header.i=@gmail.com header.s=20210112 header.b=mp0TI8s1; spf=pass (domain: gmail.com, ip: 209.85.217.51, mailfrom: guajen0710@gmail.com) Received: by mail-vs1-f51.google.com with SMTP id y14so1168085vsm.9 for ; Tue, 05 Oct 2021 18:15:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to; bh=0PcoO2TB5Ls7C2NjV76iZ4kGlxrt/bDuPraD+CHn5D0=; b=mp0TI8s1lPCmgbMHrHYfMp7K0pcsfcceOsluIAtjy3ehexujxl6yu7RdxbM/9GXMso kfFtr4262/da4L5QGeUd/ZJ/vs/c6dRrcsBSmk2ZqDu1yvhrv/BwDmM1BxEqMnQghjal 1GC9qNB3kYbyKuX6tnLS0XS8NEIrXq2Sgp9vm0lJoovfTmrn+2WAO4wBTy/I9OS9LK63 TnMgjX6Gu8b6nXp5BVDL77YHBCuZ91n+m+Yxz/C3+IZNn+717RT+BxRuNvandksgb41D kRYzT12E+35xKM1a1v48i8TjunBwxHF+La2tYfyRd+HSuNRcRg7g1LIsDPMxtRny29YM LApQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to; bh=0PcoO2TB5Ls7C2NjV76iZ4kGlxrt/bDuPraD+CHn5D0=; b=f77GarYSxnj223/ixoP5YQtdEhn4gi3mU59QcCoboNPetaY5HjRa+hFuLswTGHMvE/ /oMun7VuPsYvCslhnm2tKNbu8oPozA2BM8lIdyHE8DsC7vwn5qdi0B1jc73BLx1jiRv9 1mhGIj0+F+Rsw7Luzn35kFxG8P/b6WRrr2hmdkIAibtjIaMSyitwuqJfL0XCqfklNco5 Bzrkw65n1GWYsaw2sCwm+XmSIdexzmF0/gDk7ESLLYFLgCpexfAO2KHpme4kDfxT/fgQ Nrx/pnPDOytpL9ICPsEiXFSSRbF1wBgwF+UFAK8E3CxZdAkWjAoZZhsnmuALWWh1EFmx VPog== X-Gm-Message-State: AOAM531amOIi7NCNkG5y/kSMRn7RUu8VzEvnJI0GtjUT0i9/jMYQgjs8 8JVystogOM9YHF+eAXcf76BBmFyG7SRVeFT3TIEelma9Ej4= X-Google-Smtp-Source: ABdhPJyKvsPlmP5S8FA6mTnr5+rZ3Z8ivg2gatSoz6tVOwssFrajS3EejDyugYHQf0BeDp2O6L13KQZkPS9cFafMCNc= X-Received: by 2002:a67:ad17:: with SMTP id t23mr22456206vsl.35.1633482938838; Tue, 05 Oct 2021 18:15:38 -0700 (PDT) MIME-Version: 1.0 References: <20211006003049.6-1-ianx.kuo@intel.com> <20211006003049.6-2-ianx.kuo@intel.com> In-Reply-To: <20211006003049.6-2-ianx.kuo@intel.com> From: guajen0710@gmail.com Date: Wed, 6 Oct 2021 09:15:26 +0800 Message-ID: Subject: Re: [edk2-devel] [PATCH v6 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib To: devel@edk2.groups.io, ianx.kuo@intel.com, mhaeuser@posteo.de Content-Type: multipart/alternative; boundary="00000000000050f1e205cda4e2ce" --00000000000050f1e205cda4e2ce Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Marvin Thanks for reply on Patch V5 I think the patch should eliminate your concern. IanX Kuo =E6=96=BC 2021=E5=B9=B410=E6=9C=886=E6=97=A5 = =E9=80=B1=E4=B8=89 =E4=B8=8A=E5=8D=888:31 =E5=AF=AB=E9=81=93=EF=BC=9A > From: IanX Kuo > > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675 > > Add QuickSort function into BaseLib > > Cc: Ray Ni > Cc: Michael D Kinney > Cc: Liming Gao > Cc: Zhiguang Liu > Signed-off-by: IanX Kuo > --- > MdePkg/Include/Library/BaseLib.h | 49 ++++++++ > MdePkg/Library/BaseLib/BaseLib.inf | 1 + > MdePkg/Library/BaseLib/QuickSort.c | 116 ++++++++++++++++++ > .../Library/BaseLib/UnitTestHostBaseLib.inf | 3 +- > 4 files changed, 168 insertions(+), 1 deletion(-) > create mode 100644 MdePkg/Library/BaseLib/QuickSort.c > > diff --git a/MdePkg/Include/Library/BaseLib.h > b/MdePkg/Include/Library/BaseLib.h > index 2452c1d92e..0ae0f4e6af 100644 > --- a/MdePkg/Include/Library/BaseLib.h > +++ b/MdePkg/Include/Library/BaseLib.h > @@ -2856,6 +2856,55 @@ RemoveEntryList ( > // > // Math Services > // > +/** > + Prototype for comparison function for any two element types. > + > + @param[in] Buffer1 The pointer to first buffer. > + @param[in] Buffer2 The pointer to second buffer. > + > + @retval 0 Buffer1 equal to Buffer2. > + @return <0 Buffer1 is less than Buffer2. > + @return >0 Buffer1 is greater than Buffer2. > +**/ > +typedef > +INTN > +(EFIAPI *BASE_SORT_COMPARE)( > + IN CONST VOID *Buffer1, > + IN CONST VOID *Buffer2 > + ); > + > +/** > + This function is identical to perform QuickSort, > + 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 BufferOneElement is NULL, then ASSERT. > + if ElementSize is < 1, then ASSERT. > + > + if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equal= s > to ElementSize. > + It's used by QuickSort() for swapping i= n > sorting. > +**/ > +VOID > +EFIAPI > +QuickSort ( > + IN OUT VOID *BufferToSort, > + IN CONST UINTN Count, > + IN CONST UINTN ElementSize, > + IN BASE_SORT_COMPARE CompareFunction, > + OUT VOID *BufferOneElement > + ); > > /** > Shifts a 64-bit integer left between 0 and 63 bits. The low bits are > filled > diff --git a/MdePkg/Library/BaseLib/BaseLib.inf > b/MdePkg/Library/BaseLib/BaseLib.inf > index 6efa5315b6..cebda3b210 100644 > --- a/MdePkg/Library/BaseLib/BaseLib.inf > +++ b/MdePkg/Library/BaseLib/BaseLib.inf > @@ -32,6 +32,7 @@ > SwapBytes16.c > LongJump.c > SetJump.c > + QuickSort.c > RShiftU64.c > RRotU64.c > RRotU32.c > diff --git a/MdePkg/Library/BaseLib/QuickSort.c > b/MdePkg/Library/BaseLib/QuickSort.c > new file mode 100644 > index 0000000000..3aff18188b > --- /dev/null > +++ b/MdePkg/Library/BaseLib/QuickSort.c > @@ -0,0 +1,116 @@ > +/** @file > + Math worker functions. > + > + Copyright (c) 2021, Intel Corporation. All rights reserved.
> + SPDX-License-Identifier: BSD-2-Clause-Patent > + > +**/ > + > +#include "BaseLibInternals.h" > + > +/** > + This function is identical to perform QuickSort, > + 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 BufferOneElement is NULL, then ASSERT. > + if ElementSize is < 1, then ASSERT. > + > + if Count is < 2 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[out] BufferOneElement Caller provided buffer whose size equal= s > to ElementSize. > + It's used by QuickSort() for swapping i= n > sorting. > +**/ > +VOID > +EFIAPI > +QuickSort ( > + IN OUT VOID *BufferToSort, > + IN CONST UINTN Count, > + IN CONST UINTN ElementSize, > + IN BASE_SORT_COMPARE CompareFunction, > + OUT VOID *BufferOneElement > + ) > +{ > + VOID *Pivot; > + UINTN LoopCount; > + UINTN NextSwapLocation; > + > + ASSERT (BufferToSort !=3D NULL); > + ASSERT (CompareFunction !=3D NULL); > + ASSERT (BufferOneElement !=3D NULL); > + ASSERT (ElementSize >=3D 1); > + > + if (Count < 2) { > + 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 pivot is greater than the element. > + // > + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) * > ElementSize)), Pivot) <=3D 0){ > + // > + // swap > + // > + CopyMem (BufferOneElement, (UINT8*) BufferToSort + > (NextSwapLocation * ElementSize), ElementSize); > + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), > (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementSize); > + CopyMem ((UINT8*) BufferToSort + ((LoopCount)*ElementSize), > BufferOneElement, ElementSize); > + > + // > + // increment NextSwapLocation > + // > + NextSwapLocation++; > + } > + } > + // > + // swap pivot to it's final position (NextSwapLocation) > + // > + CopyMem (BufferOneElement, Pivot, ElementSize); > + CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * > ElementSize), ElementSize); > + CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), > BufferOneElement, ElementSize); > + > + // > + // Now recurse on 2 partial lists. neither of these will have the > 'pivot' element > + // IE list is sorted left half, pivot element, sorted right half... > + // > + if (NextSwapLocation >=3D 2) { > + QuickSort ( > + BufferToSort, > + NextSwapLocation, > + ElementSize, > + CompareFunction, > + BufferOneElement > + ); > + } > + > + if ((Count - NextSwapLocation - 1) >=3D 2) { > + QuickSort ( > + (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize, > + Count - NextSwapLocation - 1, > + ElementSize, > + CompareFunction, > + BufferOneElement > + ); > + } > +} > diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf > b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf > index eae1a7158d..d09bd12bef 100644 > --- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf > +++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf > @@ -1,7 +1,7 @@ > ## @file > # Base Library implementation for use with host based unit tests. > # > -# Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved. > +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved. > # Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved. > # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.
> # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All > rights reserved.
> @@ -33,6 +33,7 @@ > SwapBytes16.c > LongJump.c > SetJump.c > + QuickSort.c > RShiftU64.c > RRotU64.c > RRotU32.c > -- > 2.30.0.windows.1 > > > > ------------ > Groups.io Links: You receive all messages sent to this group. > View/Reply Online (#81531): https://edk2.groups.io/g/devel/message/81531 > Mute This Topic: https://groups.io/mt/86108888/4133238 > Group Owner: devel+owner@edk2.groups.io > Unsubscribe: https://edk2.groups.io/g/devel/unsub [guajen0710@gmail.com] > ------------ > > > --00000000000050f1e205cda4e2ce Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Marvin=C2=A0

Thanks for reply on Patch V5
I think the patch s= hould eliminate your concern.

IanX Kuo <ianx.kuo@intel.com> =E6=96=BC 2021=E5=B9=B410=E6=9C=886= =E6=97=A5 =E9=80=B1=E4=B8=89 =E4=B8=8A=E5=8D=888:31 =E5=AF=AB=E9=81=93=EF= =BC=9A
From: IanX Kuo <ianx.ku= o@intel.com>

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

Add QuickSort function into BaseLib

Cc: Ray Ni <ray.ni@intel.com>
Cc: Michael D Kinney <michael.d.kinney@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Signed-off-by: IanX Kuo <ianx.kuo@intel.com>
---
=C2=A0MdePkg/Include/Library/BaseLib.h=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 |=C2=A0 49 ++++++++
=C2=A0MdePkg/Library/BaseLib/BaseLib.inf=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 |=C2=A0 =C2=A01 +
=C2=A0MdePkg/Library/BaseLib/QuickSort.c=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 | 116 ++++++++++++++++++
=C2=A0.../Library/BaseLib/UnitTestHostBaseLib.inf=C2=A0 =C2=A0|=C2=A0 =C2= =A03 +-
=C2=A04 files changed, 168 insertions(+), 1 deletion(-)
=C2=A0create mode 100644 MdePkg/Library/BaseLib/QuickSort.c

diff --git a/MdePkg/Include/Library/BaseLib.h b/MdePkg/Include/Library/Base= Lib.h
index 2452c1d92e..0ae0f4e6af 100644
--- a/MdePkg/Include/Library/BaseLib.h
+++ b/MdePkg/Include/Library/BaseLib.h
@@ -2856,6 +2856,55 @@ RemoveEntryList (
=C2=A0//
=C2=A0// Math Services
=C2=A0//
+/**
+=C2=A0 Prototype for comparison function for any two element types.
+
+=C2=A0 @param[in] Buffer1=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 The pointer to first buffer.
+=C2=A0 @param[in] Buffer2=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 The pointer to second buffer.
+
+=C2=A0 @retval 0=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Buffer1 equal to Buffer2.
+=C2=A0 @return <0=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Buffer1 is less than Buffer2.
+=C2=A0 @return >0=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Buffer1 is greater than Buffer2.
+**/
+typedef
+INTN
+(EFIAPI *BASE_SORT_COMPARE)(
+=C2=A0 IN CONST VOID=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0*Buffer1,
+=C2=A0 IN CONST VOID=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0*Buffer2
+=C2=A0 );
+
+/**
+=C2=A0 This function is identical to perform QuickSort,
+=C2=A0 except that is uses the pre-allocated buffer so the in place sortin= g does not need to
+=C2=A0 allocate and free buffers constantly.
+
+=C2=A0 Each element must be equal sized.
+
+=C2=A0 if BufferToSort is NULL, then ASSERT.
+=C2=A0 if CompareFunction is NULL, then ASSERT.
+=C2=A0 if BufferOneElement is NULL, then ASSERT.
+=C2=A0 if ElementSize is < 1, then ASSERT.
+
+=C2=A0 if Count is < 2 then perform no action.
+
+=C2=A0 @param[in, out] BufferToSort=C2=A0 =C2=A0on call a Buffer of (possi= bly sorted) elements
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0on return a buffer of sorted e= lements
+=C2=A0 @param[in] Count=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0the number of elements in the buffer to sort
+=C2=A0 @param[in] ElementSize=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Size of an = element in bytes
+=C2=A0 @param[in] CompareFunction=C2=A0 =C2=A0 =C2=A0The function to call = to perform the comparison
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0of any 2 elements
+=C2=A0 @param[out] BufferOneElement=C2=A0 =C2=A0Caller provided buffer who= se size equals to ElementSize.
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0It's used by QuickSort() f= or swapping in sorting.
+**/
+VOID
+EFIAPI
+QuickSort (
+=C2=A0 IN OUT VOID=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*BufferToSort,
+=C2=A0 IN CONST UINTN=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Count,
+=C2=A0 IN CONST UINTN=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ElementSize,
+=C2=A0 IN=C2=A0 =C2=A0 =C2=A0 =C2=A0BASE_SORT_COMPARE=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 CompareFunction,
+=C2=A0 OUT VOID=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *BufferOneElement
+=C2=A0 );

=C2=A0/**
=C2=A0 =C2=A0Shifts a 64-bit integer left between 0 and 63 bits. The low bi= ts are filled
diff --git a/MdePkg/Library/BaseLib/BaseLib.inf b/MdePkg/Library/BaseLib/Ba= seLib.inf
index 6efa5315b6..cebda3b210 100644
--- a/MdePkg/Library/BaseLib/BaseLib.inf
+++ b/MdePkg/Library/BaseLib/BaseLib.inf
@@ -32,6 +32,7 @@
=C2=A0 =C2=A0SwapBytes16.c
=C2=A0 =C2=A0LongJump.c
=C2=A0 =C2=A0SetJump.c
+=C2=A0 QuickSort.c
=C2=A0 =C2=A0RShiftU64.c
=C2=A0 =C2=A0RRotU64.c
=C2=A0 =C2=A0RRotU32.c
diff --git a/MdePkg/Library/BaseLib/QuickSort.c b/MdePkg/Library/BaseLib/Qu= ickSort.c
new file mode 100644
index 0000000000..3aff18188b
--- /dev/null
+++ b/MdePkg/Library/BaseLib/QuickSort.c
@@ -0,0 +1,116 @@
+/** @file
+=C2=A0 Math worker functions.
+
+=C2=A0 Copyright (c) 2021, Intel Corporation. All rights reserved.<BR&g= t;
+=C2=A0 SPDX-License-Identifier: BSD-2-Clause-Patent
+
+**/
+
+#include "BaseLibInternals.h"
+
+/**
+=C2=A0 This function is identical to perform QuickSort,
+=C2=A0 except that is uses the pre-allocated buffer so the in place sortin= g does not need to
+=C2=A0 allocate and free buffers constantly.
+
+=C2=A0 Each element must be equal sized.
+
+=C2=A0 if BufferToSort is NULL, then ASSERT.
+=C2=A0 if CompareFunction is NULL, then ASSERT.
+=C2=A0 if BufferOneElement is NULL, then ASSERT.
+=C2=A0 if ElementSize is < 1, then ASSERT.
+
+=C2=A0 if Count is < 2 then perform no action.
+
+=C2=A0 @param[in, out] BufferToSort=C2=A0 =C2=A0on call a Buffer of (possi= bly sorted) elements
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0on return a buffer of sorted e= lements
+=C2=A0 @param[in] Count=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0the number of elements in the buffer to sort
+=C2=A0 @param[in] ElementSize=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Size of an = element in bytes
+=C2=A0 @param[in] CompareFunction=C2=A0 =C2=A0 =C2=A0The function to call = to perform the comparison
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0of any 2 elements
+=C2=A0 @param[out] BufferOneElement=C2=A0 =C2=A0Caller provided buffer who= se size equals to ElementSize.
+=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0It's used by QuickSort() f= or swapping in sorting.
+**/
+VOID
+EFIAPI
+QuickSort (
+=C2=A0 IN OUT VOID=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0*BufferToSort,
+=C2=A0 IN CONST UINTN=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Count,
+=C2=A0 IN CONST UINTN=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 ElementSize,
+=C2=A0 IN=C2=A0 =C2=A0 =C2=A0 =C2=A0BASE_SORT_COMPARE=C2=A0 =C2=A0 =C2=A0 = =C2=A0 =C2=A0 =C2=A0 CompareFunction,
+=C2=A0 OUT VOID=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2= =A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 *BufferOneElement
+=C2=A0 )
+{
+=C2=A0 VOID=C2=A0 =C2=A0 =C2=A0 =C2=A0 *Pivot;
+=C2=A0 UINTN=C2=A0 =C2=A0 =C2=A0 =C2=A0LoopCount;
+=C2=A0 UINTN=C2=A0 =C2=A0 =C2=A0 =C2=A0NextSwapLocation;
+
+=C2=A0 ASSERT (BufferToSort=C2=A0 =C2=A0 =C2=A0!=3D NULL);
+=C2=A0 ASSERT (CompareFunction=C2=A0 !=3D NULL);
+=C2=A0 ASSERT (BufferOneElement !=3D NULL);
+=C2=A0 ASSERT (ElementSize=C2=A0 =C2=A0 =C2=A0 >=3D 1);
+
+=C2=A0 if (Count < 2) {
+=C2=A0 =C2=A0 return;
+=C2=A0 }
+
+=C2=A0 NextSwapLocation =3D 0;
+
+=C2=A0 //
+=C2=A0 // pick a pivot (we choose last element)
+=C2=A0 //
+=C2=A0 Pivot =3D ((UINT8*) BufferToSort + ((Count - 1) * ElementSize)); +
+=C2=A0 //
+=C2=A0 // Now get the pivot such that all on "left" are below it=
+=C2=A0 // and everything "right" are above it
+=C2=A0 //
+=C2=A0 for (LoopCount =3D 0; LoopCount < Count -1; LoopCount++) {
+=C2=A0 =C2=A0 //
+=C2=A0 =C2=A0 // if the pivot is greater than the element.
+=C2=A0 =C2=A0 //
+=C2=A0 =C2=A0 if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((Loop= Count) * ElementSize)), Pivot) <=3D 0){
+=C2=A0 =C2=A0 =C2=A0 //
+=C2=A0 =C2=A0 =C2=A0 // swap
+=C2=A0 =C2=A0 =C2=A0 //
+=C2=A0 =C2=A0 =C2=A0 CopyMem (BufferOneElement, (UINT8*) BufferToSort + (N= extSwapLocation * ElementSize), ElementSize);
+=C2=A0 =C2=A0 =C2=A0 CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * = ElementSize), (UINT8*) BufferToSort + ((LoopCount) * ElementSize), ElementS= ize);
+=C2=A0 =C2=A0 =C2=A0 CopyMem ((UINT8*) BufferToSort + ((LoopCount)*Element= Size), BufferOneElement, ElementSize);
+
+=C2=A0 =C2=A0 =C2=A0 //
+=C2=A0 =C2=A0 =C2=A0 // increment NextSwapLocation
+=C2=A0 =C2=A0 =C2=A0 //
+=C2=A0 =C2=A0 =C2=A0 NextSwapLocation++;
+=C2=A0 =C2=A0 }
+=C2=A0 }
+=C2=A0 //
+=C2=A0 // swap pivot to it's final position (NextSwapLocation)
+=C2=A0 //
+=C2=A0 CopyMem (BufferOneElement, Pivot, ElementSize);
+=C2=A0 CopyMem (Pivot, (UINT8*) BufferToSort + (NextSwapLocation * Element= Size), ElementSize);
+=C2=A0 CopyMem ((UINT8*) BufferToSort + (NextSwapLocation * ElementSize), = BufferOneElement, ElementSize);
+
+=C2=A0 //
+=C2=A0 // Now recurse on 2 partial lists.=C2=A0 neither of these will have= the 'pivot' element
+=C2=A0 // IE list is sorted left half, pivot element, sorted right half...=
+=C2=A0 //
+=C2=A0 if (NextSwapLocation >=3D 2) {
+=C2=A0 =C2=A0 QuickSort (
+=C2=A0 =C2=A0 =C2=A0 BufferToSort,
+=C2=A0 =C2=A0 =C2=A0 NextSwapLocation,
+=C2=A0 =C2=A0 =C2=A0 ElementSize,
+=C2=A0 =C2=A0 =C2=A0 CompareFunction,
+=C2=A0 =C2=A0 =C2=A0 BufferOneElement
+=C2=A0 =C2=A0 =C2=A0 );
+=C2=A0 }
+
+=C2=A0 if ((Count - NextSwapLocation - 1) >=3D 2) {
+=C2=A0 =C2=A0 QuickSort (
+=C2=A0 =C2=A0 =C2=A0 (UINT8 *)BufferToSort + (NextSwapLocation + 1) * Elem= entSize,
+=C2=A0 =C2=A0 =C2=A0 Count - NextSwapLocation - 1,
+=C2=A0 =C2=A0 =C2=A0 ElementSize,
+=C2=A0 =C2=A0 =C2=A0 CompareFunction,
+=C2=A0 =C2=A0 =C2=A0 BufferOneElement
+=C2=A0 =C2=A0 =C2=A0 );
+=C2=A0 }
+}
diff --git a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf b/MdePkg/Librar= y/BaseLib/UnitTestHostBaseLib.inf
index eae1a7158d..d09bd12bef 100644
--- a/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
+++ b/MdePkg/Library/BaseLib/UnitTestHostBaseLib.inf
@@ -1,7 +1,7 @@
=C2=A0## @file
=C2=A0#=C2=A0 Base Library implementation for use with host based unit test= s.
=C2=A0#
-#=C2=A0 Copyright (c) 2007 - 2020, Intel Corporation. All rights reserved.= <BR>
+#=C2=A0 Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.= <BR>
=C2=A0#=C2=A0 Portions copyright (c) 2008 - 2009, Apple Inc. All rights res= erved.<BR>
=C2=A0#=C2=A0 Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reser= ved.<BR>
=C2=A0#=C2=A0 Copyright (c) 2020, Hewlett Packard Enterprise Development LP= . All rights reserved.<BR>
@@ -33,6 +33,7 @@
=C2=A0 =C2=A0SwapBytes16.c
=C2=A0 =C2=A0LongJump.c
=C2=A0 =C2=A0SetJump.c
+=C2=A0 QuickSort.c
=C2=A0 =C2=A0RShiftU64.c
=C2=A0 =C2=A0RRotU64.c
=C2=A0 =C2=A0RRotU32.c
--
2.30.0.windows.1



------------
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#81531): https://edk2.grou= ps.io/g/devel/message/81531
Mute This Topic: https://groups.io/mt/86108888/41332= 38
Group Owner: devel+owner@edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub= [guajen0710@gmail.com]
------------


--00000000000050f1e205cda4e2ce--