MdeModulePkg: Replace BSD License with BSD+Patent License

[mirror_edk2.git] / MdeModulePkg / Library / BaseSortLib / BaseSortLib.c

/** @file\r
  Library used for sorting routines.\r
\r
  Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. <BR>\r
  SPDX-License-Identifier: BSD-2-Clause-Patent\r
\r
**/\r
#include <Uefi.h>\r
\r
#include <Library/BaseLib.h>\r
#include <Library/BaseMemoryLib.h>\r
#include <Library/DebugLib.h>\r
#include <Library/MemoryAllocationLib.h>\r
#include <Library/SortLib.h>\r
\r
/**\r
  Worker function for QuickSorting.  This function is identical to PerformQuickSort,\r
  except that is uses the pre-allocated buffer so the in place sorting does not need to\r
  allocate and free buffers constantly.\r
\r
  Each element must be equal sized.\r
\r
  if BufferToSort is NULL, then ASSERT.\r
  if CompareFunction is NULL, then ASSERT.\r
  if Buffer is NULL, then ASSERT.\r
\r
  if Count is < 2 then perform no action.\r
  if Size is < 1 then perform no action.\r
\r
  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements\r
                                 on return a buffer of sorted elements\r
  @param[in] Count               the number of elements in the buffer to sort\r
  @param[in] ElementSize         Size of an element in bytes\r
  @param[in] CompareFunction     The function to call to perform the comparison\r
                                 of any 2 elements\r
  @param[in] Buffer              Buffer of size ElementSize for use in swapping\r
**/\r
VOID\r
EFIAPI\r
QuickSortWorker (\r
  IN OUT VOID                           *BufferToSort,\r
  IN CONST UINTN                        Count,\r
  IN CONST UINTN                        ElementSize,\r
  IN       SORT_COMPARE                 CompareFunction,\r
  IN VOID                               *Buffer\r
  )\r
{\r
  VOID        *Pivot;\r
  UINTN       LoopCount;\r
  UINTN       NextSwapLocation;\r
\r
  ASSERT(BufferToSort     != NULL);\r
  ASSERT(CompareFunction  != NULL);\r
  ASSERT(Buffer  != NULL);\r
\r
  if ( Count < 2\r
    || ElementSize  < 1\r
   ){\r
    return;\r
  }\r
\r
  NextSwapLocation = 0;\r
\r
  //\r
  // pick a pivot (we choose last element)\r
  //\r
  Pivot = ((UINT8*)BufferToSort+((Count-1)*ElementSize));\r
\r
  //\r
  // Now get the pivot such that all on "left" are below it\r
  // and everything "right" are above it\r
  //\r
  for ( LoopCount = 0\r
      ; LoopCount < Count -1\r
      ; LoopCount++\r
     ){\r
    //\r
    // if the element is less than the pivot\r
    //\r
    if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r
      //\r
      // swap\r
      //\r
      CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
      CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize);\r
      CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, ElementSize);\r
\r
      //\r
      // increment NextSwapLocation\r
      //\r
      NextSwapLocation++;\r
    }\r
  }\r
  //\r
  // swap pivot to it's final position (NextSwapLocaiton)\r
  //\r
  CopyMem (Buffer, Pivot, ElementSize);\r
  CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), ElementSize);\r
  CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, ElementSize);\r
\r
  //\r
  // Now recurse on 2 paritial lists.  neither of these will have the 'pivot' element\r
  // IE list is sorted left half, pivot element, sorted right half...\r
  //\r
  if (NextSwapLocation >= 2) {\r
    QuickSortWorker(\r
      BufferToSort,\r
      NextSwapLocation,\r
      ElementSize,\r
      CompareFunction,\r
      Buffer);\r
  }\r
\r
  if ((Count - NextSwapLocation - 1) >= 2) {\r
    QuickSortWorker(\r
      (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize,\r
      Count - NextSwapLocation - 1,\r
      ElementSize,\r
      CompareFunction,\r
      Buffer);\r
  }\r
  return;\r
}\r
/**\r
  Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r
\r
  Each element must be equal sized.\r
\r
  if BufferToSort is NULL, then ASSERT.\r
  if CompareFunction is NULL, then ASSERT.\r
\r
  if Count is < 2 then perform no action.\r
  if Size is < 1 then perform no action.\r
\r
  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements\r
                                 on return a buffer of sorted elements\r
  @param[in] Count               the number of elements in the buffer to sort\r
  @param[in] ElementSize         Size of an element in bytes\r
  @param[in] CompareFunction     The function to call to perform the comparison\r
                                 of any 2 elements\r
**/\r
VOID\r
EFIAPI\r
PerformQuickSort (\r
  IN OUT VOID                           *BufferToSort,\r
  IN CONST UINTN                        Count,\r
  IN CONST UINTN                        ElementSize,\r
  IN       SORT_COMPARE                 CompareFunction\r
  )\r
{\r
  VOID  *Buffer;\r
\r
  ASSERT(BufferToSort     != NULL);\r
  ASSERT(CompareFunction  != NULL);\r
\r
  Buffer = AllocateZeroPool(ElementSize);\r
  ASSERT(Buffer != NULL);\r
\r
  QuickSortWorker(\r
    BufferToSort,\r
    Count,\r
    ElementSize,\r
    CompareFunction,\r
    Buffer);\r
\r
  FreePool(Buffer);\r
  return;\r
}\r
\r
/**\r
  Not supported in Base version.\r
\r
  @param[in] Buffer1  Ignored.\r
  @param[in] Buffer2  Ignored.\r
\r
  ASSERT and return 0.\r
**/\r
INTN\r
EFIAPI\r
DevicePathCompare (\r
  IN  CONST VOID             *Buffer1,\r
  IN  CONST VOID             *Buffer2\r
  )\r
{\r
  ASSERT(FALSE);\r
  return 0;\r
}\r
\r
/**\r
  Not supported in Base version.\r
\r
  @param[in] Buffer1  Ignored.\r
  @param[in] Buffer2  Ignored.\r
\r
  ASSERT and return 0.\r
**/\r
INTN\r
EFIAPI\r
StringNoCaseCompare (\r
  IN  CONST VOID             *Buffer1,\r
  IN  CONST VOID             *Buffer2\r
  )\r
{\r
  ASSERT(FALSE);\r
  return 0;\r
}\r
\r
\r
/**\r
  Not supported in Base version.\r
\r
  @param[in] Buffer1  Ignored.\r
  @param[in] Buffer2  Ignored.\r
\r
  ASSERT and return 0.\r
**/\r
INTN\r
EFIAPI\r
StringCompare (\r
  IN  CONST VOID                *Buffer1,\r
  IN  CONST VOID                *Buffer2\r
  )\r
{\r
  ASSERT(FALSE);\r
  return 0;\r
}\r
\r
\r