* [PATCH v7 0/1] Add function QuickSort into MdePkg/BaseLib @ 2021-10-08 0:27 IanX Kuo 2021-10-08 0:27 ` [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo 0 siblings, 1 reply; 7+ messages in thread From: IanX Kuo @ 2021-10-08 0:27 UTC (permalink / raw) To: devel; +Cc: amy.chan, ray.ni, IanX Kuo From: IanX Kuo <ianx.kuo@intel.com> First change 1. MdePkg/BaseLib: Add QuickSort function It need to seperate to second change 2. MdeModulePkg/SortLib: Use QuickSort instead of QuickSortWorker 3. CryptLib/CryptLib: Remove duplicate QuickSortWorker 4. CpuCacheInfoLib: Remove MdeModulePkg dependency IanX Kuo (1): MdePkg/BaseLib: Add QuickSort function on BaseLib 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 -- 2.30.0.windows.1 ^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib 2021-10-08 0:27 [PATCH v7 0/1] Add function QuickSort into MdePkg/BaseLib IanX Kuo @ 2021-10-08 0:27 ` IanX Kuo 2021-10-08 2:15 ` 回复: [edk2-devel] " gaoliming 0 siblings, 1 reply; 7+ messages in thread From: IanX Kuo @ 2021-10-08 0:27 UTC (permalink / raw) To: devel Cc: amy.chan, ray.ni, IanX Kuo, Michael D Kinney, Liming Gao, Zhiguang Liu From: IanX Kuo <ianx.kuo@intel.com> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 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> --- 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..a825c072b0 --- /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 element is less than or equal to the pivot + // + 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 ^ permalink raw reply related [flat|nested] 7+ messages in thread
* 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib 2021-10-08 0:27 ` [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo @ 2021-10-08 2:15 ` gaoliming 2021-10-08 15:46 ` Michael D Kinney 0 siblings, 1 reply; 7+ messages in thread From: gaoliming @ 2021-10-08 2:15 UTC (permalink / raw) To: devel, ianx.kuo Cc: amy.chan, ray.ni, 'Michael D Kinney', 'Zhiguang Liu' Kuo: I suggest to move SORT_COMPARE definition from MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h, and then let SortLib.h include BaseLib.h. Thanks Liming > -----邮件原件----- > 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo > 发送时间: 2021年10月8日 8:27 > 收件人: devel@edk2.groups.io > 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo > <ianx.kuo@intel.com>; Michael D Kinney <michael.d.kinney@intel.com>; > Liming Gao <gaoliming@byosoft.com.cn>; Zhiguang Liu > <zhiguang.liu@intel.com> > 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function > on BaseLib > > From: IanX Kuo <ianx.kuo@intel.com> > > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 > > 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> > --- > 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..a825c072b0 > --- /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 element is less than or equal to the pivot > > + // > > + 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 (#81615): https://edk2.groups.io/g/devel/message/81615 > Mute This Topic: https://groups.io/mt/86159728/4905953 > Group Owner: devel+owner@edk2.groups.io > Unsubscribe: https://edk2.groups.io/g/devel/unsub > [gaoliming@byosoft.com.cn] > -=-=-=-=-=-= > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib 2021-10-08 2:15 ` 回复: [edk2-devel] " gaoliming @ 2021-10-08 15:46 ` Michael D Kinney 2021-10-08 16:09 ` Marvin Häuser 0 siblings, 1 reply; 7+ messages in thread From: Michael D Kinney @ 2021-10-08 15:46 UTC (permalink / raw) To: devel@edk2.groups.io, gaoliming@byosoft.com.cn, Kuo, IanX, Kinney, Michael D Cc: Chan, Amy, Ni, Ray, Liu, Zhiguang Hi Liming, In general it is not a good idea to include a library include file from another library include file. This becomes a hidden dependency. Mike > -----Original Message----- > From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming > Sent: Thursday, October 7, 2021 7:16 PM > To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com> > Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kinney, Michael D <michael.d.kinney@intel.com>; Liu, > Zhiguang <zhiguang.liu@intel.com> > Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib > > Kuo: > I suggest to move SORT_COMPARE definition from > MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h, > and then let SortLib.h include BaseLib.h. > > Thanks > Liming > > -----邮件原件----- > > 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo > > 发送时间: 2021年10月8日 8:27 > > 收件人: devel@edk2.groups.io > > 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo > > <ianx.kuo@intel.com>; Michael D Kinney <michael.d.kinney@intel.com>; > > Liming Gao <gaoliming@byosoft.com.cn>; Zhiguang Liu > > <zhiguang.liu@intel.com> > > 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function > > on BaseLib > > > > From: IanX Kuo <ianx.kuo@intel.com> > > > > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 > > > > 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> > > --- > > 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..a825c072b0 > > --- /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 element is less than or equal to the pivot > > > > + // > > > > + 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 (#81615): https://edk2.groups.io/g/devel/message/81615 > > Mute This Topic: https://groups.io/mt/86159728/4905953 > > Group Owner: devel+owner@edk2.groups.io > > Unsubscribe: https://edk2.groups.io/g/devel/unsub > > [gaoliming@byosoft.com.cn] > > -=-=-=-=-=-= > > > > > > > > > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib 2021-10-08 15:46 ` Michael D Kinney @ 2021-10-08 16:09 ` Marvin Häuser 2021-10-11 1:21 ` 回复: " gaoliming 0 siblings, 1 reply; 7+ messages in thread From: Marvin Häuser @ 2021-10-08 16:09 UTC (permalink / raw) To: devel, michael.d.kinney, gaoliming@byosoft.com.cn, Kuo, IanX Cc: Chan, Amy, Ni, Ray, Liu, Zhiguang Hey all, I also don't think it makes much logical sense. They are distinct APIs in separate libraries that happen to take a function with the same prototype. I think the patches look good now, thanks! Best regards, Marvin On 08/10/2021 17:46, Michael D Kinney wrote: > Hi Liming, > > In general it is not a good idea to include a library include file from another library include file. > > This becomes a hidden dependency. > > Mike > >> -----Original Message----- >> From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming >> Sent: Thursday, October 7, 2021 7:16 PM >> To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com> >> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kinney, Michael D <michael.d.kinney@intel.com>; Liu, >> Zhiguang <zhiguang.liu@intel.com> >> Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib >> >> Kuo: >> I suggest to move SORT_COMPARE definition from >> MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h, >> and then let SortLib.h include BaseLib.h. >> >> Thanks >> Liming >>> -----邮件原件----- >>> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo >>> 发送时间: 2021年10月8日 8:27 >>> 收件人: devel@edk2.groups.io >>> 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo >>> <ianx.kuo@intel.com>; Michael D Kinney <michael.d.kinney@intel.com>; >>> Liming Gao <gaoliming@byosoft.com.cn>; Zhiguang Liu >>> <zhiguang.liu@intel.com> >>> 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function >>> on BaseLib >>> >>> From: IanX Kuo <ianx.kuo@intel.com> >>> >>> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 >>> >>> 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> >>> --- >>> 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..a825c072b0 >>> --- /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 element is less than or equal to the pivot >>> >>> + // >>> >>> + 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 (#81615): https://edk2.groups.io/g/devel/message/81615 >>> Mute This Topic: https://groups.io/mt/86159728/4905953 >>> Group Owner: devel+owner@edk2.groups.io >>> Unsubscribe: https://edk2.groups.io/g/devel/unsub >>> [gaoliming@byosoft.com.cn] >>> -=-=-=-=-=-= >>> >> >> >> >> >> >> > > > > > ^ permalink raw reply [flat|nested] 7+ messages in thread
* 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib 2021-10-08 16:09 ` Marvin Häuser @ 2021-10-11 1:21 ` gaoliming 2021-10-12 0:09 ` IanX Kuo 0 siblings, 1 reply; 7+ messages in thread From: gaoliming @ 2021-10-11 1:21 UTC (permalink / raw) To: 'Marvin Häuser', devel, michael.d.kinney, 'Kuo, IanX' Cc: 'Chan, Amy', 'Ni, Ray', 'Liu, Zhiguang' Michael and Marvin: I understand your concern. I want to reduce the duplicated definition for the same function. I will not keep my idea if you are both OK to define BASE_SORT_COMPARE and SORT_COMPARE. Thanks Liming > -----邮件原件----- > 发件人: Marvin Häuser <mhaeuser@posteo.de> > 发送时间: 2021年10月9日 0:09 > 收件人: devel@edk2.groups.io; michael.d.kinney@intel.com; > gaoliming@byosoft.com.cn; Kuo, IanX <ianx.kuo@intel.com> > 抄送: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Liu, > Zhiguang <zhiguang.liu@intel.com> > 主题: Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort > function on BaseLib > > Hey all, > > I also don't think it makes much logical sense. They are distinct APIs > in separate libraries that happen to take a function with the same > prototype. > > I think the patches look good now, thanks! > > Best regards, > Marvin > > On 08/10/2021 17:46, Michael D Kinney wrote: > > Hi Liming, > > > > In general it is not a good idea to include a library include file from another > library include file. > > > > This becomes a hidden dependency. > > > > Mike > > > >> -----Original Message----- > >> From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of > gaoliming > >> Sent: Thursday, October 7, 2021 7:16 PM > >> To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com> > >> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Kinney, > Michael D <michael.d.kinney@intel.com>; Liu, > >> Zhiguang <zhiguang.liu@intel.com> > >> Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add > QuickSort function on BaseLib > >> > >> Kuo: > >> I suggest to move SORT_COMPARE definition from > >> MdeModulePkg\Include\Library\SortLib.h to > MdePkg\Include\Library\BaseLib.h, > >> and then let SortLib.h include BaseLib.h. > >> > >> Thanks > >> Liming > >>> -----邮件原件----- > >>> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo > >>> 发送时间: 2021年10月8日 8:27 > >>> 收件人: devel@edk2.groups.io > >>> 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo > >>> <ianx.kuo@intel.com>; Michael D Kinney <michael.d.kinney@intel.com>; > >>> Liming Gao <gaoliming@byosoft.com.cn>; Zhiguang Liu > >>> <zhiguang.liu@intel.com> > >>> 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort > function > >>> on BaseLib > >>> > >>> From: IanX Kuo <ianx.kuo@intel.com> > >>> > >>> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 > >>> > >>> 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> > >>> --- > >>> 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..a825c072b0 > >>> --- /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 element is less than or equal to the pivot > >>> > >>> + // > >>> > >>> + 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 (#81615): > https://edk2.groups.io/g/devel/message/81615 > >>> Mute This Topic: https://groups.io/mt/86159728/4905953 > >>> Group Owner: devel+owner@edk2.groups.io > >>> Unsubscribe: https://edk2.groups.io/g/devel/unsub > >>> [gaoliming@byosoft.com.cn] > >>> -=-=-=-=-=-= > >>> > >> > >> > >> > >> > >> > >> > > > > > > > > > > ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib 2021-10-11 1:21 ` 回复: " gaoliming @ 2021-10-12 0:09 ` IanX Kuo 0 siblings, 0 replies; 7+ messages in thread From: IanX Kuo @ 2021-10-12 0:09 UTC (permalink / raw) To: devel@edk2.groups.io, gaoliming@byosoft.com.cn, 'Marvin Häuser', Kinney, Michael D Cc: Chan, Amy, Ni, Ray, Liu, Zhiguang I send Patch v9, have anyone free can help me for the reviewed by. Patch v8 is "move SORT_COMPARE definition from MdeModulePkg\Include\Library\SortLib.h to MdePkg\Include\Library\BaseLib.h, and then let SortLib.h include BaseLib.h." Patch v9 is rollback to Patch v7. Thanks, Ian Kuo -----Original Message----- From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of gaoliming Sent: Monday, October 11, 2021 9:21 AM To: 'Marvin Häuser' <mhaeuser@posteo.de>; devel@edk2.groups.io; Kinney, Michael D <michael.d.kinney@intel.com>; Kuo, IanX <ianx.kuo@intel.com> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Liu, Zhiguang <zhiguang.liu@intel.com> Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib Michael and Marvin: I understand your concern. I want to reduce the duplicated definition for the same function. I will not keep my idea if you are both OK to define BASE_SORT_COMPARE and SORT_COMPARE. Thanks Liming > -----邮件原件----- > 发件人: Marvin Häuser <mhaeuser@posteo.de> > 发送时间: 2021年10月9日 0:09 > 收件人: devel@edk2.groups.io; michael.d.kinney@intel.com; > gaoliming@byosoft.com.cn; Kuo, IanX <ianx.kuo@intel.com> > 抄送: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; Liu, > Zhiguang <zhiguang.liu@intel.com> > 主题: Re: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort > function on BaseLib > > Hey all, > > I also don't think it makes much logical sense. They are distinct APIs > in separate libraries that happen to take a function with the same > prototype. > > I think the patches look good now, thanks! > > Best regards, > Marvin > > On 08/10/2021 17:46, Michael D Kinney wrote: > > Hi Liming, > > > > In general it is not a good idea to include a library include file > > from another > library include file. > > > > This becomes a hidden dependency. > > > > Mike > > > >> -----Original Message----- > >> From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of > gaoliming > >> Sent: Thursday, October 7, 2021 7:16 PM > >> To: devel@edk2.groups.io; Kuo, IanX <ianx.kuo@intel.com> > >> Cc: Chan, Amy <amy.chan@intel.com>; Ni, Ray <ray.ni@intel.com>; > >> Kinney, > Michael D <michael.d.kinney@intel.com>; Liu, > >> Zhiguang <zhiguang.liu@intel.com> > >> Subject: 回复: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add > QuickSort function on BaseLib > >> > >> Kuo: > >> I suggest to move SORT_COMPARE definition from > >> MdeModulePkg\Include\Library\SortLib.h to > MdePkg\Include\Library\BaseLib.h, > >> and then let SortLib.h include BaseLib.h. > >> > >> Thanks > >> Liming > >>> -----邮件原件----- > >>> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 IanX Kuo > >>> 发送时间: 2021年10月8日 8:27 > >>> 收件人: devel@edk2.groups.io > >>> 抄送: amy.chan@intel.com; ray.ni@intel.com; IanX Kuo > >>> <ianx.kuo@intel.com>; Michael D Kinney > >>> <michael.d.kinney@intel.com>; Liming Gao > >>> <gaoliming@byosoft.com.cn>; Zhiguang Liu <zhiguang.liu@intel.com> > >>> 主题: [edk2-devel] [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort > function > >>> on BaseLib > >>> > >>> From: IanX Kuo <ianx.kuo@intel.com> > >>> > >>> REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3675 > >>> > >>> 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> > >>> --- > >>> 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..a825c072b0 > >>> --- /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 element is less than or equal to the pivot > >>> > >>> + // > >>> > >>> + 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 (#81615): > https://edk2.groups.io/g/devel/message/81615 > >>> Mute This Topic: https://groups.io/mt/86159728/4905953 > >>> Group Owner: devel+owner@edk2.groups.io > >>> Unsubscribe: https://edk2.groups.io/g/devel/unsub > >>> [gaoliming@byosoft.com.cn] > >>> -=-=-=-=-=-= > >>> > >> > >> > >> > >> > >> > >> > > > > > > > > > > ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2021-10-12 0:09 UTC | newest] Thread overview: 7+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2021-10-08 0:27 [PATCH v7 0/1] Add function QuickSort into MdePkg/BaseLib IanX Kuo 2021-10-08 0:27 ` [PATCH v7 1/1] MdePkg/BaseLib: Add QuickSort function on BaseLib IanX Kuo 2021-10-08 2:15 ` 回复: [edk2-devel] " gaoliming 2021-10-08 15:46 ` Michael D Kinney 2021-10-08 16:09 ` Marvin Häuser 2021-10-11 1:21 ` 回复: " gaoliming 2021-10-12 0:09 ` IanX Kuo
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox