MdeModulePkg/Library/BaseSortLib/BaseSortLib.c

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