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
 125     ASSERT_EFI_ERROR (Status);
 126   }
 127
 128   TextPath1 = ConvertDevicePathToText (
 129                 DevicePath1,
 130                 FALSE,
 131                 FALSE
 132                 );
 133
 134   TextPath2 = ConvertDevicePathToText (
 135                 DevicePath2,
 136                 FALSE,
 137                 FALSE
 138                 );
 139
 140   if (TextPath1 == NULL) {
 141     RetVal = -1;
 142   } else if (TextPath2 == NULL) {
 143     RetVal = 1;
 144   } else {
 145     RetVal = mUnicodeCollation->StriColl (
 146                                   mUnicodeCollation,
 147                                   TextPath1,
 148                                   TextPath2
 149                                   );
 150   }
 151
 152   USL_FREE_NON_NULL (TextPath1);
 153   USL_FREE_NON_NULL (TextPath2);
 154
 155   return (RetVal);
 156 }
 157
 158 /**
 159   Function to compare 2 strings without regard to case of the characters.
 160
 161   @param[in] Buffer1            Pointer to String to compare.
 162   @param[in] Buffer2            Pointer to second String to compare.
 163
 164   @retval 0                     Buffer1 equal to Buffer2.
 165   @retval <0                    Buffer1 is less than Buffer2.
 166   @retval >0                    Buffer1 is greater than Buffer2.
 167 **/
 168 INTN
 169 EFIAPI
 170 StringNoCaseCompare (
 171   IN  CONST VOID  *Buffer1,
 172   IN  CONST VOID  *Buffer2
 173   )
 174 {
 175   EFI_STATUS  Status;
 176
 177   if (mUnicodeCollation == NULL) {
 178     Status = gBS->LocateProtocol (
 179                     &gEfiUnicodeCollation2ProtocolGuid,
 180                     NULL,
 181                     (VOID **)&mUnicodeCollation
 182                     );
 183
 184     ASSERT_EFI_ERROR (Status);
 185   }
 186
 187   return (mUnicodeCollation->StriColl (
 188                                mUnicodeCollation,
 189                                *(CHAR16 **)Buffer1,
 190                                *(CHAR16 **)Buffer2
 191                                ));
 192 }
 193
 194 /**
 195   Function to compare 2 strings.
 196
 197   @param[in] Buffer1            Pointer to String to compare (CHAR16**).
 198   @param[in] Buffer2            Pointer to second String to compare (CHAR16**).
 199
 200   @retval 0                     Buffer1 equal to Buffer2.
 201   @retval <0                    Buffer1 is less than Buffer2.
 202   @retval >0                    Buffer1 is greater than Buffer2.
 203 **/
 204 INTN
 205 EFIAPI
 206 StringCompare (
 207   IN  CONST VOID  *Buffer1,
 208   IN  CONST VOID  *Buffer2
 209   )
 210 {
 211   return (StrCmp (
 212             *(CHAR16 **)Buffer1,
 213             *(CHAR16 **)Buffer2
 214             ));
 215 }