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