ShellPkg/Library/UefiSortLib/UefiSortLib.c

   1 /** @file
   2   Library used for sorting routines.
   3
   4 Copyright (c) 2009, Intel Corporation
   5 All rights reserved. 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 /**
  29   Worker function for QuickSorting.  This function is identical to PerformQuickSort,
  30   except that is uses the pre-allocated buffer so the in place sorting does not need to
  31   allocate and free buffers constantly.
  32
  33   Each element must be equal sized.
  34
  35   if BufferToSort is NULL, then ASSERT.
  36   if CompareFunction is NULL, then ASSERT.
  37   if Buffer is NULL, then ASSERT.
  38
  39   if Count is < 2 then perform no action.
  40   if Size is < 1 then perform no action.
  41
  42   @param[in,out] BufferToSort   on call a Buffer of (possibly sorted) elements
  43                                 on return a buffer of sorted elements
  44   @param[in] Count              the number of elements in the buffer to sort
  45   @param[in] ElementSize        Size of an element in bytes
  46   @param[in] CompareFunction    The function to call to perform the comparison
  47                                 of any 2 elements
  48   @param[in] Buffer             Buffer of size ElementSize for use in swapping
  49 **/
  50 VOID
  51 EFIAPI
  52 QuickSortWorker (
  53   IN OUT VOID                           *BufferToSort,
  54   IN CONST UINTN                        Count,
  55   IN CONST UINTN                        ElementSize,
  56   IN       SORT_COMPARE                 CompareFunction,
  57   IN VOID                               *Buffer
  58   ){
  59   VOID        *Pivot;
  60   UINTN       LoopCount;
  61   UINTN       NextSwapLocation;
  62
  63   ASSERT(BufferToSort     != NULL);
  64   ASSERT(CompareFunction  != NULL);
  65   ASSERT(Buffer  != NULL);
  66
  67   if ( Count < 2
  68     || ElementSize  < 1
  69     ){
  70     return;
  71   }
  72
  73   NextSwapLocation = 0;
  74
  75   //
  76   // pick a pivot (we choose last element)
  77   //
  78   Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));
  79
  80   //
  81   // Now get the pivot such that all on "left" are below it
  82   // and everything "right" are above it
  83   //
  84   for ( LoopCount = 0
  85       ; LoopCount < Count -1
  86       ; LoopCount++
  87       ){
  88     //
  89     // if the element is less than the pivot
  90     //
  91     if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
  92       //
  93       // swap
  94       //
  95       CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
  96       CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
  97       CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
  98
  99       //
 100       // increment NextSwapLocation
 101       //
 102       NextSwapLocation++;
 103     }
 104   }
 105   //
 106   // swap pivot to it's final position (NextSwapLocaiton)
 107   //
 108   CopyMem (Buffer, Pivot, ElementSize);
 109   CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
 110   CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
 111
 112   //
 113   // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element
 114   // IE list is sorted left half, pivot element, sorted right half...
 115   //
 116   QuickSortWorker(
 117     BufferToSort,
 118     NextSwapLocation,
 119     ElementSize,
 120     CompareFunction,
 121     Buffer);
 122
 123   QuickSortWorker(
 124     (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
 125     Count - NextSwapLocation - 1,
 126     ElementSize,
 127     CompareFunction,
 128     Buffer);
 129
 130   return;
 131 }
 132 /**
 133   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 134
 135   Each element must be equal sized.
 136
 137   if BufferToSort is NULL, then ASSERT.
 138   if CompareFunction is NULL, then ASSERT.
 139
 140   if Count is < 2 then perform no action.
 141   if Size is < 1 then perform no action.
 142
 143   @param[in,out] BufferToSort   on call a Buffer of (possibly sorted) elements
 144                                 on return a buffer of sorted elements
 145   @param[in] Count              the number of elements in the buffer to sort
 146   @param[in] ElementSize        Size of an element in bytes
 147   @param[in] CompareFunction    The function to call to perform the comparison
 148                                 of any 2 elements
 149 **/
 150 VOID
 151 EFIAPI
 152 PerformQuickSort (
 153   IN OUT VOID                           *BufferToSort,
 154   IN CONST UINTN                        Count,
 155   IN CONST UINTN                        ElementSize,
 156   IN       SORT_COMPARE                 CompareFunction
 157   ){
 158   VOID  *Buffer;
 159
 160   ASSERT(BufferToSort     != NULL);
 161   ASSERT(CompareFunction  != NULL);
 162
 163   Buffer = AllocatePool(ElementSize);
 164   ASSERT(Buffer != NULL);
 165
 166   QuickSortWorker(
 167     BufferToSort,
 168     Count,
 169     ElementSize,
 170     CompareFunction,
 171     Buffer);
 172
 173   FreePool(Buffer);
 174   return;
 175 }
 176
 177 /**
 178   function to compare 2 device paths for use in QuickSort
 179
 180   @param[in] Buffer1            pointer to Device Path poiner to compare
 181   @param[in] Buffer2            pointer to second DevicePath pointer to compare
 182
 183   @retval 0                     Buffer1 equal to Buffer2
 184   @return < 0                   Buffer1 is less than Buffer2
 185   @return > 0                   Buffer1 is greater than Buffer2
 186 **/
 187 INTN
 188 DevicePathCompare (
 189   IN  VOID             *Buffer1,
 190   IN  VOID             *Buffer2
 191   ){
 192   EFI_DEVICE_PATH_PROTOCOL  *DevicePath1;
 193   EFI_DEVICE_PATH_PROTOCOL  *DevicePath2;
 194   CHAR16                    *TextPath1;
 195   CHAR16                    *TextPath2;
 196   EFI_STATUS                Status;
 197   INTN                      RetVal;
 198
 199   STATIC EFI_DEVICE_PATH_TO_TEXT_PROTOCOL *DevicePathToText = NULL;
 200   STATIC EFI_UNICODE_COLLATION_PROTOCOL   *UnicodeCollation = NULL;
 201
 202   DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;
 203   DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;
 204
 205   if (DevicePath1 == NULL) {
 206     if (DevicePath2 == NULL) {
 207       return 0;
 208     }
 209
 210     return -1;
 211   }
 212
 213   if (DevicePath2 == NULL) {
 214     return 1;
 215   }
 216
 217   if (DevicePathToText == NULL) {
 218     Status = gBS->LocateProtocol(
 219       &gEfiDevicePathToTextProtocolGuid,
 220       NULL,
 221       (VOID**)&DevicePathToText);
 222
 223     ASSERT_EFI_ERROR(Status);
 224   }
 225
 226   if (UnicodeCollation == NULL) {
 227     Status = gBS->LocateProtocol(
 228       &gEfiUnicodeCollation2ProtocolGuid,
 229       NULL,
 230       (VOID**)&UnicodeCollation);
 231
 232     ASSERT_EFI_ERROR(Status);
 233   }
 234
 235   TextPath1 = DevicePathToText->ConvertDevicePathToText(
 236     DevicePath1,
 237     FALSE,
 238     FALSE);
 239
 240   TextPath2 = DevicePathToText->ConvertDevicePathToText(
 241     DevicePath2,
 242     FALSE,
 243     FALSE);
 244
 245   RetVal = UnicodeCollation->StriColl(
 246     UnicodeCollation,
 247     TextPath1,
 248     TextPath2);
 249
 250   FreePool(TextPath1);
 251   FreePool(TextPath2);
 252
 253   return (RetVal);
 254 }