ShellPkg/Library/BaseSortLib/BaseSortLib.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 <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   QuickSortWorker(
 113     BufferToSort,
 114     NextSwapLocation,
 115     ElementSize,
 116     CompareFunction,
 117     Buffer);
 118
 119   QuickSortWorker(
 120     (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
 121     Count - NextSwapLocation - 1,
 122     ElementSize,
 123     CompareFunction,
 124     Buffer);
 125
 126   return;
 127 }
 128 /**
 129   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 130
 131   Each element must be equal sized.
 132
 133   if BufferToSort is NULL, then ASSERT.
 134   if CompareFunction is NULL, then ASSERT.
 135
 136   if Count is < 2 then perform no action.
 137   if Size is < 1 then perform no action.
 138
 139   @param[in,out] BufferToSort   on call a Buffer of (possibly sorted) elements
 140                                 on return a buffer of sorted elements
 141   @param[in] Count              the number of elements in the buffer to sort
 142   @param[in] ElementSize        Size of an element in bytes
 143   @param[in] CompareFunction    The function to call to perform the comparison
 144                                 of any 2 elements
 145 **/
 146 VOID
 147 EFIAPI
 148 PerformQuickSort (
 149   IN OUT VOID                           *BufferToSort,
 150   IN CONST UINTN                        Count,
 151   IN CONST UINTN                        ElementSize,
 152   IN       SORT_COMPARE                 CompareFunction
 153   )
 154 {
 155   VOID  *Buffer;
 156
 157   ASSERT(BufferToSort     != NULL);
 158   ASSERT(CompareFunction  != NULL);
 159
 160   Buffer = AllocatePool(ElementSize);
 161   ASSERT(Buffer != NULL);
 162
 163   QuickSortWorker(
 164     BufferToSort,
 165     Count,
 166     ElementSize,
 167     CompareFunction,
 168     Buffer);
 169
 170   FreePool(Buffer);
 171   return;
 172 }
 173
 174 /**
 175   Not supported in Base version.
 176
 177   ASSERT and return 0.
 178 **/
 179 INTN
 180 DevicePathCompare (
 181   IN  CONST VOID             *Buffer1,
 182   IN  CONST VOID             *Buffer2
 183   )
 184 {
 185   ASSERT(FALSE);
 186   return 0;
 187 }
 188
 189 /**
 190   Function to compare 2 strings without regard to case of the characters.
 191
 192   @param[in] Buffer1            Pointer to String to compare.
 193   @param[in] Buffer2            Pointer to second String to compare.
 194
 195   @retval 0                     Buffer1 equal to Buffer2.
 196   @return < 0                   Buffer1 is less than Buffer2.
 197   @return > 0                   Buffer1 is greater than Buffer2.
 198 **/
 199 INTN
 200 EFIAPI
 201 StringNoCaseCompare (
 202   IN  CONST VOID             *Buffer1,
 203   IN  CONST VOID             *Buffer2
 204   )
 205 {
 206   ASSERT(FALSE);
 207   return 0;
 208 }
 209
 210