[edk2-devel] [PATCH v2 06/10] ShellPkg/ShellCommandLib: add ShellSortFileList()
Philippe Mathieu-Daudé
philmd at redhat.com
Wed Jan 13 13:19:28 UTC 2021
On 1/13/21 9:54 AM, Laszlo Ersek wrote:
> Introduce the ShellSortFileList() function, for sorting an
> EFI_SHELL_FILE_INFO list, by FileName or by FullName.
>
> Duplicates can be kept in the same list, or separated out to a new list.
> In either case, the relative order between duplicates does not change (the
> sorting is stable).
>
> For the sorting, use OrderedCollectionLib rather than SortLib:
>
> - The PerformQuickSort() function from the latter has quadratic worst-case
> time complexity, plus it is implemented recursively (see
> "MdeModulePkg/Library/UefiSortLib/UefiSortLib.c"). It can also not
> return an error on memory allocation failure.
>
> - In comparison, the Red-Black Tree instance of OrderedCollectionLib sorts
> in O(n*log(n)) worst-case time, contains no recursion with the default
> PcdValidateOrderedCollection=FALSE setting, and the OrderedCollectionLib
> class APIs return errors appropriately.
>
> The OrderedCollectionLib APIs do not permit duplicates natively, but by
> using lists as collection entries, stable sorting of duplicates can be
> achieved.
>
> Cc: Philippe Mathieu-Daudé <philmd at redhat.com>
> Cc: Ray Ni <ray.ni at intel.com>
> Cc: Zhichao Gao <zhichao.gao at intel.com>
> Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
> Signed-off-by: Laszlo Ersek <lersek at redhat.com>
> Reviewed-by: Zhichao Gao <zhichao.gao at intel.com>
> ---
>
> Notes:
> v2:
> - no changes
> - pick up Zhichao's R-b
>
> ShellPkg/ShellPkg.dsc | 1 +
> ShellPkg/Include/Library/ShellCommandLib.h | 81 +++++
> ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf | 1 +
> ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h | 19 ++
> ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c | 312 ++++++++++++++++++++
> 5 files changed, 414 insertions(+)
Reviewed-by: Philippe Mathieu-Daude <philmd at redhat.com>
-=-=-=-=-=-=-=-=-=-=-=-
Groups.io Links: You receive all messages sent to this group.
View/Reply Online (#70252): https://edk2.groups.io/g/devel/message/70252
Mute This Topic: https://groups.io/mt/79646584/1813853
Group Owner: devel+owner at edk2.groups.io
Unsubscribe: https://edk2.groups.io/g/devel/unsub [edk2-devel-archive at redhat.com]
-=-=-=-=-=-=-=-=-=-=-=-
More information about the edk2-devel-archive
mailing list