Re: [PATCH v2 06/10] ShellPkg/ShellCommandLib: add ShellSortFileList()

["Philippe Mathieu-Daudé" <philmd@redhat.com>]

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@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>
> ---
> 
> 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@redhat.com>