ShellPkg/Library/BaseSortLib/BaseSortLib.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
  17 #include <Library/BaseLib.h>
  18 #include <Library/BaseMemoryLib.h>
  19 #include <Library/DebugLib.h>
  20 #include <Library/MemoryAllocationLib.h>
  21 #include <Library/SortLib.h>
  22
  23 /**
  24   Worker function for QuickSorting.  This function is identical to PerformQuickSort,
  25   except that is uses the pre-allocated buffer so the in place sorting does not need to
  26   allocate and free buffers constantly.
  27
  28   Each element must be equal sized.
  29
  30   if BufferToSort is NULL, then ASSERT.
  31   if CompareFunction is NULL, then ASSERT.
  32   if Buffer is NULL, then ASSERT.
  33
  34   if Count is < 2 then perform no action.
  35   if Size is < 1 then perform no action.
  36
  37   @param[in,out] BufferToSort   on call a Buffer of (possibly sorted) elements
  38                                 on return a buffer of sorted elements
  39   @param[in] Count              the number of elements in the buffer to sort
  40   @param[in] ElementSize        Size of an element in bytes
  41   @param[in] CompareFunction    The function to call to perform the comparison
  42                                 of any 2 elements
  43   @param[in] Buffer             Buffer of size ElementSize for use in swapping
  44 **/
  45 VOID
  46 EFIAPI
  47 QuickSortWorker (
  48   IN OUT VOID                           *BufferToSort,
  49   IN CONST UINTN                        Count,
  50   IN CONST UINTN                        ElementSize,
  51   IN       SORT_COMPARE                 CompareFunction,
  52   IN VOID                               *Buffer
  53   )
  54 {
  55   VOID        *Pivot;
  56   UINTN       LoopCount;
  57   UINTN       NextSwapLocation;
  58
  59   ASSERT(BufferToSort     != NULL);
  60   ASSERT(CompareFunction  != NULL);
  61   ASSERT(Buffer  != NULL);
  62
  63   if ( Count < 2
  64     || ElementSize  < 1
  65    ){
  66     return;
  67   }
  68
  69   NextSwapLocation = 0;
  70
  71   //
  72   // pick a pivot (we choose last element)
  73   //
  74   Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));
  75
  76   //
  77   // Now get the pivot such that all on "left" are below it
  78   // and everything "right" are above it
  79   //
  80   for ( LoopCount = 0
  81       ; LoopCount < Count -1
  82       ; LoopCount++
  83      ){
  84     //
  85     // if the element is less than the pivot
  86     //
  87     if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){
  88       //
  89       // swap
  90       //
  91       CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
  92       CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);
  93       CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);
  94
  95       //
  96       // increment NextSwapLocation
  97       //
  98       NextSwapLocation++;
  99     }
 100   }
 101   //
 102   // swap pivot to it's final position (NextSwapLocaiton)
 103   //
 104   CopyMem (Buffer, Pivot, ElementSize);
 105   CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);
 106   CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);
 107
 108   //
 109   // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element
 110   // IE list is sorted left half, pivot element, sorted right half...
 111   //
 112   if (NextSwapLocation >= 2) {
 113     QuickSortWorker(
 114       BufferToSort,
 115       NextSwapLocation,
 116       ElementSize,
 117       CompareFunction,
 118       Buffer);
 119   }
 120
 121   if ((Count - NextSwapLocation - 1) >= 2) {
 122     QuickSortWorker(
 123       (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
 124       Count - NextSwapLocation - 1,
 125       ElementSize,
 126       CompareFunction,
 127       Buffer);
 128   }
 129   return;
 130 }
 131 /**
 132   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 133
 134   Each element must be equal sized.
 135
 136   if BufferToSort is NULL, then ASSERT.
 137   if CompareFunction is NULL, then ASSERT.
 138
 139   if Count is < 2 then perform no action.
 140   if Size is < 1 then perform no action.
 141
 142   @param[in,out] BufferToSort   on call a Buffer of (possibly sorted) elements
 143                                 on return a buffer of sorted elements
 144   @param[in] Count              the number of elements in the buffer to sort
 145   @param[in] ElementSize        Size of an element in bytes
 146   @param[in] CompareFunction    The function to call to perform the comparison
 147                                 of any 2 elements
 148 **/
 149 VOID
 150 EFIAPI
 151 PerformQuickSort (
 152   IN OUT VOID                           *BufferToSort,
 153   IN CONST UINTN                        Count,
 154   IN CONST UINTN                        ElementSize,
 155   IN       SORT_COMPARE                 CompareFunction
 156   )
 157 {
 158   VOID  *Buffer;
 159
 160   ASSERT(BufferToSort     != NULL);
 161   ASSERT(CompareFunction  != NULL);
 162
 163   Buffer = AllocateZeroPool(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   Not supported in Base version.
 179
 180   @param[in] Buffer1  Ignored.
 181   @param[in] Buffer2  Ignored.
 182
 183   ASSERT and return 0.
 184 **/
 185 INTN
 186 EFIAPI
 187 DevicePathCompare (
 188   IN  CONST VOID             *Buffer1,
 189   IN  CONST VOID             *Buffer2
 190   )
 191 {
 192   ASSERT(FALSE);
 193   return 0;
 194 }
 195
 196 /**
 197   Function to compare 2 strings without regard to case of the characters.
 198
 199   @param[in] Buffer1            Pointer to String to compare.
 200   @param[in] Buffer2            Pointer to second String to compare.
 201
 202   @retval 0                     Buffer1 equal to Buffer2.
 203   @return < 0                   Buffer1 is less than Buffer2.
 204   @return > 0                   Buffer1 is greater than Buffer2.
 205 **/
 206 INTN
 207 EFIAPI
 208 StringNoCaseCompare (
 209   IN  CONST VOID             *Buffer1,
 210   IN  CONST VOID             *Buffer2
 211   )
 212 {
 213   ASSERT(FALSE);
 214   return 0;
 215 }
 216
 217
 218 /**
 219   Function to compare 2 strings.
 220
 221   @param[in] Buffer1            Pointer to String to compare (CHAR16**).
 222   @param[in] Buffer2            Pointer to second String to compare (CHAR16**).
 223
 224   @retval 0                     Buffer1 equal to Buffer2.
 225   @return < 0                   Buffer1 is less than Buffer2.
 226   @return > 0                   Buffer1 is greater than Buffer2.
 227 **/
 228 INTN
 229 EFIAPI
 230 StringCompare (
 231   IN  CONST VOID                *Buffer1,
 232   IN  CONST VOID                *Buffer2
 233   )
 234 {
 235   ASSERT(FALSE);
 236   return 0;
 237 }
 238
 239