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>

diff --git a/ShellPkg/Include/Library/ShellCommandLib.h b/ShellPkg/Include/Library/ShellCommandLib.h
index 63fcac82a2de2a387acdeee92db5188ccff6d056..bc1afed5e7f53e9a1cb985611818ee932645dbb1 100644 (file)
--- a/ShellPkg/Include/Library/ShellCommandLib.h
+++ b/ShellPkg/Include/Library/ShellCommandLib.h
@@ -714,4 +714,85 @@ CatSDumpHex (
   IN UINTN   DataSize,\r
   IN VOID    *UserData\r
   );\r
+\r
+//\r
+// Determines the ordering operation for ShellSortFileList().\r
+//\r
+typedef enum {\r
+  //\r
+  // Sort the EFI_SHELL_FILE_INFO objects by the FileName field, in increasing\r
+  // order, using gUnicodeCollation->StriColl().\r
+  //\r
+  ShellSortFileListByFileName,\r
+  //\r
+  // Sort the EFI_SHELL_FILE_INFO objects by the FullName field, in increasing\r
+  // order, using gUnicodeCollation->StriColl().\r
+  //\r
+  ShellSortFileListByFullName,\r
+  ShellSortFileListMax\r
+} SHELL_SORT_FILE_LIST;\r
+\r
+/**\r
+  Sort an EFI_SHELL_FILE_INFO list, optionally moving duplicates to a separate\r
+  list.\r
+\r
+  @param[in,out] FileList  The list of EFI_SHELL_FILE_INFO objects to sort.\r
+\r
+                           If FileList is NULL on input, then FileList is\r
+                           considered an empty, hence already sorted, list.\r
+\r
+                           Otherwise, if (*FileList) is NULL on input, then\r
+                           EFI_INVALID_PARAMETER is returned.\r
+\r
+                           Otherwise, the caller is responsible for having\r
+                           initialized (*FileList)->Link with\r
+                           InitializeListHead(). No other fields in the\r
+                           (**FileList) head element are accessed by this\r
+                           function.\r
+\r
+                           On output, (*FileList) is sorted according to Order.\r
+                           If Duplicates is NULL on input, then duplicate\r
+                           elements are preserved, sorted stably, on\r
+                           (*FileList). If Duplicates is not NULL on input,\r
+                           then duplicates are moved (stably sorted) to the\r
+                           new, dynamically allocated (*Duplicates) list.\r
+\r
+  @param[out] Duplicates   If Duplicates is NULL on input, (*FileList) will be\r
+                           a monotonically ordered list on output, with\r
+                           duplicates stably sorted.\r
+\r
+                           If Duplicates is not NULL on input, (*FileList) will\r
+                           be a strictly monotonically oredered list on output,\r
+                           with duplicates separated (stably sorted) to\r
+                           (*Duplicates). All fields except Link will be\r
+                           zero-initialized in the (**Duplicates) head element.\r
+                           If no duplicates exist, then (*Duplicates) is set to\r
+                           NULL on output.\r
+\r
+  @param[in] Order         Determines the comparison operation between\r
+                           EFI_SHELL_FILE_INFO objects.\r
+\r
+  @retval EFI_INVALID_PARAMETER  (UINTN)Order is greater than or equal to\r
+                                 (UINTN)ShellSortFileListMax. Neither the\r
+                                 (*FileList) nor the (*Duplicates) list has\r
+                                 been modified.\r
+\r
+  @retval EFI_INVALID_PARAMETER  (*FileList) was NULL on input. Neither the\r
+                                 (*FileList) nor the (*Duplicates) list has\r
+                                 been modified.\r
+\r
+  @retval EFI_OUT_OF_RESOURCES   Memory allocation failed. Neither the\r
+                                 (*FileList) nor the (*Duplicates) list has\r
+                                 been modified.\r
+\r
+  @retval EFI_SUCCESS            Sorting successful, including the case when\r
+                                 FileList is NULL on input.\r
+**/\r
+EFI_STATUS\r
+EFIAPI\r
+ShellSortFileList (\r
+  IN OUT EFI_SHELL_FILE_INFO  **FileList,\r
+     OUT EFI_SHELL_FILE_INFO  **Duplicates OPTIONAL,\r
+  IN     SHELL_SORT_FILE_LIST Order\r
+  );\r
 #endif //_SHELL_COMMAND_LIB_\r

