[edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg

Wed Sep 22 06:03:37 UTC 2021

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 <amy.chan at intel.com>; gaoliming <gaoliming at byosoft.com.cn>; 'Andrew Fish' <afish at apple.com>; 'edk2-devel-groups-io' <devel at edk2.groups.io>
Cc: Kinney, Michael D <michael.d.kinney at intel.com>; 'Gao, Liming' <liming.gao at intel.com>; Liu, Zhiguang <Zhiguang.Liu at intel.com>; Wang, Jian J <jian.j.wang at intel.com>; Gao, Zhichao <zhichao.gao at intel.com>
Subject: RE: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg

Amy,
No. We only Add QuickSort() function API into BaseLib.h.

From: Chan, Amy <amy.chan at intel.com<mailto:amy.chan at intel.com>>
Sent: Thursday, September 16, 2021 10:46 AM
To: gaoliming <gaoliming at byosoft.com.cn<mailto:gaoliming at byosoft.com.cn>>; 'Andrew Fish' <afish at apple.com<mailto:afish at apple.com>>; 'edk2-devel-groups-io' <devel at edk2.groups.io<mailto:devel at edk2.groups.io>>
Cc: Ni, Ray <ray.ni at intel.com<mailto:ray.ni at intel.com>>; Kinney, Michael D <michael.d.kinney at intel.com<mailto:michael.d.kinney at intel.com>>; 'Gao, Liming' <liming.gao at intel.com<mailto:liming.gao at intel.com>>; Liu, Zhiguang <zhiguang.liu at intel.com<mailto:zhiguang.liu at intel.com>>; Wang, Jian J <jian.j.wang at intel.com<mailto:jian.j.wang at intel.com>>; Gao, Zhichao <zhichao.gao at intel.com<mailto:zhichao.gao at intel.com>>
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 <gaoliming at byosoft.com.cn<mailto:gaoliming at byosoft.com.cn>>
Sent: Thursday, September 16, 2021 10:23 AM
To: 'Andrew Fish' <afish at apple.com<mailto:afish at apple.com>>; 'edk2-devel-groups-io' <devel at edk2.groups.io<mailto:devel at edk2.groups.io>>
Cc: Ni, Ray <ray.ni at intel.com<mailto:ray.ni at intel.com>>; Kinney, Michael D <michael.d.kinney at intel.com<mailto:michael.d.kinney at intel.com>>; 'Gao, Liming' <liming.gao at intel.com<mailto:liming.gao at intel.com>>; Liu, Zhiguang <zhiguang.liu at intel.com<mailto:zhiguang.liu at intel.com>>; Wang, Jian J <jian.j.wang at intel.com<mailto:jian.j.wang at intel.com>>; Gao, Zhichao <zhichao.gao at intel.com<mailto:zhichao.gao at intel.com>>; Chan, Amy <amy.chan at intel.com<mailto:amy.chan at intel.com>>
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 <afish at apple.com<mailto:afish at apple.com>>
发送时间: 2021年9月16日 10:13
收件人: edk2-devel-groups-io <devel at edk2.groups.io<mailto:devel at edk2.groups.io>>; Liming Gao <gaoliming at byosoft.com.cn<mailto:gaoliming at byosoft.com.cn>>
抄送: Ni, Ray <ray.ni at intel.com<mailto:ray.ni at intel.com>>; Mike Kinney <michael.d.kinney at intel.com<mailto:michael.d.kinney at intel.com>>; Gao, Liming <liming.gao at intel.com<mailto:liming.gao at intel.com>>; Liu, Zhiguang <zhiguang.liu at intel.com<mailto:zhiguang.liu at intel.com>>; Wang, Jian J <jian.j.wang at intel.com<mailto:jian.j.wang at intel.com>>; Gao, Zhichao <zhichao.gao at intel.com<mailto:zhichao.gao at intel.com>>; Chan, Amy <amy.chan at intel.com<mailto:amy.chan at intel.com>>
主题: Re: [edk2-devel] RFC: Add BaseLib/QuickSort in MdePkg

On Sep 15, 2021, at 6:26 PM, gaoliming <gaoliming at byosoft.com.cn<mailto:gaoliming at byosoft.com.cn>> 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
发件人: devel at edk2.groups.io<mailto:devel at edk2.groups.io> <devel at edk2.groups.io<mailto:devel at edk2.groups.io>> 代表 Ni, Ray
发送时间: 2021年9月14日 14:15
收件人: Kinney, Michael D <michael.d.kinney at intel.com<mailto:michael.d.kinney at intel.com>>; Gao, Liming <liming.gao at intel.com<mailto:liming.gao at intel.com>>; Liu, Zhiguang <zhiguang.liu at intel.com<mailto:zhiguang.liu at intel.com>>; Wang, Jian J <jian.j.wang at intel.com<mailto:jian.j.wang at intel.com>>; Gao, Zhichao <zhichao.gao at intel.com<mailto:zhichao.gao at intel.com>>
抄送: devel at edk2.groups.io<mailto:devel at edk2.groups.io>; Chan, Amy <amy.chan at intel.com<mailto:amy.chan at intel.com>>
主题: [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 (#80946): https://edk2.groups.io/g/devel/message/80946
Mute This Topic: https://groups.io/mt/85644120/1813853
Group Owner: devel+owner at edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [edk2-devel-archive at redhat.com]
-=-=-=-=-=-=-=-=-=-=-=-

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://listman.redhat.com/archives/edk2-devel-archive/attachments/20210922/becad9cb/attachment.htm>