\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
projects / mirror_edk2.git / blobdiff