From 101c55ac0db79b9ccff8b612f11755a3d473a82c Mon Sep 17 00:00:00 2001 From: Laszlo Ersek Date: Wed, 13 Jan 2021 09:54:49 +0100 Subject: ShellPkg/ShellCommandLib: add ShellSortFileList() MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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é Cc: Ray Ni Cc: Zhichao Gao Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151 Signed-off-by: Laszlo Ersek Reviewed-by: Zhichao Gao Message-Id: <20210113085453.10168-7-lersek@redhat.com> Reviewed-by: Philippe Mathieu-Daudé --- ShellPkg/ShellPkg.dsc | 1 + 1 file changed, 1 insertion(+) (limited to 'ShellPkg/ShellPkg.dsc') diff --git a/ShellPkg/ShellPkg.dsc b/ShellPkg/ShellPkg.dsc index c42bc9464a..a8b6de3342 100644 --- a/ShellPkg/ShellPkg.dsc +++ b/ShellPkg/ShellPkg.dsc @@ -47,6 +47,7 @@ ShellCommandLib|ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf ShellCEntryLib|ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingLib.inf + OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.inf PeCoffGetEntryPointLib|MdePkg/Library/BasePeCoffGetEntryPointLib/BasePeCoffGetEntryPointLib.inf BcfgCommandLib|ShellPkg/Library/UefiShellBcfgCommandLib/UefiShellBcfgCommandLib.inf -- cgit