diff --git a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
index 345808a1eac633aae01edb0a7dfbdb83f89777e0..b06d22592d33df8fa136c34f22ba93f2939c13e1 100644 (file)
--- a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
+++ b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.c
@@ -1909,3 +1909,315 @@ CatSDumpHex (
 \r
   return RetVal;\r
 }\r
+\r
+/**\r
+  ORDERED_COLLECTION_USER_COMPARE function for SHELL_SORT_UNIQUE_NAME objects.\r
+\r
+  @param[in] Unique1AsVoid  The first SHELL_SORT_UNIQUE_NAME object (Unique1),\r
+                            passed in as a pointer-to-VOID.\r
+\r
+  @param[in] Unique2AsVoid  The second SHELL_SORT_UNIQUE_NAME object (Unique2),\r
+                            passed in as a pointer-to-VOID.\r
+\r
+  @retval <0  If Unique1 compares less than Unique2.\r
+\r
+  @retval  0  If Unique1 compares equal to Unique2.\r
+\r
+  @retval >0  If Unique1 compares greater than Unique2.\r
+**/\r
+STATIC\r
+INTN\r
+EFIAPI\r
+UniqueNameCompare (\r
+  IN CONST VOID *Unique1AsVoid,\r
+  IN CONST VOID *Unique2AsVoid\r
+  )\r
+{\r
+  CONST SHELL_SORT_UNIQUE_NAME *Unique1;\r
+  CONST SHELL_SORT_UNIQUE_NAME *Unique2;\r
+\r
+  Unique1 = Unique1AsVoid;\r
+  Unique2 = Unique2AsVoid;\r
+\r
+  //\r
+  // We need to cast away CONST for EFI_UNICODE_COLLATION_STRICOLL.\r
+  //\r
+  return gUnicodeCollation->StriColl (\r
+                              gUnicodeCollation,\r
+                              (CHAR16 *)Unique1->Alias,\r
+                              (CHAR16 *)Unique2->Alias\r
+                              );\r
+}\r
+\r
+/**\r
+  ORDERED_COLLECTION_KEY_COMPARE function for SHELL_SORT_UNIQUE_NAME objects.\r
+\r
+  @param[in] UniqueAliasAsVoid  The CHAR16 string UniqueAlias, passed in as a\r
+                                pointer-to-VOID.\r
+\r
+  @param[in] UniqueAsVoid       The SHELL_SORT_UNIQUE_NAME object (Unique),\r
+                                passed in as a pointer-to-VOID.\r
+\r
+  @retval <0  If UniqueAlias compares less than Unique->Alias.\r
+\r
+  @retval  0  If UniqueAlias compares equal to Unique->Alias.\r
+\r
+  @retval >0  If UniqueAlias compares greater than Unique->Alias.\r
+**/\r
+STATIC\r
+INTN\r
+EFIAPI\r
+UniqueNameAliasCompare (\r
+  IN CONST VOID *UniqueAliasAsVoid,\r
+  IN CONST VOID *UniqueAsVoid\r
+  )\r
+{\r
+  CONST CHAR16                 *UniqueAlias;\r
+  CONST SHELL_SORT_UNIQUE_NAME *Unique;\r
+\r
+  UniqueAlias = UniqueAliasAsVoid;\r
+  Unique      = UniqueAsVoid;\r
+\r
+  //\r
+  // We need to cast away CONST for EFI_UNICODE_COLLATION_STRICOLL.\r
+  //\r
+  return gUnicodeCollation->StriColl (\r
+                              gUnicodeCollation,\r
+                              (CHAR16 *)UniqueAlias,\r
+                              (CHAR16 *)Unique->Alias\r
+                              );\r
+}\r
+\r
+/**\r
+  Sort an EFI_SHELL_FILE_INFO list, optionally moving duplicates to a separate\r
+  list.\r
+\r
+  @param[in,out] FileList  The list of EFI_SHELL_FILE_INFO objects to sort.\r
+\r
+                           If FileList is NULL on input, then FileList is\r
+                           considered an empty, hence already sorted, list.\r
+\r
+                           Otherwise, if (*FileList) is NULL on input, then\r
+                           EFI_INVALID_PARAMETER is returned.\r
+\r
+                           Otherwise, the caller is responsible for having\r
+                           initialized (*FileList)->Link with\r
+                           InitializeListHead(). No other fields in the\r
+                           (**FileList) head element are accessed by this\r
+                           function.\r
+\r
+                           On output, (*FileList) is sorted according to Order.\r
+                           If Duplicates is NULL on input, then duplicate\r
+                           elements are preserved, sorted stably, on\r
+                           (*FileList). If Duplicates is not NULL on input,\r
+                           then duplicates are moved (stably sorted) to the\r
+                           new, dynamically allocated (*Duplicates) list.\r
+\r
+  @param[out] Duplicates   If Duplicates is NULL on input, (*FileList) will be\r
+                           a monotonically ordered list on output, with\r
+                           duplicates stably sorted.\r
+\r
+                           If Duplicates is not NULL on input, (*FileList) will\r
+                           be a strictly monotonically oredered list on output,\r
+                           with duplicates separated (stably sorted) to\r
+                           (*Duplicates). All fields except Link will be\r
+                           zero-initialized in the (**Duplicates) head element.\r
+                           If no duplicates exist, then (*Duplicates) is set to\r
+                           NULL on output.\r
+\r
+  @param[in] Order         Determines the comparison operation between\r
+                           EFI_SHELL_FILE_INFO objects.\r
+\r
+  @retval EFI_INVALID_PARAMETER  (UINTN)Order is greater than or equal to\r
+                                 (UINTN)ShellSortFileListMax. Neither the\r
+                                 (*FileList) nor the (*Duplicates) list has\r
+                                 been modified.\r
+\r
+  @retval EFI_INVALID_PARAMETER  (*FileList) was NULL on input. Neither the\r
+                                 (*FileList) nor the (*Duplicates) list has\r
+                                 been modified.\r
+\r
+  @retval EFI_OUT_OF_RESOURCES   Memory allocation failed. Neither the\r
+                                 (*FileList) nor the (*Duplicates) list has\r
+                                 been modified.\r
+\r
+  @retval EFI_SUCCESS            Sorting successful, including the case when\r
+                                 FileList is NULL on input.\r
+**/\r
+EFI_STATUS\r
+EFIAPI\r
+ShellSortFileList (\r
+  IN OUT EFI_SHELL_FILE_INFO  **FileList,\r
+     OUT EFI_SHELL_FILE_INFO  **Duplicates OPTIONAL,\r
+  IN     SHELL_SORT_FILE_LIST Order\r
+  )\r
+{\r
+  LIST_ENTRY               *FilesHead;\r
+  ORDERED_COLLECTION       *Sort;\r
+  LIST_ENTRY               *FileEntry;\r
+  EFI_SHELL_FILE_INFO      *FileInfo;\r
+  SHELL_SORT_UNIQUE_NAME   *Unique;\r
+  EFI_STATUS               Status;\r
+  EFI_SHELL_FILE_INFO      *Dupes;\r
+  LIST_ENTRY               *NextFileEntry;\r
+  CONST CHAR16             *Alias;\r
+  ORDERED_COLLECTION_ENTRY *SortEntry;\r
+  LIST_ENTRY               *TargetFileList;\r
+  ORDERED_COLLECTION_ENTRY *NextSortEntry;\r
+  VOID                     *UniqueAsVoid;\r
+\r
+  if ((UINTN)Order >= (UINTN)ShellSortFileListMax) {\r
+    return EFI_INVALID_PARAMETER;\r
+  }\r
+\r
+  if (FileList == NULL) {\r
+    //\r
+    // FileList is considered empty, hence already sorted, with no duplicates.\r
+    //\r
+    if (Duplicates != NULL) {\r
+      *Duplicates = NULL;\r
+    }\r
+    return EFI_SUCCESS;\r
+  }\r
+\r
+  if (*FileList == NULL) {\r
+    return EFI_INVALID_PARAMETER;\r
+  }\r
+  FilesHead = &(*FileList)->Link;\r
+\r
+  //\r
+  // Collect all the unique names.\r
+  //\r
+  Sort = OrderedCollectionInit (UniqueNameCompare, UniqueNameAliasCompare);\r
+  if (Sort == NULL) {\r
+    return EFI_OUT_OF_RESOURCES;\r
+  }\r
+\r
+  BASE_LIST_FOR_EACH (FileEntry, FilesHead) {\r
+    FileInfo = (EFI_SHELL_FILE_INFO *)FileEntry;\r
+\r
+    //\r
+    // Try to record the name of this file as a unique name.\r
+    //\r
+    Unique = AllocatePool (sizeof (*Unique));\r
+    if (Unique == NULL) {\r
+      Status = EFI_OUT_OF_RESOURCES;\r
+      goto UninitSort;\r
+    }\r
+    Unique->Alias = ((Order == ShellSortFileListByFileName) ?\r
+                     FileInfo->FileName :\r
+                     FileInfo->FullName);\r
+    InitializeListHead (&Unique->SameNameList);\r
+\r
+    Status = OrderedCollectionInsert (Sort, NULL, Unique);\r
+    if (EFI_ERROR (Status)) {\r
+      //\r
+      // Only two errors are possible: memory allocation failed, or this name\r
+      // has been encountered before. In either case, the\r
+      // SHELL_SORT_UNIQUE_NAME object being constructed has to be released.\r
+      //\r
+      FreePool (Unique);\r
+      //\r
+      // Memory allocation failure is fatal, while having seen the same name\r
+      // before is normal.\r
+      //\r
+      if (Status == EFI_OUT_OF_RESOURCES) {\r
+        goto UninitSort;\r
+      }\r
+      ASSERT (Status == EFI_ALREADY_STARTED);\r
+    }\r
+  }\r
+\r
+  //\r
+  // If separation of duplicates has been requested, allocate the list for\r
+  // them.\r
+  //\r
+  if (Duplicates != NULL) {\r
+    Dupes = AllocateZeroPool (sizeof (*Dupes));\r
+    if (Dupes == NULL) {\r
+      Status = EFI_OUT_OF_RESOURCES;\r
+      goto UninitSort;\r
+    }\r
+    InitializeListHead (&Dupes->Link);\r
+  }\r
+\r
+  //\r
+  // No memory allocation beyond this point; thus, no chance to fail. We can\r
+  // now migrate the EFI_SHELL_FILE_INFO objects from (*FileList) to Sort.\r
+  //\r
+  BASE_LIST_FOR_EACH_SAFE (FileEntry, NextFileEntry, FilesHead) {\r
+    FileInfo = (EFI_SHELL_FILE_INFO *)FileEntry;\r
+    //\r
+    // Look up the SHELL_SORT_UNIQUE_NAME that matches FileInfo's name.\r
+    //\r
+    Alias = ((Order == ShellSortFileListByFileName) ?\r
+             FileInfo->FileName :\r
+             FileInfo->FullName);\r
+    SortEntry = OrderedCollectionFind (Sort, Alias);\r
+    ASSERT (SortEntry != NULL);\r
+    Unique = OrderedCollectionUserStruct (SortEntry);\r
+    //\r
+    // Move FileInfo from (*FileList) to the end of the list of files whose\r
+    // names all compare identical to FileInfo's name.\r
+    //\r
+    RemoveEntryList (&FileInfo->Link);\r
+    InsertTailList (&Unique->SameNameList, &FileInfo->Link);\r
+  }\r
+\r
+  //\r
+  // All EFI_SHELL_FILE_INFO objects originally in (*FileList) have been\r
+  // distributed to Sort. Now migrate them back to (*FileList), advancing in\r
+  // unique name order.\r
+  //\r
+  for (SortEntry = OrderedCollectionMin (Sort);\r
+       SortEntry != NULL;\r
+       SortEntry = OrderedCollectionNext (SortEntry)) {\r
+    Unique = OrderedCollectionUserStruct (SortEntry);\r
+    //\r
+    // The first FileInfo encountered for each unique name goes back on\r
+    // (*FileList) unconditionally. Further FileInfo instances for the same\r
+    // unique name -- that is, duplicates -- are either returned to (*FileList)\r
+    // or separated, dependent on the caller's request.\r
+    //\r
+    TargetFileList = FilesHead;\r
+    BASE_LIST_FOR_EACH_SAFE (FileEntry, NextFileEntry, &Unique->SameNameList) {\r
+      RemoveEntryList (FileEntry);\r
+      InsertTailList (TargetFileList, FileEntry);\r
+      if (Duplicates != NULL) {\r
+        TargetFileList = &Dupes->Link;\r
+      }\r
+    }\r
+  }\r
+\r
+  //\r
+  // We're done. If separation of duplicates has been requested, output the\r
+  // list of duplicates -- and free that list at once, if it's empty (i.e., if\r
+  // no duplicates have been found).\r
+  //\r
+  if (Duplicates != NULL) {\r
+    if (IsListEmpty (&Dupes->Link)) {\r
+      FreePool (Dupes);\r
+      *Duplicates = NULL;\r
+    } else {\r
+      *Duplicates = Dupes;\r
+    }\r
+  }\r
+  Status = EFI_SUCCESS;\r
+\r
+  //\r
+  // Fall through.\r
+  //\r
+UninitSort:\r
+  for (SortEntry = OrderedCollectionMin (Sort);\r
+       SortEntry != NULL;\r
+       SortEntry = NextSortEntry) {\r
+    NextSortEntry = OrderedCollectionNext (SortEntry);\r
+    OrderedCollectionDelete (Sort, SortEntry, &UniqueAsVoid);\r
+    Unique = UniqueAsVoid;\r
+    ASSERT (IsListEmpty (&Unique->SameNameList));\r
+    FreePool (Unique);\r
+  }\r
+  OrderedCollectionUninit (Sort);\r
+\r
+  return Status;\r
+}\r

