ShellPkg/Library/UefiSortLib/UefiSortLib.c

   1 /** @file
   2   Library used for sorting routines.
   3
   4   Copyright (c) 2009 - 2010, 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   QuickSortWorker(
 122     BufferToSort,
 123     NextSwapLocation,
 124     ElementSize,
 125     CompareFunction,
 126     Buffer);
 127
 128   QuickSortWorker(
 129     (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
 130     Count - NextSwapLocation - 1,
 131     ElementSize,
 132     CompareFunction,
 133     Buffer);
 134
 135   return;
 136 }
 137 /**
 138   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 139
 140   Each element must be equal sized.
 141
 142   if BufferToSort is NULL, then ASSERT.
 143   if CompareFunction is NULL, then ASSERT.
 144
 145   if Count is < 2 then perform no action.
 146   if Size is < 1 then perform no action.
 147
 148   @param[in,out] BufferToSort   on call a Buffer of (possibly sorted) elements
 149                                 on return a buffer of sorted elements
 150   @param[in] Count              the number of elements in the buffer to sort
 151   @param[in] ElementSize        Size of an element in bytes
 152   @param[in] CompareFunction    The function to call to perform the comparison
 153                                 of any 2 elements
 154 **/
 155 VOID
 156 EFIAPI
 157 PerformQuickSort (
 158   IN OUT VOID                           *BufferToSort,
 159   IN CONST UINTN                        Count,
 160   IN CONST UINTN                        ElementSize,
 161   IN       SORT_COMPARE                 CompareFunction
 162   )
 163 {
 164   VOID  *Buffer;
 165
 166   ASSERT(BufferToSort     != NULL);
 167   ASSERT(CompareFunction  != NULL);
 168
 169   Buffer = AllocatePool(ElementSize);
 170   ASSERT(Buffer != NULL);
 171
 172   QuickSortWorker(
 173     BufferToSort,
 174     Count,
 175     ElementSize,
 176     CompareFunction,
 177     Buffer);
 178
 179   FreePool(Buffer);
 180   return;
 181 }
 182
 183 /**
 184   function to compare 2 device paths for use in QuickSort
 185
 186   @param[in] Buffer1            pointer to Device Path poiner to compare
 187   @param[in] Buffer2            pointer to second DevicePath pointer to compare
 188
 189   @retval 0                     Buffer1 equal to Buffer2
 190   @return < 0                   Buffer1 is less than Buffer2
 191   @return > 0                   Buffer1 is greater than Buffer2
 192 **/
 193 INTN
 194 EFIAPI
 195 DevicePathCompare (
 196   IN  CONST VOID             *Buffer1,
 197   IN  CONST VOID             *Buffer2
 198   )
 199 {
 200   EFI_DEVICE_PATH_PROTOCOL  *DevicePath1;
 201   EFI_DEVICE_PATH_PROTOCOL  *DevicePath2;
 202   CHAR16                    *TextPath1;
 203   CHAR16                    *TextPath2;
 204   EFI_STATUS                Status;
 205   INTN                      RetVal;
 206
 207   DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;
 208   DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;
 209
 210   if (DevicePath1 == NULL) {
 211     if (DevicePath2 == NULL) {
 212       return 0;
 213     }
 214
 215     return -1;
 216   }
 217
 218   if (DevicePath2 == NULL) {
 219     return 1;
 220   }
 221
 222   if (mDevicePathToText == NULL) {
 223     Status = gBS->LocateProtocol(
 224       &gEfiDevicePathToTextProtocolGuid,
 225       NULL,
 226       (VOID**)&mDevicePathToText);
 227
 228     ASSERT_EFI_ERROR(Status);
 229   }
 230
 231   if (mUnicodeCollation == NULL) {
 232     Status = gBS->LocateProtocol(
 233       &gEfiUnicodeCollation2ProtocolGuid,
 234       NULL,
 235       (VOID**)&mUnicodeCollation);
 236
 237     ASSERT_EFI_ERROR(Status);
 238   }
 239
 240   TextPath1 = mDevicePathToText->ConvertDevicePathToText(
 241     DevicePath1,
 242     FALSE,
 243     FALSE);
 244
 245   TextPath2 = mDevicePathToText->ConvertDevicePathToText(
 246     DevicePath2,
 247     FALSE,
 248     FALSE);
 249
 250   RetVal = mUnicodeCollation->StriColl(
 251     mUnicodeCollation,
 252     TextPath1,
 253     TextPath2);
 254
 255   FreePool(TextPath1);
 256   FreePool(TextPath2);
 257
 258   return (RetVal);
 259 }
 260
 261 /**
 262   Function to compare 2 strings without regard to case of the characters.
 263
 264   @param[in] Buffer1            Pointer to String to compare.
 265   @param[in] Buffer2            Pointer to second String to compare.
 266
 267   @retval 0                     Buffer1 equal to Buffer2.
 268   @return < 0                   Buffer1 is less than Buffer2.
 269   @return > 0                   Buffer1 is greater than Buffer2.
 270 **/
 271 INTN
 272 EFIAPI
 273 StringNoCaseCompare (
 274   IN  CONST VOID             *Buffer1,
 275   IN  CONST VOID             *Buffer2
 276   )
 277 {
 278   EFI_STATUS                Status;
 279   if (mUnicodeCollation == NULL) {
 280     Status = gBS->LocateProtocol(
 281       &gEfiUnicodeCollation2ProtocolGuid,
 282       NULL,
 283       (VOID**)&mUnicodeCollation);
 284
 285     ASSERT_EFI_ERROR(Status);
 286   }
 287
 288   return (mUnicodeCollation->StriColl(
 289     mUnicodeCollation,
 290     *(CHAR16**)Buffer1,
 291     *(CHAR16**)Buffer2));
 292 }
 293
 294
 295 /**
 296   Function to compare 2 strings.
 297
 298   @param[in] Buffer1            Pointer to String to compare (CHAR16**).
 299   @param[in] Buffer2            Pointer to second String to compare (CHAR16**).
 300
 301   @retval 0                     Buffer1 equal to Buffer2.
 302   @return < 0                   Buffer1 is less than Buffer2.
 303   @return > 0                   Buffer1 is greater than Buffer2.
 304 **/
 305 INTN
 306 EFIAPI
 307 StringCompare (
 308   IN  CONST VOID                *Buffer1,
 309   IN  CONST VOID                *Buffer2
 310   )
 311 {
 312   return (StrCmp(
 313     *(CHAR16**)Buffer1,
 314     *(CHAR16**)Buffer2));
 315 }