MdeModulePkg/Library/UefiSortLib/UefiSortLib.c

   1 /** @file
   2   Library used for sorting routines.
   3
   4   Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
   5   SPDX-License-Identifier: BSD-2-Clause-Patent
   6
   7 **/
   8
   9 #include <Uefi.h>
  10
  11 #include <Protocol/UnicodeCollation.h>
  12 #include <Protocol/DevicePath.h>
  13
  14 #include <Library/UefiBootServicesTableLib.h>
  15 #include <Library/BaseLib.h>
  16 #include <Library/BaseMemoryLib.h>
  17 #include <Library/DebugLib.h>
  18 #include <Library/MemoryAllocationLib.h>
  19 #include <Library/SortLib.h>
  20 #include <Library/DevicePathLib.h>
  21
  22 STATIC EFI_UNICODE_COLLATION_PROTOCOL   *mUnicodeCollation = NULL;
  23
  24 #define USL_FREE_NON_NULL(Pointer)  \
  25 {                                     \
  26   if ((Pointer) != NULL) {            \
  27   FreePool((Pointer));                \
  28   (Pointer) = NULL;                   \
  29   }                                   \
  30 }
  31
  32 /**
  33   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
  34
  35   Each element must be equal sized.
  36
  37   if BufferToSort is NULL, then ASSERT.
  38   if CompareFunction is NULL, then ASSERT.
  39
  40   if Count is < 2 then perform no action.
  41   if Size is < 1 then perform no action.
  42
  43   @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
  44                                  on return a buffer of sorted elements
  45   @param[in] Count               the number of elements in the buffer to sort
  46   @param[in] ElementSize         Size of an element in bytes
  47   @param[in] CompareFunction     The function to call to perform the comparison
  48                                  of any 2 elements
  49 **/
  50 VOID
  51 EFIAPI
  52 PerformQuickSort (
  53   IN OUT VOID                           *BufferToSort,
  54   IN CONST UINTN                        Count,
  55   IN CONST UINTN                        ElementSize,
  56   IN       SORT_COMPARE                 CompareFunction
  57   )
  58 {
  59   VOID  *Buffer;
  60
  61   ASSERT(BufferToSort     != NULL);
  62   ASSERT(CompareFunction  != NULL);
  63
  64   Buffer = AllocateZeroPool(ElementSize);
  65   ASSERT(Buffer != NULL);
  66
  67   QuickSort (
  68     BufferToSort,
  69     Count,
  70     ElementSize,
  71     CompareFunction,
  72     Buffer
  73     );
  74
  75   FreePool(Buffer);
  76   return;
  77 }
  78
  79 /**
  80   Function to compare 2 device paths for use in QuickSort.
  81
  82   @param[in] Buffer1            pointer to Device Path poiner to compare
  83   @param[in] Buffer2            pointer to second DevicePath pointer to compare
  84
  85   @retval 0                     Buffer1 equal to Buffer2
  86   @retval <0                    Buffer1 is less than Buffer2
  87   @retval >0                    Buffer1 is greater than Buffer2
  88 **/
  89 INTN
  90 EFIAPI
  91 DevicePathCompare (
  92   IN  CONST VOID             *Buffer1,
  93   IN  CONST VOID             *Buffer2
  94   )
  95 {
  96   EFI_DEVICE_PATH_PROTOCOL  *DevicePath1;
  97   EFI_DEVICE_PATH_PROTOCOL  *DevicePath2;
  98   CHAR16                    *TextPath1;
  99   CHAR16                    *TextPath2;
 100   EFI_STATUS                Status;
 101   INTN                      RetVal;
 102
 103   DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;
 104   DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;
 105
 106   if (DevicePath1 == NULL) {
 107     if (DevicePath2 == NULL) {
 108       return 0;
 109     }
 110
 111     return -1;
 112   }
 113
 114   if (DevicePath2 == NULL) {
 115     return 1;
 116   }
 117
 118   if (mUnicodeCollation == NULL) {
 119     Status = gBS->LocateProtocol(
 120       &gEfiUnicodeCollation2ProtocolGuid,
 121       NULL,
 122       (VOID**)&mUnicodeCollation);
 123
 124     ASSERT_EFI_ERROR(Status);
 125   }
 126
 127   TextPath1 = ConvertDevicePathToText(
 128     DevicePath1,
 129     FALSE,
 130     FALSE);
 131
 132   TextPath2 = ConvertDevicePathToText(
 133     DevicePath2,
 134     FALSE,
 135     FALSE);
 136
 137   if (TextPath1 == NULL) {
 138     RetVal = -1;
 139   } else if (TextPath2 == NULL) {
 140     RetVal = 1;
 141   } else {
 142     RetVal = mUnicodeCollation->StriColl(
 143       mUnicodeCollation,
 144       TextPath1,
 145       TextPath2);
 146   }
 147
 148   USL_FREE_NON_NULL(TextPath1);
 149   USL_FREE_NON_NULL(TextPath2);
 150
 151   return (RetVal);
 152 }
 153
 154 /**
 155   Function to compare 2 strings without regard to case of the characters.
 156
 157   @param[in] Buffer1            Pointer to String to compare.
 158   @param[in] Buffer2            Pointer to second String to compare.
 159
 160   @retval 0                     Buffer1 equal to Buffer2.
 161   @retval <0                    Buffer1 is less than Buffer2.
 162   @retval >0                    Buffer1 is greater than Buffer2.
 163 **/
 164 INTN
 165 EFIAPI
 166 StringNoCaseCompare (
 167   IN  CONST VOID             *Buffer1,
 168   IN  CONST VOID             *Buffer2
 169   )
 170 {
 171   EFI_STATUS                Status;
 172   if (mUnicodeCollation == NULL) {
 173     Status = gBS->LocateProtocol(
 174       &gEfiUnicodeCollation2ProtocolGuid,
 175       NULL,
 176       (VOID**)&mUnicodeCollation);
 177
 178     ASSERT_EFI_ERROR(Status);
 179   }
 180
 181   return (mUnicodeCollation->StriColl(
 182     mUnicodeCollation,
 183     *(CHAR16**)Buffer1,
 184     *(CHAR16**)Buffer2));
 185 }
 186
 187
 188 /**
 189   Function to compare 2 strings.
 190
 191   @param[in] Buffer1            Pointer to String to compare (CHAR16**).
 192   @param[in] Buffer2            Pointer to second String to compare (CHAR16**).
 193
 194   @retval 0                     Buffer1 equal to Buffer2.
 195   @retval <0                    Buffer1 is less than Buffer2.
 196   @retval >0                    Buffer1 is greater than Buffer2.
 197 **/
 198 INTN
 199 EFIAPI
 200 StringCompare (
 201   IN  CONST VOID                *Buffer1,
 202   IN  CONST VOID                *Buffer2
 203   )
 204 {
 205   return (StrCmp(
 206     *(CHAR16**)Buffer1,
 207     *(CHAR16**)Buffer2));
 208 }