ShellPkg/Library/BaseSortLib/BaseSortLib.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 <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   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   QuickSortWorker(
 112     BufferToSort,
 113     NextSwapLocation,
 114     ElementSize,
 115     CompareFunction,
 116     Buffer);
 117
 118   QuickSortWorker(
 119     (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,
 120     Count - NextSwapLocation - 1,
 121     ElementSize,
 122     CompareFunction,
 123     Buffer);
 124
 125   return;
 126 }
 127 /**
 128   Function to perform a Quick Sort alogrithm on a buffer of comparable elements.
 129
 130   Each element must be equal sized.
 131
 132   if BufferToSort is NULL, then ASSERT.
 133   if CompareFunction is NULL, then ASSERT.
 134
 135   if Count is < 2 then perform no action.
 136   if Size is < 1 then perform no action.
 137
 138   @param[in,out] BufferToSort   on call a Buffer of (possibly sorted) elements
 139                                 on return a buffer of sorted elements
 140   @param[in] Count              the number of elements in the buffer to sort
 141   @param[in] ElementSize        Size of an element in bytes
 142   @param[in] CompareFunction    The function to call to perform the comparison
 143                                 of any 2 elements
 144 **/
 145 VOID
 146 EFIAPI
 147 PerformQuickSort (
 148   IN OUT VOID                           *BufferToSort,
 149   IN CONST UINTN                        Count,
 150   IN CONST UINTN                        ElementSize,
 151   IN       SORT_COMPARE                 CompareFunction
 152   ){
 153   VOID  *Buffer;
 154
 155   ASSERT(BufferToSort     != NULL);
 156   ASSERT(CompareFunction  != NULL);
 157
 158   Buffer = AllocatePool(ElementSize);
 159   ASSERT(Buffer != NULL);
 160
 161   QuickSortWorker(
 162     BufferToSort,
 163     Count,
 164     ElementSize,
 165     CompareFunction,
 166     Buffer);
 167
 168   FreePool(Buffer);
 169   return;
 170 }