More details on new QuickSort() API:
The new API needs to carry additional parameter “BufferOneElement”.
This parameter gives QuickSort() the temporary buffer for swapping in sorting.
It’s to avoid BaseLib depends on MemoryAllocationLib.
…
@param [in] BufferOneElement When ElementSize > 256, caller needs to provide a
buffer whose size
equals to ElementSize. It’s used by QuickSort()
for swapping in sorting.
When ElementSize <= 256, QuickSort() uses a local
stack 256-byte buffer.
@retval EFI_INVALID_PARAMETER When (ElementSize > 256) and (BufferOneElement ==
NULL).
…
VOID
EFIAPI
QuickSort (
IN OUT VOID *BufferToSort,
IN CONST UINTN ElementCount,
IN CONST UINTN ElementSize,
IN SORT_COMPARE CompareFunction,
IN VOID *BufferOneElement OPTIONAL
);
Any comments?
From: [email protected] <[email protected]> On Behalf Of Ni, Ray
Sent: Wednesday, September 22, 2021 2:04 PM
To: Chan, Amy <[email protected]>; gaoliming <[email protected]>;
'Andrew Fish' <[email protected]>; 'edk2-devel-groups-io' <[email protected]>
Cc: Kinney, Michael D <[email protected]>; 'Gao, Liming'
<[email protected]>; Liu, Zhiguang <[email protected]>; Wang, Jian J
<[email protected]>; Gao, Zhichao <[email protected]>
Subject: Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
I don’t see objection so far.
So, the final solution is:
1. Add QuickSort() API to BaseLib in MdePkg.
2. Update existing MdeModulePkg/SortLib to use QuickSort() in the
implementation (proposed by Andrew Fish and Liming Gao)
3. Update UefiCpuPkg to use QuickSortLib to remove improper dependency on
MdeModulePkg
Thanks,
Ray
From: Ni, Ray
Sent: Thursday, September 16, 2021 10:48 AM
To: Chan, Amy <[email protected]<mailto:[email protected]>>; gaoliming
<[email protected]<mailto:[email protected]>>; 'Andrew Fish'
<[email protected]<mailto:[email protected]>>; 'edk2-devel-groups-io'
<[email protected]<mailto:[email protected]>>
Cc: Kinney, Michael D
<[email protected]<mailto:[email protected]>>; 'Gao, Liming'
<[email protected]<mailto:[email protected]>>; Liu, Zhiguang
<[email protected]<mailto:[email protected]>>; Wang, Jian J
<[email protected]<mailto:[email protected]>>; Gao, Zhichao
<[email protected]<mailto:[email protected]>>
Subject: RE: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
Amy,
No. We only Add QuickSort() function API into BaseLib.h.
From: Chan, Amy <[email protected]<mailto:[email protected]>>
Sent: Thursday, September 16, 2021 10:46 AM
To: gaoliming <[email protected]<mailto:[email protected]>>;
'Andrew Fish' <[email protected]<mailto:[email protected]>>; 'edk2-devel-groups-io'
<[email protected]<mailto:[email protected]>>
Cc: Ni, Ray <[email protected]<mailto:[email protected]>>; Kinney, Michael D
<[email protected]<mailto:[email protected]>>; 'Gao, Liming'
<[email protected]<mailto:[email protected]>>; Liu, Zhiguang
<[email protected]<mailto:[email protected]>>; Wang, Jian J
<[email protected]<mailto:[email protected]>>; Gao, Zhichao
<[email protected]<mailto:[email protected]>>
Subject: RE: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
Just to double confirm, will we have the null instance of QuickSort in MdePkg?
Regards,
Amy
From: gaoliming <[email protected]<mailto:[email protected]>>
Sent: Thursday, September 16, 2021 10:23 AM
To: 'Andrew Fish' <[email protected]<mailto:[email protected]>>;
'edk2-devel-groups-io' <[email protected]<mailto:[email protected]>>
Cc: Ni, Ray <[email protected]<mailto:[email protected]>>; Kinney, Michael D
<[email protected]<mailto:[email protected]>>; 'Gao, Liming'
<[email protected]<mailto:[email protected]>>; Liu, Zhiguang
<[email protected]<mailto:[email protected]>>; Wang, Jian J
<[email protected]<mailto:[email protected]>>; Gao, Zhichao
<[email protected]<mailto:[email protected]>>; Chan, Amy
<[email protected]<mailto:[email protected]>>
Subject: 回复: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
Andrew:
Thanks for your suggestion. I think your idea is better. We add new
QuickSort() API to BaseLib, and update SortLib library instance to consume
BaseLib QuickSort() API. This way has no change in current SortLib library
class. It is the compatible solution.
Thanks
Liming
发件人: Andrew Fish <[email protected]<mailto:[email protected]>>
发送时间: 2021年9月16日 10:13
收件人: edk2-devel-groups-io <[email protected]<mailto:[email protected]>>;
Liming Gao <[email protected]<mailto:[email protected]>>
抄送: Ni, Ray <[email protected]<mailto:[email protected]>>; Mike Kinney
<[email protected]<mailto:[email protected]>>; Gao, Liming
<[email protected]<mailto:[email protected]>>; Liu, Zhiguang
<[email protected]<mailto:[email protected]>>; Wang, Jian J
<[email protected]<mailto:[email protected]>>; Gao, Zhichao
<[email protected]<mailto:[email protected]>>; Chan, Amy
<[email protected]<mailto:[email protected]>>
主题: Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
On Sep 15, 2021, at 6:26 PM, gaoliming
<[email protected]<mailto:[email protected]>> wrote:
Ray:
SortLib has been added since 2015. I would suggest to still keep this library
class. To resolve the package dependency, my proposal is to move the library
class header file SortLib.h from MdeModulePkg to MdePkg, and still keep the
library instance in MdeModulePkg. This proposal has no impact on the existing
platform.
If we add QuickSort() API to the BaseLib can we not just port the existing
MdeModulePkg/SortLib to use QuickSort() in the implementation? Or is there some
other way to add the new thing in a backward compatible way.
Thanks,
Andrew Fish
Thanks
Liming
发件人: [email protected]<mailto:[email protected]>
<[email protected]<mailto:[email protected]>> 代表 Ni, Ray
发送时间: 2021年9月14日 14:15
收件人: Kinney, Michael D
<[email protected]<mailto:[email protected]>>; Gao, Liming
<[email protected]<mailto:[email protected]>>; Liu, Zhiguang
<[email protected]<mailto:[email protected]>>; Wang, Jian J
<[email protected]<mailto:[email protected]>>; Gao, Zhichao
<[email protected]<mailto:[email protected]>>
抄送: [email protected]<mailto:[email protected]>; Chan, Amy
<[email protected]<mailto:[email protected]>>
主题: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg
Hi package maintainers of MdePkg, MdeModulePkg and ShellPkg, community,
A commit (UefiCpuPkg/CpuCacheInfoLib: Sort CpuCacheInfo
array<https://github.com/tianocore/edk2/commit/4de77ae9890d241271f543e9195ab3516f3abec6>)
to UefiCpuPkg let
UefiCpuPkg depend on MdeModulePkg because the SortLib class and instances are
all in MdeModulePkg.
UefiCpuPkg depending on MdeModulePkg breaks the rule that “UefiCpuPkg should
ONLY depend on MdePkg”.
To address this issue, there are two approaches:
1. Duplicate the sort logic in UefiCpuPkg to not depend on
MdeModulePkg/SortLib
2. Add QuickSort() API to BaseLib in MdePkg.
Approach #2 (MdePkg/BaseLib/QuickSort) makes more sense because quick sort is a
standard algorithm.
We encourage consumers to update their code to use the quick sort in MdePkg and
gradually deprecate today’s MdeModulePkg/SortLib.
If you don’t have concerns, I plan to:
1. “Add QuickSort() to BaseLib” and update all existing consumers to use
this API instead.
VOID
EFIAPI
QuickSort (
IN OUT VOID *BufferToSort,
IN CONST UINTN Count,
IN CONST UINTN ElementSize,
IN SORT_COMPARE CompareFunction
);
1. “Add new ShellPkg/SortCompareLib”
Background: ShellPkg requires to sort devicepath/string so 3 APIs in
UefiSortLib (DevicePathCompare, StringNoCaseCompare, StringCompare) are
provided for Shell usage. we can move the 3 APIs to the SortCompareLib and
update Shell code to use BaseLib/QuickSort directly, with the sort compare
function from SortCompareLib.
Any concerns?
Thanks,
Ray
-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#81061): https://edk2.groups.io/g/devel/message/81061
Mute This Topic: https://groups.io/mt/85644120/21656
Group Owner: [email protected]
Unsubscribe: https://edk2.groups.io/g/devel/unsub [[email protected]]
-=-=-=-=-=-=-=-=-=-=-=-
