MdeModulePkg/Library/BaseSortLib/BaseSortLib.c

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