Adding new library instance for SortLib with built in function for sorting device...

git-svn-id: https://edk2.svn.sourceforge.net/svnroot/edk2/trunk/edk2@9399 6f19259b-4bc3-4df7-8a09-765794883524

diff --git a/ShellPkg/Library/UefiSortLib/UefiSortLib.c b/ShellPkg/Library/UefiSortLib/UefiSortLib.c
new file mode 100644 (file)
index 0000000..e7a8d1e
--- /dev/null
+++ b/ShellPkg/Library/UefiSortLib/UefiSortLib.c
@@ -0,0 +1,254 @@
+/** @file\r
+  Library used for sorting routines.\r
+\r
+Copyright (c) 2009, Intel Corporation\r
+All rights reserved. This program and the accompanying materials\r
+are licensed and made available under the terms and conditions of the BSD License\r
+which accompanies this distribution.  The full text of the license may be found at\r
+http://opensource.org/licenses/bsd-license.php\r
+\r
+THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
+WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
+\r
+**/\r
+\r
+#include <Uefi.h>\r
+\r
+#include <Protocol/UnicodeCollation.h>\r
+#include <Protocol/DevicePath.h>\r
+#include <Protocol/DevicePathToText.h>\r
+\r
+#include <Library/UefiBootServicesTableLib.h>\r
+#include <Library/BaseLib.h>\r
+#include <Library/BaseMemoryLib.h>\r
+#include <Library/DebugLib.h>\r
+#include <Library/MemoryAllocationLib.h>\r
+#include <Library/SortLib.h> \r
+\r
+/**\r
+  Worker function for QuickSorting.  This function is identical to PerformQuickSort, \r
+  except that is uses the pre-allocated buffer so the in place sorting does not need to \r
+  allocate and free buffers constantly.\r
+\r
+  Each element must be equal sized.\r
+\r
+  if BufferToSort is NULL, then ASSERT.\r
+  if CompareFunction is NULL, then ASSERT.\r
+  if Buffer is NULL, then ASSERT.\r
+\r
+  if Count is < 2 then perform no action.\r
+  if Size is < 1 then perform no action.\r
+\r
+  @param[in,out] BufferToSort   on call a Buffer of (possibly sorted) elements\r
+                                on return a buffer of sorted elements\r
+  @param[in] Count              the number of elements in the buffer to sort\r
+  @param[in] ElementSize        Size of an element in bytes\r
+  @param[in] CompareFunction    The function to call to perform the comparison \r
+                                of any 2 elements\r
+  @param[in] Buffer             Buffer of size ElementSize for use in swapping\r
+**/\r
+VOID\r
+EFIAPI\r
+QuickSortWorker (\r
+  IN OUT VOID                           *BufferToSort,\r
+  IN CONST UINTN                        Count,\r
+  IN CONST UINTN                        ElementSize,\r
+  IN       SORT_COMPARE                 CompareFunction,\r
+  IN VOID                               *Buffer\r
+  ){\r
+  VOID        *Pivot;\r
+  UINTN       LoopCount;\r
+  UINTN       NextSwapLocation;\r
+\r
+  ASSERT(BufferToSort     != NULL);\r
+  ASSERT(CompareFunction  != NULL);\r
+  ASSERT(Buffer  != NULL);\r
+\r
+  if ( Count < 2 \r
+    || ElementSize  < 1\r
+    ){\r
+    return;\r
+  }\r
+\r
+  NextSwapLocation = 0;\r
+\r
+  //\r
+  // pick a pivot (we choose last element)\r
+  //\r
+  Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));\r
+\r
+  //\r
+  // Now get the pivot such that all on "left" are below it\r
+  // and everything "right" are above it\r
+  //\r
+  for ( LoopCount = 0\r
+      ; LoopCount < Count -1 \r
+      ; LoopCount++\r
+      ){\r
+    //\r
+    // if the element is less than the pivot\r
+    //\r
+    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r
+      //\r
+      // swap \r
+      //\r
+      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
+      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);\r
+      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);\r
+\r
+      //\r
+      // increment NextSwapLocation\r
+      // \r
+      NextSwapLocation++;\r
+    }\r
+  }\r
+  //\r
+  // swap pivot to it's final position (NextSwapLocaiton)\r
+  //\r
+  CopyMem (Buffer, Pivot, ElementSize);\r
+  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
+  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);\r
+\r
+  //\r
+  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element \r
+  // IE list is sorted left half, pivot element, sorted right half...\r
+  //\r
+  QuickSortWorker(\r
+    BufferToSort, \r
+    NextSwapLocation, \r
+    ElementSize, \r
+    CompareFunction,\r
+    Buffer);\r
+\r
+  QuickSortWorker(\r
+    (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,\r
+    Count - NextSwapLocation - 1, \r
+    ElementSize, \r
+    CompareFunction,\r
+    Buffer);\r
+\r
+  return;\r
+}\r
+/**\r
+  Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r
+\r
+  Each element must be equal sized.\r
+\r
+  if BufferToSort is NULL, then ASSERT.\r
+  if CompareFunction is NULL, then ASSERT.\r
+\r
+  if Count is < 2 then perform no action.\r
+  if Size is < 1 then perform no action.\r
+\r
+  @param[in,out] BufferToSort   on call a Buffer of (possibly sorted) elements\r
+                                on return a buffer of sorted elements\r
+  @param[in] Count              the number of elements in the buffer to sort\r
+  @param[in] ElementSize        Size of an element in bytes\r
+  @param[in] CompareFunction    The function to call to perform the comparison \r
+                                of any 2 elements\r
+**/\r
+VOID\r
+EFIAPI\r
+PerformQuickSort (\r
+  IN OUT VOID                           *BufferToSort,\r
+  IN CONST UINTN                        Count,\r
+  IN CONST UINTN                        ElementSize,\r
+  IN       SORT_COMPARE                 CompareFunction\r
+  ){\r
+  VOID  *Buffer;\r
+\r
+  ASSERT(BufferToSort     != NULL);\r
+  ASSERT(CompareFunction  != NULL);\r
+\r
+  Buffer = AllocatePool(ElementSize);\r
+  ASSERT(Buffer != NULL);\r
+\r
+  QuickSortWorker(\r
+    BufferToSort,\r
+    Count,\r
+    ElementSize,\r
+    CompareFunction,\r
+    Buffer);\r
+\r
+  FreePool(Buffer);\r
+  return;\r
+}\r
+\r
+/**\r
+  function to compare 2 device paths for use in QuickSort\r
+\r
+  @param[in] Buffer1            pointer to Device Path poiner to compare\r
+  @param[in] Buffer2            pointer to second DevicePath pointer to compare\r
+\r
+  @retval 0                     Buffer1 equal to Buffer2\r
+  @return < 0                   Buffer1 is less than Buffer2\r
+  @return > 0                   Buffer1 is greater than Buffer2                     \r
+**/\r
+INTN\r
+DevicePathCompare (\r
+  IN  VOID             *Buffer1,\r
+  IN  VOID             *Buffer2\r
+  ){\r
+  EFI_DEVICE_PATH_PROTOCOL  *DevicePath1;\r
+  EFI_DEVICE_PATH_PROTOCOL  *DevicePath2;\r
+  CHAR16                    *TextPath1;\r
+  CHAR16                    *TextPath2;\r
+  EFI_STATUS                Status;\r
+  INTN                      RetVal;\r
+   \r
+  STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL *DevicePathToText = NULL;\r
+  STATIC EFI_UNICODE_COLLATION_PROTOCOL   *UnicodeCollation = NULL;\r
+\r
+  DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;\r
+  DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;\r
+\r
+  if (DevicePath1 == NULL) {\r
+    if (DevicePath2 == NULL) {\r
+      return 0;\r
+    }\r
+\r
+    return -1;\r
+  }\r
+\r
+  if (DevicePath2 == NULL) {\r
+    return 1;\r
+  }\r
+  \r
+  if (DevicePathToText == NULL) {\r
+    Status = gBS->LocateProtocol(\r
+      &gEfiDevicePathToTextProtocolGuid,\r
+      NULL,\r
+      (VOID**)&DevicePathToText);\r
+\r
+    ASSERT_EFI_ERROR(Status);\r
+  }\r
+\r
+  if (UnicodeCollation == NULL) {\r
+    Status = gBS->LocateProtocol(\r
+      &gEfiUnicodeCollation2ProtocolGuid,\r
+      NULL,\r
+      (VOID**)&UnicodeCollation);\r
+\r
+    ASSERT_EFI_ERROR(Status);\r
+  }\r
+\r
+  TextPath1 = DevicePathToText->ConvertDevicePathToText(\r
+    DevicePath1,\r
+    FALSE,\r
+    FALSE);\r
+\r
+  TextPath2 = DevicePathToText->ConvertDevicePathToText(\r
+    DevicePath2,\r
+    FALSE,\r
+    FALSE);\r
+  \r
+  RetVal = UnicodeCollation->StriColl(\r
+    UnicodeCollation,\r
+    TextPath1,\r
+    TextPath2);\r
+\r
+  FreePool(TextPath1);\r
+  FreePool(TextPath2);\r
+\r
+  return (RetVal);\r
+}
\ No newline at end of file

