MdePkg/Library/BaseLib/QuickSort.c

   1 /** @file
   2   Math worker functions.
   3
   4   Copyright (c) 2021, Intel Corporation. All rights reserved.<BR>
   5   SPDX-License-Identifier: BSD-2-Clause-Patent
   6
   7 **/
   8
   9 #include "BaseLibInternals.h"
  10
  11 /**
  12   This function is identical to perform QuickSort,
  13   except that is uses the pre-allocated buffer so the in place sorting does not need to
  14   allocate and free buffers constantly.
  15
  16   Each element must be equal sized.
  17
  18   if BufferToSort is NULL, then ASSERT.
  19   if CompareFunction is NULL, then ASSERT.
  20   if BufferOneElement is NULL, then ASSERT.
  21   if ElementSize is < 1, then ASSERT.
  22
  23   if Count is < 2 then perform no action.
  24
  25   @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
  26                                  on return a buffer of sorted elements
  27   @param[in] Count               the number of elements in the buffer to sort
  28   @param[in] ElementSize         Size of an element in bytes
  29   @param[in] CompareFunction     The function to call to perform the comparison
  30                                  of any 2 elements
  31   @param[out] BufferOneElement   Caller provided buffer whose size equals to ElementSize.
  32                                  It's used by QuickSort() for swapping in sorting.
  33 **/
  34 VOID
  35 EFIAPI
  36 QuickSort (
  37   IN OUT VOID                 *BufferToSort,
  38   IN CONST UINTN              Count,
  39   IN CONST UINTN              ElementSize,
  40   IN       BASE_SORT_COMPARE  CompareFunction,
  41   OUT VOID                    *BufferOneElement
  42   )
  43 {
  44   VOID   *Pivot;
  45   UINTN  LoopCount;
  46   UINTN  NextSwapLocation;
  47
  48   ASSERT (BufferToSort     != NULL);
  49   ASSERT (CompareFunction  != NULL);
  50   ASSERT (BufferOneElement != NULL);
  51   ASSERT (ElementSize      >= 1);
  52
  53   if (Count < 2) {
  54     return;
  55   }
  56
  57   NextSwapLocation = 0;
  58
  59   //
  60   // pick a pivot (we choose last element)
  61   //
  62   Pivot = ((UINT8 *)BufferToSort + ((Count - 1) * ElementSize));
  63
  64   //
  65   // Now get the pivot such that all on "left" are below it
  66   // and everything "right" are above it
  67   //
  68   for (LoopCount = 0; LoopCount < Count -1; LoopCount++) {
  69     //
  70     // if the element is less than or equal to the pivot
  71     //
  72     if (CompareFunction ((VOID *)((UINT8 *)BufferToSort + ((LoopCount) * ElementSize)), Pivot) <= 0) {
  73       //
  74       // swap
  75       //
  76       CopyMem (BufferOneElement, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
  77       CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), (UINT8 *)BufferToSort + ((LoopCount) * ElementSize), ElementSize);
  78       CopyMem ((UINT8 *)BufferToSort + ((LoopCount)*ElementSize), BufferOneElement, ElementSize);
  79
  80       //
  81       // increment NextSwapLocation
  82       //
  83       NextSwapLocation++;
  84     }
  85   }
  86
  87   //
  88   // swap pivot to it's final position (NextSwapLocation)
  89   //
  90   CopyMem (BufferOneElement, Pivot, ElementSize);
  91   CopyMem (Pivot, (UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), ElementSize);
  92   CopyMem ((UINT8 *)BufferToSort + (NextSwapLocation * ElementSize), BufferOneElement, ElementSize);
  93
  94   //
  95   // Now recurse on 2 partial lists.  neither of these will have the 'pivot' element
  96   // IE list is sorted left half, pivot element, sorted right half...
  97   //
  98   if (NextSwapLocation >= 2) {
  99     QuickSort (
 100       BufferToSort,
 101       NextSwapLocation,
 102       ElementSize,
 103       CompareFunction,
 104       BufferOneElement
 105       );
 106   }
 107
 108   if ((Count - NextSwapLocation - 1) >= 2) {
 109     QuickSort (
 110       (UINT8 *)BufferToSort + (NextSwapLocation + 1) * ElementSize,
 111       Count - NextSwapLocation - 1,
 112       ElementSize,
 113       CompareFunction,
 114       BufferOneElement
 115       );
 116   }
 117 }