ShellPkg/Library/UefiSortLib/UefiSortLib.c

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