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 DevicePathCompare (
 195   IN  CONST VOID             *Buffer1,
 196   IN  CONST VOID             *Buffer2
 197   )
 198 {
 199   EFI_DEVICE_PATH_PROTOCOL  *DevicePath1;
 200   EFI_DEVICE_PATH_PROTOCOL  *DevicePath2;
 201   CHAR16                    *TextPath1;
 202   CHAR16                    *TextPath2;
 203   EFI_STATUS                Status;
 204   INTN                      RetVal;
 205
 206   DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;
 207   DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;
 208
 209   if (DevicePath1 == NULL) {
 210     if (DevicePath2 == NULL) {
 211       return 0;
 212     }
 213
 214     return -1;
 215   }
 216
 217   if (DevicePath2 == NULL) {
 218     return 1;
 219   }
 220
 221   if (mDevicePathToText == NULL) {
 222     Status = gBS->LocateProtocol(
 223       &gEfiDevicePathToTextProtocolGuid,
 224       NULL,
 225       (VOID**)&mDevicePathToText);
 226
 227     ASSERT_EFI_ERROR(Status);
 228   }
 229
 230   if (mUnicodeCollation == NULL) {
 231     Status = gBS->LocateProtocol(
 232       &gEfiUnicodeCollation2ProtocolGuid,
 233       NULL,
 234       (VOID**)&mUnicodeCollation);
 235
 236     ASSERT_EFI_ERROR(Status);
 237   }
 238
 239   TextPath1 = mDevicePathToText->ConvertDevicePathToText(
 240     DevicePath1,
 241     FALSE,
 242     FALSE);
 243
 244   TextPath2 = mDevicePathToText->ConvertDevicePathToText(
 245     DevicePath2,
 246     FALSE,
 247     FALSE);
 248
 249   RetVal = mUnicodeCollation->StriColl(
 250     mUnicodeCollation,
 251     TextPath1,
 252     TextPath2);
 253
 254   FreePool(TextPath1);
 255   FreePool(TextPath2);
 256
 257   return (RetVal);
 258 }
 259
 260 /**
 261   Function to compare 2 strings without regard to case of the characters.
 262
 263   @param[in] Buffer1            Pointer to String to compare.
 264   @param[in] Buffer2            Pointer to second String to compare.
 265
 266   @retval 0                     Buffer1 equal to Buffer2.
 267   @return < 0                   Buffer1 is less than Buffer2.
 268   @return > 0                   Buffer1 is greater than Buffer2.
 269 **/
 270 INTN
 271 EFIAPI
 272 StringNoCaseCompare (
 273   IN  CONST VOID             *Buffer1,
 274   IN  CONST VOID             *Buffer2
 275   )
 276 {
 277   EFI_STATUS                Status;
 278   if (mUnicodeCollation == NULL) {
 279     Status = gBS->LocateProtocol(
 280       &gEfiUnicodeCollation2ProtocolGuid,
 281       NULL,
 282       (VOID**)&mUnicodeCollation);
 283
 284     ASSERT_EFI_ERROR(Status);
 285   }
 286
 287   return (mUnicodeCollation->StriColl(
 288     mUnicodeCollation,
 289     *(CHAR16**)Buffer1,
 290     *(CHAR16**)Buffer2));
 291 }
 292
 293