ShellPkg/ShellCommandLib: add ShellSortFileList()

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@redhat.com>
Cc: Ray Ni <ray.ni@intel.com>
Cc: Zhichao Gao <zhichao.gao@intel.com>
Ref: https://bugzilla.tianocore.org/show_bug.cgi?id=3151
Signed-off-by: Laszlo Ersek <lersek@redhat.com>
Reviewed-by: Zhichao Gao <zhichao.gao@intel.com>
Message-Id: <20210113085453.10168-7-lersek@redhat.com>
Reviewed-by: Philippe Mathieu-Daudé <philmd@redhat.com>

1 files changed, 1 insertions, 0 deletions

diff --git a/ShellPkg/ShellPkg.dsc b/ShellPkg/ShellPkg.dsc
index c42bc94..a8b6de3 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