MdeModulePkg/Library/UefiSortLib/UefiSortLib.c

   1 /** @file
   2   Library used for sorting routines.
   3
   4   Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>
   5   This program and the accompanying materials
   6   are licensed and made available under the terms and conditions of the BSD License
   7   which accompanies this distribution.  The full text of the license may be found at
   8   http://opensource.org/licenses/bsd-license.php
   9
  10   THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,
  11   WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.
  12
  13 **/
  14
  15 #include <Uefi.h>
  16
  17 #include <Protocol/UnicodeCollation.h>
  18 #include <Protocol/DevicePath.h>
  19
  20 #include <Library/UefiBootServicesTableLib.h>
  21 #include <Library/BaseLib.h>
  22 #include <Library/BaseMemoryLib.h>
  23 #include <Library/DebugLib.h>
  24 #include <Library/MemoryAllocationLib.h>
  25 #include <Library/SortLib.h>
  26 #include <Library/DevicePathLib.h>
  27
  28 STATIC EFI_UNICODE_COLLATION_PROTOCOL   *mUnicodeCollation = NULL;
  29
  30 #define USL_FREE_NON_NULL(Pointer)  \
  31 {                                     \
  32   if ((Pointer) != NULL) {            \
  33   FreePool((Pointer));                \
  34   (Pointer) = NULL;                   \
  35   }                                   \
  36 }
  37
  38 /**
  39   Worker function for QuickSorting.  This function is identical to PerformQuickSort,
  40   except that is uses the pre-allocated buffer so the in place sorting does not need to
  41   allocate and free buffers constantly.
  42
  43   Each element must be equal sized.
  44
  45   if BufferToSort is NULL, then ASSERT.
  46   if CompareFunction is NULL, then ASSERT.
  47   if Buffer is NULL, then ASSERT.
  48
  49   if Count is < 2 then perform no action.
  50   if Size is < 1 then perform no action.
  51
  52   @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
  53                                  on return a buffer of sorted elements
  54   @param[in] Count               the number of elements in the buffer to sort
  55   @param[in] ElementSize         Size of an element in bytes
  56   @param[in] CompareFunction     The function to call to perform the comparison
  57                                  of any 2 elements
  58   @param[in] Buffer              Buffer of size ElementSize for use in swapping
  59 **/
  60 VOID
  61 EFIAPI
  62 QuickSortWorker (
  63   IN OUT VOID                           *BufferToSort,
  64   IN CONST UINTN                        Count,
  65   IN CONST UINTN                        ElementSize,
  66   IN       SORT_COMPARE                 CompareFunction,
  67   IN VOID                               *Buffer
  68   )
  69 {
  70   VOID        *Pivot;
  71   UINTN       LoopCount;
  72   UINTN       NextSwapLocation;
  73
  74   ASSERT(BufferToSort     != NULL);
  75   ASSERT(CompareFunction  != NULL);
  76   ASSERT(Buffer  != NULL);
  77
  78   if ( Count < 2
  79     || ElementSize  < 1
  80    ){
  81     return;
  82   }
  83
  84   NextSwapLocation = 0;
  85
  86   //
  87   // pick a pivot (we choose last element)
  88   //
  89   Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));
  90
  91   //
  92   // Now get the pivot such that all on "left" are below it
  93   // and everything "right" are above it
  94   //
  95   for ( LoopCount = 0
  96       ; LoopCount < Count -1
  97       ; LoopCount++
  98      ){
  99     //
 100     // if the element is less than the pivot
 101     //
 102     if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
 103       //
 104       // swap
 105       //
 106       CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
 107       CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
 108       CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
 109
 110       //
 111       // increment NextSwapLocation
 112       //
 113       NextSwapLocation++;
 114     }
 115   }
 116   //
 117   // swap pivot to it's final position (NextSwapLocaiton)
 118   //
 119   CopyMem (Buffer, Pivot, ElementSize);
 120   CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
 121   CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
 122
 123   //
 124   // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element
 125   // IE list is sorted left half, pivot element, sorted right half...
 126   //
 127   if (NextSwapLocation >= 2) {
 128     QuickSortWorker(
 129       BufferToSort,
 130       NextSwapLocation,
 131       ElementSize,
 132       CompareFunction,
 133       Buffer);
 134   }
 135
 136   if ((Count - NextSwapLocation - 1) >= 2) {
 137     QuickSortWorker(
 138       (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
 139       Count - NextSwapLocation - 1,
 140       ElementSize,
 141       CompareFunction,
 142       Buffer);
 143   }
 144
 145   return;
 146 }
 147 /**
 148   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 149
 150   Each element must be equal sized.
 151
 152   if BufferToSort is NULL, then ASSERT.
 153   if CompareFunction is NULL, then ASSERT.
 154
 155   if Count is < 2 then perform no action.
 156   if Size is < 1 then perform no action.
 157
 158   @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
 159                                  on return a buffer of sorted elements
 160   @param[in] Count               the number of elements in the buffer to sort
 161   @param[in] ElementSize         Size of an element in bytes
 162   @param[in] CompareFunction     The function to call to perform the comparison
 163                                  of any 2 elements
 164 **/
 165 VOID
 166 EFIAPI
 167 PerformQuickSort (
 168   IN OUT VOID                           *BufferToSort,
 169   IN CONST UINTN                        Count,
 170   IN CONST UINTN                        ElementSize,
 171   IN       SORT_COMPARE                 CompareFunction
 172   )
 173 {
 174   VOID  *Buffer;
 175
 176   ASSERT(BufferToSort     != NULL);
 177   ASSERT(CompareFunction  != NULL);
 178
 179   Buffer = AllocateZeroPool(ElementSize);
 180   ASSERT(Buffer != NULL);
 181
 182   QuickSortWorker(
 183     BufferToSort,
 184     Count,
 185     ElementSize,
 186     CompareFunction,
 187     Buffer);
 188
 189   FreePool(Buffer);
 190   return;
 191 }
 192
 193 /**
 194   Function to compare 2 device paths for use in QuickSort.
 195
 196   @param[in] Buffer1            pointer to Device Path poiner to compare
 197   @param[in] Buffer2            pointer to second DevicePath pointer to compare
 198
 199   @retval 0                     Buffer1 equal to Buffer2
 200   @retval <0                    Buffer1 is less than Buffer2
 201   @retval >0                    Buffer1 is greater than Buffer2
 202 **/
 203 INTN
 204 EFIAPI
 205 DevicePathCompare (
 206   IN  CONST VOID             *Buffer1,
 207   IN  CONST VOID             *Buffer2
 208   )
 209 {
 210   EFI_DEVICE_PATH_PROTOCOL  *DevicePath1;
 211   EFI_DEVICE_PATH_PROTOCOL  *DevicePath2;
 212   CHAR16                    *TextPath1;
 213   CHAR16                    *TextPath2;
 214   EFI_STATUS                Status;
 215   INTN                      RetVal;
 216
 217   DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;
 218   DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;
 219
 220   if (DevicePath1 == NULL) {
 221     if (DevicePath2 == NULL) {
 222       return 0;
 223     }
 224
 225     return -1;
 226   }
 227
 228   if (DevicePath2 == NULL) {
 229     return 1;
 230   }
 231
 232   if (mUnicodeCollation == NULL) {
 233     Status = gBS->LocateProtocol(
 234       &gEfiUnicodeCollation2ProtocolGuid,
 235       NULL,
 236       (VOID**)&mUnicodeCollation);
 237
 238     ASSERT_EFI_ERROR(Status);
 239   }
 240
 241   TextPath1 = ConvertDevicePathToText(
 242     DevicePath1,
 243     FALSE,
 244     FALSE);
 245
 246   TextPath2 = ConvertDevicePathToText(
 247     DevicePath2,
 248     FALSE,
 249     FALSE);
 250
 251   if (TextPath1 == NULL) {
 252     RetVal = -1;
 253   } else if (TextPath2 == NULL) {
 254     RetVal = 1;
 255   } else {
 256     RetVal = mUnicodeCollation->StriColl(
 257       mUnicodeCollation,
 258       TextPath1,
 259       TextPath2);
 260   }
 261
 262   USL_FREE_NON_NULL(TextPath1);
 263   USL_FREE_NON_NULL(TextPath2);
 264
 265   return (RetVal);
 266 }
 267
 268 /**
 269   Function to compare 2 strings without regard to case of the characters.
 270
 271   @param[in] Buffer1            Pointer to String to compare.
 272   @param[in] Buffer2            Pointer to second String to compare.
 273
 274   @retval 0                     Buffer1 equal to Buffer2.
 275   @retval <0                    Buffer1 is less than Buffer2.
 276   @retval >0                    Buffer1 is greater than Buffer2.
 277 **/
 278 INTN
 279 EFIAPI
 280 StringNoCaseCompare (
 281   IN  CONST VOID             *Buffer1,
 282   IN  CONST VOID             *Buffer2
 283   )
 284 {
 285   EFI_STATUS                Status;
 286   if (mUnicodeCollation == NULL) {
 287     Status = gBS->LocateProtocol(
 288       &gEfiUnicodeCollation2ProtocolGuid,
 289       NULL,
 290       (VOID**)&mUnicodeCollation);
 291
 292     ASSERT_EFI_ERROR(Status);
 293   }
 294
 295   return (mUnicodeCollation->StriColl(
 296     mUnicodeCollation,
 297     *(CHAR16**)Buffer1,
 298     *(CHAR16**)Buffer2));
 299 }
 300
 301
 302 /**
 303   Function to compare 2 strings.
 304
 305   @param[in] Buffer1            Pointer to String to compare (CHAR16**).
 306   @param[in] Buffer2            Pointer to second String to compare (CHAR16**).
 307
 308   @retval 0                     Buffer1 equal to Buffer2.
 309   @retval <0                    Buffer1 is less than Buffer2.
 310   @retval >0                    Buffer1 is greater than Buffer2.
 311 **/
 312 INTN
 313 EFIAPI
 314 StringCompare (
 315   IN  CONST VOID                *Buffer1,
 316   IN  CONST VOID                *Buffer2
 317   )
 318 {
 319   return (StrCmp(
 320     *(CHAR16**)Buffer1,
 321     *(CHAR16**)Buffer2));
 322 }