Re: [PATCH 4/8] ShellPkg/ShellCommandLib: add ShellSortFileList()

["Gao, Zhichao" <zhichao.gao@intel.com>]

Reviewed-by: Zhichao Gao <zhichao.gao@intel.com>

Thanks,
Zhichao

> -----Original Message-----
> From: Laszlo Ersek <lersek@redhat.com>
> Sent: Monday, January 4, 2021 11:43 PM
> To: edk2-devel-groups-io <devel@edk2.groups.io>
> Cc: Philippe Mathieu-Daudé <philmd@redhat.com>; Ni, Ray <ray.ni@intel.com>;
> Gao, Zhichao <zhichao.gao@intel.com>
> Subject: [PATCH 4/8] 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>
> ---
>  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(+)
> 
> diff --git a/ShellPkg/ShellPkg.dsc b/ShellPkg/ShellPkg.dsc index
> c42bc9464a0f..a8b6de334284 100644
> --- a/ShellPkg/ShellPkg.dsc
> +++ b/ShellPkg/ShellPkg.dsc
> @@ -47,6 +47,7 @@ [LibraryClasses.common]
> 
> ShellCommandLib|ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.i
> nf
>    ShellCEntryLib|ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf
> 
> HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingLib.in
> f
> +
> + OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeL
> + ib/BaseOrderedCollectionRedBlackTreeLib.inf
> 
> 
> PeCoffGetEntryPointLib|MdePkg/Library/BasePeCoffGetEntryPointLib/BasePeCo
> ffGetEntryPointLib.inf
> 
> BcfgCommandLib|ShellPkg/Library/UefiShellBcfgCommandLib/UefiShellBcfgCom
> mandLib.inf
> diff --git a/ShellPkg/Include/Library/ShellCommandLib.h
> b/ShellPkg/Include/Library/ShellCommandLib.h
> index 63fcac82a2de..bc1afed5e7f5 100644
> --- a/ShellPkg/Include/Library/ShellCommandLib.h
> +++ b/ShellPkg/Include/Library/ShellCommandLib.h
> @@ -714,4 +714,85 @@ CatSDumpHex (
>    IN UINTN   DataSize,
>    IN VOID    *UserData
>    );
> +
> +//
> +// Determines the ordering operation for ShellSortFileList().
> +//
> +typedef enum {
> +  //
> +  // Sort the EFI_SHELL_FILE_INFO objects by the FileName field, in
> +increasing
> +  // order, using gUnicodeCollation->StriColl().
> +  //
> +  ShellSortFileListByFileName,
> +  //
> +  // Sort the EFI_SHELL_FILE_INFO objects by the FullName field, in
> +increasing
> +  // order, using gUnicodeCollation->StriColl().
> +  //
> +  ShellSortFileListByFullName,
> +  ShellSortFileListMax
> +} SHELL_SORT_FILE_LIST;
> +
> +/**
> +  Sort an EFI_SHELL_FILE_INFO list, optionally moving duplicates to a
> +separate
> +  list.
> +
> +  @param[in,out] FileList  The list of EFI_SHELL_FILE_INFO objects to sort.
> +
> +                           If FileList is NULL on input, then FileList is
> +                           considered an empty, hence already sorted, list.
> +
> +                           Otherwise, if (*FileList) is NULL on input, then
> +                           EFI_INVALID_PARAMETER is returned.
> +
> +                           Otherwise, the caller is responsible for having
> +                           initialized (*FileList)->Link with
> +                           InitializeListHead(). No other fields in the
> +                           (**FileList) head element are accessed by this
> +                           function.
> +
> +                           On output, (*FileList) is sorted according to Order.
> +                           If Duplicates is NULL on input, then duplicate
> +                           elements are preserved, sorted stably, on
> +                           (*FileList). If Duplicates is not NULL on input,
> +                           then duplicates are moved (stably sorted) to the
> +                           new, dynamically allocated (*Duplicates) list.
> +
> +  @param[out] Duplicates   If Duplicates is NULL on input, (*FileList) will be
> +                           a monotonically ordered list on output, with
> +                           duplicates stably sorted.
> +
> +                           If Duplicates is not NULL on input, (*FileList) will
> +                           be a strictly monotonically oredered list on output,
> +                           with duplicates separated (stably sorted) to
> +                           (*Duplicates). All fields except Link will be
> +                           zero-initialized in the (**Duplicates) head element.
> +                           If no duplicates exist, then (*Duplicates) is set to
> +                           NULL on output.
> +
> +  @param[in] Order         Determines the comparison operation between
> +                           EFI_SHELL_FILE_INFO objects.
> +
> +  @retval EFI_INVALID_PARAMETER  (UINTN)Order is greater than or equal to
> +                                 (UINTN)ShellSortFileListMax. Neither the
> +                                 (*FileList) nor the (*Duplicates) list has
> +                                 been modified.
> +
> +  @retval EFI_INVALID_PARAMETER  (*FileList) was NULL on input. Neither the
> +                                 (*FileList) nor the (*Duplicates) list has
> +                                 been modified.
> +
> +  @retval EFI_OUT_OF_RESOURCES   Memory allocation failed. Neither the
> +                                 (*FileList) nor the (*Duplicates) list has
> +                                 been modified.
> +
> +  @retval EFI_SUCCESS            Sorting successful, including the case when
> +                                 FileList is NULL on input.
> +**/
> +EFI_STATUS
> +EFIAPI
> +ShellSortFileList (
> +  IN OUT EFI_SHELL_FILE_INFO  **FileList,
> +     OUT EFI_SHELL_FILE_INFO  **Duplicates OPTIONAL,
> +  IN     SHELL_SORT_FILE_LIST Order
> +  );
>  #endif //_SHELL_COMMAND_LIB_
> diff --git a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> index a1b5601c96b6..08ca7cb78842 100644
> --- a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> +++ b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
> @@ -42,6 +42,7 @@ [LibraryClasses]
>    ShellLib
>    HiiLib
>    HandleParsingLib
> +  OrderedCollectionLib
> 
>  [Protocols]
>    gEfiUnicodeCollation2ProtocolGuid                       ## CONSUMES
> diff --git a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
> b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
> index 8ecc2f6bf5a2..0ca291e4f9bf 100644
> --- a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
> +++ b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
> @@ -39,6 +39,7 @@
>  #include <Library/HiiLib.h>
>  #include <Library/UefiBootServicesTableLib.h>
>  #include <Library/UefiLib.h>
> +#include <Library/OrderedCollectionLib.h>
> 
>  typedef struct{
>    LIST_ENTRY                  Link;
> @@ -60,6 +61,24 @@ typedef struct {
>    CHAR16            *Path;
>  } SHELL_COMMAND_FILE_HANDLE;
> 
> +//
> +// Collects multiple EFI_SHELL_FILE_INFO objects that share the same name.
> +//
> +typedef struct {
> +  //
> +  // A string that compares equal to either the FileName or the
> +FullName fields
> +  // of all EFI_SHELL_FILE_INFO objects on SameNameList, according to
> +  // gUnicodeCollation->StriColl(). The string is not dynamically
> +allocated;
> +  // instead, it *aliases* the FileName or FullName field of the
> +  // EFI_SHELL_FILE_INFO object that was first encountered with this name.
> +  //
> +  CONST CHAR16 *Alias;
> +  //
> +  // A list of EFI_SHELL_FILE_INFO objects whose FileName or FullName
> +fields
> +  // compare equal to Alias, according to gUnicodeCollation->StriColl().
> +  //
> +  LIST_ENTRY SameNameList;
> +} SHELL_SORT_UNIQUE_NAME;
> 
>  #endif //_UEFI_COMMAND_LIB_INTERNAL_HEADER_
> 
> diff --git a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
> b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
> index 345808a1eac6..b06d22592d33 100644
> --- a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
> +++ b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
> @@ -1909,3 +1909,315 @@ CatSDumpHex (
> 
>    return RetVal;
>  }
> +
> +/**
> +  ORDERED_COLLECTION_USER_COMPARE function for
> SHELL_SORT_UNIQUE_NAME objects.
> +
> +  @param[in] Unique1AsVoid  The first SHELL_SORT_UNIQUE_NAME object
> (Unique1),
> +                            passed in as a pointer-to-VOID.
> +
> +  @param[in] Unique2AsVoid  The second SHELL_SORT_UNIQUE_NAME object
> (Unique2),
> +                            passed in as a pointer-to-VOID.
> +
> +  @retval <0  If Unique1 compares less than Unique2.
> +
> +  @retval  0  If Unique1 compares equal to Unique2.
> +
> +  @retval >0  If Unique1 compares greater than Unique2.
> +**/
> +STATIC
> +INTN
> +EFIAPI
> +UniqueNameCompare (
> +  IN CONST VOID *Unique1AsVoid,
> +  IN CONST VOID *Unique2AsVoid
> +  )
> +{
> +  CONST SHELL_SORT_UNIQUE_NAME *Unique1;
> +  CONST SHELL_SORT_UNIQUE_NAME *Unique2;
> +
> +  Unique1 = Unique1AsVoid;
> +  Unique2 = Unique2AsVoid;
> +
> +  //
> +  // We need to cast away CONST for EFI_UNICODE_COLLATION_STRICOLL.
> +  //
> +  return gUnicodeCollation->StriColl (
> +                              gUnicodeCollation,
> +                              (CHAR16 *)Unique1->Alias,
> +                              (CHAR16 *)Unique2->Alias
> +                              );
> +}
> +
> +/**
> +  ORDERED_COLLECTION_KEY_COMPARE function for
> SHELL_SORT_UNIQUE_NAME objects.
> +
> +  @param[in] UniqueAliasAsVoid  The CHAR16 string UniqueAlias, passed in as a
> +                                pointer-to-VOID.
> +
> +  @param[in] UniqueAsVoid       The SHELL_SORT_UNIQUE_NAME object
> (Unique),
> +                                passed in as a pointer-to-VOID.
> +
> +  @retval <0  If UniqueAlias compares less than Unique->Alias.
> +
> +  @retval  0  If UniqueAlias compares equal to Unique->Alias.
> +
> +  @retval >0  If UniqueAlias compares greater than Unique->Alias.
> +**/
> +STATIC
> +INTN
> +EFIAPI
> +UniqueNameAliasCompare (
> +  IN CONST VOID *UniqueAliasAsVoid,
> +  IN CONST VOID *UniqueAsVoid
> +  )
> +{
> +  CONST CHAR16                 *UniqueAlias;
> +  CONST SHELL_SORT_UNIQUE_NAME *Unique;
> +
> +  UniqueAlias = UniqueAliasAsVoid;
> +  Unique      = UniqueAsVoid;
> +
> +  //
> +  // We need to cast away CONST for EFI_UNICODE_COLLATION_STRICOLL.
> +  //
> +  return gUnicodeCollation->StriColl (
> +                              gUnicodeCollation,
> +                              (CHAR16 *)UniqueAlias,
> +                              (CHAR16 *)Unique->Alias
> +                              );
> +}
> +
> +/**
> +  Sort an EFI_SHELL_FILE_INFO list, optionally moving duplicates to a
> +separate
> +  list.
> +
> +  @param[in,out] FileList  The list of EFI_SHELL_FILE_INFO objects to sort.
> +
> +                           If FileList is NULL on input, then FileList is
> +                           considered an empty, hence already sorted, list.
> +
> +                           Otherwise, if (*FileList) is NULL on input, then
> +                           EFI_INVALID_PARAMETER is returned.
> +
> +                           Otherwise, the caller is responsible for having
> +                           initialized (*FileList)->Link with
> +                           InitializeListHead(). No other fields in the
> +                           (**FileList) head element are accessed by this
> +                           function.
> +
> +                           On output, (*FileList) is sorted according to Order.
> +                           If Duplicates is NULL on input, then duplicate
> +                           elements are preserved, sorted stably, on
> +                           (*FileList). If Duplicates is not NULL on input,
> +                           then duplicates are moved (stably sorted) to the
> +                           new, dynamically allocated (*Duplicates) list.
> +
> +  @param[out] Duplicates   If Duplicates is NULL on input, (*FileList) will be
> +                           a monotonically ordered list on output, with
> +                           duplicates stably sorted.
> +
> +                           If Duplicates is not NULL on input, (*FileList) will
> +                           be a strictly monotonically oredered list on output,
> +                           with duplicates separated (stably sorted) to
> +                           (*Duplicates). All fields except Link will be
> +                           zero-initialized in the (**Duplicates) head element.
> +                           If no duplicates exist, then (*Duplicates) is set to
> +                           NULL on output.
> +
> +  @param[in] Order         Determines the comparison operation between
> +                           EFI_SHELL_FILE_INFO objects.
> +
> +  @retval EFI_INVALID_PARAMETER  (UINTN)Order is greater than or equal to
> +                                 (UINTN)ShellSortFileListMax. Neither the
> +                                 (*FileList) nor the (*Duplicates) list has
> +                                 been modified.
> +
> +  @retval EFI_INVALID_PARAMETER  (*FileList) was NULL on input. Neither the
> +                                 (*FileList) nor the (*Duplicates) list has
> +                                 been modified.
> +
> +  @retval EFI_OUT_OF_RESOURCES   Memory allocation failed. Neither the
> +                                 (*FileList) nor the (*Duplicates) list has
> +                                 been modified.
> +
> +  @retval EFI_SUCCESS            Sorting successful, including the case when
> +                                 FileList is NULL on input.
> +**/
> +EFI_STATUS
> +EFIAPI
> +ShellSortFileList (
> +  IN OUT EFI_SHELL_FILE_INFO  **FileList,
> +     OUT EFI_SHELL_FILE_INFO  **Duplicates OPTIONAL,
> +  IN     SHELL_SORT_FILE_LIST Order
> +  )
> +{
> +  LIST_ENTRY               *FilesHead;
> +  ORDERED_COLLECTION       *Sort;
> +  LIST_ENTRY               *FileEntry;
> +  EFI_SHELL_FILE_INFO      *FileInfo;
> +  SHELL_SORT_UNIQUE_NAME   *Unique;
> +  EFI_STATUS               Status;
> +  EFI_SHELL_FILE_INFO      *Dupes;
> +  LIST_ENTRY               *NextFileEntry;
> +  CONST CHAR16             *Alias;
> +  ORDERED_COLLECTION_ENTRY *SortEntry;
> +  LIST_ENTRY               *TargetFileList;
> +  ORDERED_COLLECTION_ENTRY *NextSortEntry;
> +  VOID                     *UniqueAsVoid;
> +
> +  if ((UINTN)Order >= (UINTN)ShellSortFileListMax) {
> +    return EFI_INVALID_PARAMETER;
> +  }
> +
> +  if (FileList == NULL) {
> +    //
> +    // FileList is considered empty, hence already sorted, with no duplicates.
> +    //
> +    if (Duplicates != NULL) {
> +      *Duplicates = NULL;
> +    }
> +    return EFI_SUCCESS;
> +  }
> +
> +  if (*FileList == NULL) {
> +    return EFI_INVALID_PARAMETER;
> +  }
> +  FilesHead = &(*FileList)->Link;
> +
> +  //
> +  // Collect all the unique names.
> +  //
> +  Sort = OrderedCollectionInit (UniqueNameCompare,
> + UniqueNameAliasCompare);  if (Sort == NULL) {
> +    return EFI_OUT_OF_RESOURCES;
> +  }
> +
> +  BASE_LIST_FOR_EACH (FileEntry, FilesHead) {
> +    FileInfo = (EFI_SHELL_FILE_INFO *)FileEntry;
> +
> +    //
> +    // Try to record the name of this file as a unique name.
> +    //
> +    Unique = AllocatePool (sizeof (*Unique));
> +    if (Unique == NULL) {
> +      Status = EFI_OUT_OF_RESOURCES;
> +      goto UninitSort;
> +    }
> +    Unique->Alias = ((Order == ShellSortFileListByFileName) ?
> +                     FileInfo->FileName :
> +                     FileInfo->FullName);
> +    InitializeListHead (&Unique->SameNameList);
> +
> +    Status = OrderedCollectionInsert (Sort, NULL, Unique);
> +    if (EFI_ERROR (Status)) {
> +      //
> +      // Only two errors are possible: memory allocation failed, or this name
> +      // has been encountered before. In either case, the
> +      // SHELL_SORT_UNIQUE_NAME object being constructed has to be released.
> +      //
> +      FreePool (Unique);
> +      //
> +      // Memory allocation failure is fatal, while having seen the same name
> +      // before is normal.
> +      //
> +      if (Status == EFI_OUT_OF_RESOURCES) {
> +        goto UninitSort;
> +      }
> +      ASSERT (Status == EFI_ALREADY_STARTED);
> +    }
> +  }
> +
> +  //
> +  // If separation of duplicates has been requested, allocate the list
> + for  // them.
> +  //
> +  if (Duplicates != NULL) {
> +    Dupes = AllocateZeroPool (sizeof (*Dupes));
> +    if (Dupes == NULL) {
> +      Status = EFI_OUT_OF_RESOURCES;
> +      goto UninitSort;
> +    }
> +    InitializeListHead (&Dupes->Link);
> +  }
> +
> +  //
> +  // No memory allocation beyond this point; thus, no chance to fail.
> + We can  // now migrate the EFI_SHELL_FILE_INFO objects from (*FileList) to
> Sort.
> +  //
> +  BASE_LIST_FOR_EACH_SAFE (FileEntry, NextFileEntry, FilesHead) {
> +    FileInfo = (EFI_SHELL_FILE_INFO *)FileEntry;
> +    //
> +    // Look up the SHELL_SORT_UNIQUE_NAME that matches FileInfo's name.
> +    //
> +    Alias = ((Order == ShellSortFileListByFileName) ?
> +             FileInfo->FileName :
> +             FileInfo->FullName);
> +    SortEntry = OrderedCollectionFind (Sort, Alias);
> +    ASSERT (SortEntry != NULL);
> +    Unique = OrderedCollectionUserStruct (SortEntry);
> +    //
> +    // Move FileInfo from (*FileList) to the end of the list of files whose
> +    // names all compare identical to FileInfo's name.
> +    //
> +    RemoveEntryList (&FileInfo->Link);
> +    InsertTailList (&Unique->SameNameList, &FileInfo->Link);  }
> +
> +  //
> +  // All EFI_SHELL_FILE_INFO objects originally in (*FileList) have
> + been  // distributed to Sort. Now migrate them back to (*FileList),
> + advancing in  // unique name order.
> +  //
> +  for (SortEntry = OrderedCollectionMin (Sort);
> +       SortEntry != NULL;
> +       SortEntry = OrderedCollectionNext (SortEntry)) {
> +    Unique = OrderedCollectionUserStruct (SortEntry);
> +    //
> +    // The first FileInfo encountered for each unique name goes back on
> +    // (*FileList) unconditionally. Further FileInfo instances for the same
> +    // unique name -- that is, duplicates -- are either returned to (*FileList)
> +    // or separated, dependent on the caller's request.
> +    //
> +    TargetFileList = FilesHead;
> +    BASE_LIST_FOR_EACH_SAFE (FileEntry, NextFileEntry, &Unique-
> >SameNameList) {
> +      RemoveEntryList (FileEntry);
> +      InsertTailList (TargetFileList, FileEntry);
> +      if (Duplicates != NULL) {
> +        TargetFileList = &Dupes->Link;
> +      }
> +    }
> +  }
> +
> +  //
> +  // We're done. If separation of duplicates has been requested, output
> + the  // list of duplicates -- and free that list at once, if it's
> + empty (i.e., if  // no duplicates have been found).
> +  //
> +  if (Duplicates != NULL) {
> +    if (IsListEmpty (&Dupes->Link)) {
> +      FreePool (Dupes);
> +      *Duplicates = NULL;
> +    } else {
> +      *Duplicates = Dupes;
> +    }
> +  }
> +  Status = EFI_SUCCESS;
> +
> +  //
> +  // Fall through.
> +  //
> +UninitSort:
> +  for (SortEntry = OrderedCollectionMin (Sort);
> +       SortEntry != NULL;
> +       SortEntry = NextSortEntry) {
> +    NextSortEntry = OrderedCollectionNext (SortEntry);
> +    OrderedCollectionDelete (Sort, SortEntry, &UniqueAsVoid);
> +    Unique = UniqueAsVoid;
> +    ASSERT (IsListEmpty (&Unique->SameNameList));
> +    FreePool (Unique);
> +  }
> +  OrderedCollectionUninit (Sort);
> +
> +  return Status;
> +}
> --
> 2.19.1.3.g30247aa5d201
>