diff --git a/ShellPkg/Library/UefiSortLib/UefiSortLib.inf b/ShellPkg/Library/UefiSortLib/UefiSortLib.inf
new file mode 100644 (file)
index 0000000..a93c42d
--- /dev/null
+++ b/ShellPkg/Library/UefiSortLib/UefiSortLib.inf
@@ -0,0 +1,49 @@
+#/** @file\r
+#   Library used for sorting routines.\r
+#\r
+# Copyright (c) 2009, Intel Corporation.\r
+#\r
+#  All rights reserved. This program and the accompanying materials\r
+#  are licensed and made available under the terms and conditions of the BSD License\r
+#  which accompanies this distribution. The full text of the license may be found at\r
+#  http://opensource.org/licenses/bsd-license.php\r
+#  THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
+#  WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
+#\r
+#\r
+#**/\r
+\r
+[Defines]\r
+  INF_VERSION                    = 0x00010006\r
+  BASE_NAME                      = UefiSortLib\r
+  FILE_GUID                      = 4264A823-45A3-42db-B92C-AA078555CBD3\r
+  MODULE_TYPE                    = UEFI_DRIVER\r
+  VERSION_STRING                 = 1.0\r
+  LIBRARY_CLASS                  = SORTLib|UEFI_APPLICATION UEFI_DRIVER\r
+\r
+#\r
+#  VALID_ARCHITECTURES           = IA32 X64 IPF EBC\r
+#\r
+\r
+[Sources.common]\r
+  UefiSortLib.c\r
+\r
+[Packages]\r
+  MdePkg/MdePkg.dec\r
+  ShellPkg/ShellPkg.dec\r
+\r
+[LibraryClasses]\r
+  MemoryAllocationLib\r
+  BaseLib\r
+  BaseMemoryLib\r
+  DebugLib\r
+  UefiBootServicesTableLib\r
+\r
+[Protocols]\r
+  gEfiUnicodeCollation2ProtocolGuid                       # ALWAYS_CONSUMED\r
+  gEfiDevicePathProtocolGuid                              # ALWAYS_CONSUMED\r
+  gEfiDevicePathToTextProtocolGuid                        # ALWAYS_CONSUMED\r
+\r
+[Guids]\r
+\r
+[Pcd.common]\r