Hi Marvin Thanks for reply on Patch V5 I think the patch should eliminate your concern.
IanX Kuo <ianx....@intel.com> 於 2021年10月6日 週三 上午8:31 寫道： > From: IanX Kuo <ianx....@intel.com> > > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 > > Add QuickSort function into BaseLib > > Cc: Ray Ni <ray...@intel.com> > Cc: Michael D Kinney <michael.d.kin...@intel.com> > Cc: Liming Gao <gaolim...@byosoft.com.cn> > Cc: Zhiguang Liu <zhiguang....@intel.com> > Signed-off-by: IanX Kuo <ianx....@intel.com> > --- > 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 equals > to ElementSize. > + It's used by QuickSort() for swapping in > 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.<BR> > + 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 equals > to ElementSize. > + It's used by QuickSort() for swapping in > 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 != NULL); > + ASSERT (CompareFunction != NULL); > + ASSERT (BufferOneElement != NULL); > + ASSERT (ElementSize >= 1); > + > + if (Count < 2) { > + 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 pivot is greater than the element. > + // > + if (CompareFunction ((VOID*) ((UINT8*) BufferToSort + ((LoopCount) * > ElementSize)), Pivot) <= 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 >= 2) { > + QuickSort ( > + BufferToSort, > + NextSwapLocation, > + ElementSize, > + CompareFunction, > + BufferOneElement > + ); > + } > + > + if ((Count - NextSwapLocation - 1) >= 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.<BR> > +# Copyright (c) 2007 - 2021, Intel Corporation. All rights reserved.<BR> > # Portions copyright (c) 2008 - 2009, Apple Inc. All rights reserved.<BR> > # Portions copyright (c) 2011 - 2013, ARM Ltd. All rights reserved.<BR> > # Copyright (c) 2020, Hewlett Packard Enterprise Development LP. All > rights reserved.<BR> > @@ -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+ow...@edk2.groups.io > Unsubscribe: https://edk2.groups.io/g/devel/unsub [guajen0...@gmail.com] > ------------ > > > -=-=-=-=-=-=-=-=-=-=-=- Groups.io Links: You receive all messages sent to this group. View/Reply Online (#81532): https://edk2.groups.io/g/devel/message/81532 Mute This Topic: https://groups.io/mt/86108888/21656 Group Owner: devel+ow...@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [arch...@mail-archive.com] -=-=-=-=-=-=-=-=-=-=-=-
