MdeModulePkg/SortLib: Add QuickSort function on BaseLib

[mirror_edk2.git] / MdeModulePkg / Library / UefiSortLib / UefiSortLib.c

/** @file\r
  Library used for sorting routines.\r
\r
  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>\r
  SPDX-License-Identifier: BSD-2-Clause-Patent\r
\r
**/\r
\r
#include <Uefi.h>\r
\r
#include <Protocol/UnicodeCollation.h>\r
#include <Protocol/DevicePath.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
#include <Library/DevicePathLib.h>\r
\r
STATIC EFI_UNICODE_COLLATION_PROTOCOL   *mUnicodeCollation = NULL;\r
\r
#define USL_FREE_NON_NULL(Pointer)  \\r
{                                     \\r
  if ((Pointer) != NULL) {            \\r
  FreePool((Pointer));                \\r
  (Pointer) = NULL;                   \\r
  }                                   \\r
}\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
{\r
  VOID  *Buffer;\r
\r
  ASSERT(BufferToSort     != NULL);\r
  ASSERT(CompareFunction  != NULL);\r
\r
  Buffer = AllocateZeroPool(ElementSize);\r
  ASSERT(Buffer != NULL);\r
\r
  QuickSort (\r
    BufferToSort,\r
    Count,\r
    ElementSize,\r
    CompareFunction,\r
    Buffer\r
    );\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
  @retval <0                    Buffer1 is less than Buffer2\r
  @retval >0                    Buffer1 is greater than Buffer2\r
**/\r
INTN\r
EFIAPI\r
DevicePathCompare (\r
  IN  CONST VOID             *Buffer1,\r
  IN  CONST VOID             *Buffer2\r
  )\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
  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 (mUnicodeCollation == NULL) {\r
    Status = gBS->LocateProtocol(\r
      &gEfiUnicodeCollation2ProtocolGuid,\r
      NULL,\r
      (VOID**)&mUnicodeCollation);\r
\r
    ASSERT_EFI_ERROR(Status);\r
  }\r
\r
  TextPath1 = ConvertDevicePathToText(\r
    DevicePath1,\r
    FALSE,\r
    FALSE);\r
\r
  TextPath2 = ConvertDevicePathToText(\r
    DevicePath2,\r
    FALSE,\r
    FALSE);\r
\r
  if (TextPath1 == NULL) {\r
    RetVal = -1;\r
  } else if (TextPath2 == NULL) {\r
    RetVal = 1;\r
  } else {\r
    RetVal = mUnicodeCollation->StriColl(\r
      mUnicodeCollation,\r
      TextPath1,\r
      TextPath2);\r
  }\r
\r
  USL_FREE_NON_NULL(TextPath1);\r
  USL_FREE_NON_NULL(TextPath2);\r
\r
  return (RetVal);\r
}\r
\r
/**\r
  Function to compare 2 strings without regard to case of the characters.\r
\r
  @param[in] Buffer1            Pointer to String to compare.\r
  @param[in] Buffer2            Pointer to second String to compare.\r
\r
  @retval 0                     Buffer1 equal to Buffer2.\r
  @retval <0                    Buffer1 is less than Buffer2.\r
  @retval >0                    Buffer1 is greater than Buffer2.\r
**/\r
INTN\r
EFIAPI\r
StringNoCaseCompare (\r
  IN  CONST VOID             *Buffer1,\r
  IN  CONST VOID             *Buffer2\r
  )\r
{\r
  EFI_STATUS                Status;\r
  if (mUnicodeCollation == NULL) {\r
    Status = gBS->LocateProtocol(\r
      &gEfiUnicodeCollation2ProtocolGuid,\r
      NULL,\r
      (VOID**)&mUnicodeCollation);\r
\r
    ASSERT_EFI_ERROR(Status);\r
  }\r
\r
  return (mUnicodeCollation->StriColl(\r
    mUnicodeCollation,\r
    *(CHAR16**)Buffer1,\r
    *(CHAR16**)Buffer2));\r
}\r
\r
\r
/**\r
  Function to compare 2 strings.\r
\r
  @param[in] Buffer1            Pointer to String to compare (CHAR16**).\r
  @param[in] Buffer2            Pointer to second String to compare (CHAR16**).\r
\r
  @retval 0                     Buffer1 equal to Buffer2.\r
  @retval <0                    Buffer1 is less than Buffer2.\r
  @retval >0                    Buffer1 is greater than Buffer2.\r
**/\r
INTN\r
EFIAPI\r
StringCompare (\r
  IN  CONST VOID                *Buffer1,\r
  IN  CONST VOID                *Buffer2\r
  )\r
{\r
  return (StrCmp(\r
    *(CHAR16**)Buffer1,\r
    *(CHAR16**)Buffer2));\r
}\r