diff --git a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
index 8ecc2f6bf5a2824b3760a9d1e3ec62a4a7606424..0ca291e4f9bf94ce2acf1a7430529f8b59bdb7b1 100644 (file)
--- a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
+++ b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.h
@@ -39,6 +39,7 @@
 #include <Library/HiiLib.h>\r
 #include <Library/UefiBootServicesTableLib.h>\r
 #include <Library/UefiLib.h>\r
+#include <Library/OrderedCollectionLib.h>\r
 \r
 typedef struct{\r
   LIST_ENTRY                  Link;\r
@@ -60,6 +61,24 @@ typedef struct {
   CHAR16            *Path;\r
 } SHELL_COMMAND_FILE_HANDLE;\r
 \r
+//\r
+// Collects multiple EFI_SHELL_FILE_INFO objects that share the same name.\r
+//\r
+typedef struct {\r
+  //\r
+  // A string that compares equal to either the FileName or the FullName fields\r
+  // of all EFI_SHELL_FILE_INFO objects on SameNameList, according to\r
+  // gUnicodeCollation->StriColl(). The string is not dynamically allocated;\r
+  // instead, it *aliases* the FileName or FullName field of the\r
+  // EFI_SHELL_FILE_INFO object that was first encountered with this name.\r
+  //\r
+  CONST CHAR16 *Alias;\r
+  //\r
+  // A list of EFI_SHELL_FILE_INFO objects whose FileName or FullName fields\r
+  // compare equal to Alias, according to gUnicodeCollation->StriColl().\r
+  //\r
+  LIST_ENTRY SameNameList;\r
+} SHELL_SORT_UNIQUE_NAME;\r
 \r
 #endif //_UEFI_COMMAND_LIB_INTERNAL_HEADER_\r
 \r

diff --git a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
index a1b5601c96b689110d2f9470e592019cfa0ce7ba..08ca7cb78842eb11dcfae9d3a4459cd6c65cfa6c 100644 (file)
--- a/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
+++ b/ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf
@@ -42,6 +42,7 @@
   ShellLib\r
   HiiLib\r
   HandleParsingLib\r
+  OrderedCollectionLib\r
 \r
 [Protocols]\r
   gEfiUnicodeCollation2ProtocolGuid                       ## CONSUMES\r

diff --git a/ShellPkg/ShellPkg.dsc b/ShellPkg/ShellPkg.dsc
index c42bc9464a0f7be111ee3086a664506c8288928c..a8b6de334284d210e5a4673d3b7d8d63ec65373c 100644 (file)
--- a/ShellPkg/ShellPkg.dsc
+++ b/ShellPkg/ShellPkg.dsc
@@ -47,6 +47,7 @@
   ShellCommandLib|ShellPkg/Library/UefiShellCommandLib/UefiShellCommandLib.inf\r
   ShellCEntryLib|ShellPkg/Library/UefiShellCEntryLib/UefiShellCEntryLib.inf\r
   HandleParsingLib|ShellPkg/Library/UefiHandleParsingLib/UefiHandleParsingLib.inf\r
+  OrderedCollectionLib|MdePkg/Library/BaseOrderedCollectionRedBlackTreeLib/BaseOrderedCollectionRedBlackTreeLib.inf\r
 \r
   PeCoffGetEntryPointLib|MdePkg/Library/BasePeCoffGetEntryPointLib/BasePeCoffGetEntryPointLib.inf\r
   BcfgCommandLib|ShellPkg/Library/UefiShellBcfgCommandLib/UefiShellBcfgCommandLib.inf\r