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
  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 #include <Library/DevicePathLib.h>
  28
  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 (mUnicodeCollation == NULL) {
 227     Status = gBS->LocateProtocol(
 228       &gEfiUnicodeCollation2ProtocolGuid,
 229       NULL,
 230       (VOID**)&mUnicodeCollation);
 231
 232     ASSERT_EFI_ERROR(Status);
 233   }
 234
 235   TextPath1 = ConvertDevicePathToText(
 236     DevicePath1,
 237     FALSE,
 238     FALSE);
 239
 240   TextPath2 = ConvertDevicePathToText(
 241     DevicePath2,
 242     FALSE,
 243     FALSE);
 244
 245   if (TextPath1 == NULL) {
 246     RetVal = -1;
 247   } else if (TextPath2 == NULL) {
 248     RetVal = 1;
 249   } else {
 250     RetVal = mUnicodeCollation->StriColl(
 251       mUnicodeCollation,
 252       TextPath1,
 253       TextPath2);
 254   }
 255
 256   SHELL_FREE_NON_NULL(TextPath1);
 257   SHELL_FREE_NON_NULL(TextPath2);
 258
 259   return (RetVal);
 260 }
 261
 262 /**
 263   Function to compare 2 strings without regard to case of the characters.
 264
 265   @param[in] Buffer1            Pointer to String to compare.
 266   @param[in] Buffer2            Pointer to second String to compare.
 267
 268   @retval 0                     Buffer1 equal to Buffer2.
 269   @return < 0                   Buffer1 is less than Buffer2.
 270   @return > 0                   Buffer1 is greater than Buffer2.
 271 **/
 272 INTN
 273 EFIAPI
 274 StringNoCaseCompare (
 275   IN  CONST VOID             *Buffer1,
 276   IN  CONST VOID             *Buffer2
 277   )
 278 {
 279   EFI_STATUS                Status;
 280   if (mUnicodeCollation == NULL) {
 281     Status = gBS->LocateProtocol(
 282       &gEfiUnicodeCollation2ProtocolGuid,
 283       NULL,
 284       (VOID**)&mUnicodeCollation);
 285
 286     ASSERT_EFI_ERROR(Status);
 287   }
 288
 289   return (mUnicodeCollation->StriColl(
 290     mUnicodeCollation,
 291     *(CHAR16**)Buffer1,
 292     *(CHAR16**)Buffer2));
 293 }
 294
 295
 296 /**
 297   Function to compare 2 strings.
 298
 299   @param[in] Buffer1            Pointer to String to compare (CHAR16**).
 300   @param[in] Buffer2            Pointer to second String to compare (CHAR16**).
 301
 302   @retval 0                     Buffer1 equal to Buffer2.
 303   @return < 0                   Buffer1 is less than Buffer2.
 304   @return > 0                   Buffer1 is greater than Buffer2.
 305 **/
 306 INTN
 307 EFIAPI
 308 StringCompare (
 309   IN  CONST VOID                *Buffer1,
 310   IN  CONST VOID                *Buffer2
 311   )
 312 {
 313   return (StrCmp(
 314     *(CHAR16**)Buffer1,
 315     *(CHAR16**)Buffer2));
 316 }