/** @file
  Library used for sorting routines.

  Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. <BR>
  SPDX-License-Identifier: BSD-2-Clause-Patent

**/

#include <Uefi.h>

#include <Protocol/UnicodeCollation.h>
#include <Protocol/DevicePath.h>

#include <Library/UefiBootServicesTableLib.h>
#include <Library/BaseLib.h>
#include <Library/BaseMemoryLib.h>
#include <Library/DebugLib.h>
#include <Library/MemoryAllocationLib.h>
#include <Library/SortLib.h>
#include <Library/DevicePathLib.h>

STATIC EFI_UNICODE_COLLATION_PROTOCOL  *mUnicodeCollation = NULL;

#define USL_FREE_NON_NULL(Pointer)  \
{                                     \
  if ((Pointer) != NULL) {            \
  FreePool((Pointer));                \
  (Pointer) = NULL;                   \
  }                                   \
}

/**
  Function to perform a Quick Sort alogrithm on a buffer of comparable elements.

  Each element must be equal sized.

  if BufferToSort is NULL, then ASSERT.
  if CompareFunction is NULL, then ASSERT.

  if Count is < 2 then perform no action.
  if Size is < 1 then perform no action.

  @param[in, out] BufferToSort   on call a Buffer of (possibly sorted) elements
                                 on return a buffer of sorted elements
  @param[in] Count               the number of elements in the buffer to sort
  @param[in] ElementSize         Size of an element in bytes
  @param[in] CompareFunction     The function to call to perform the comparison
                                 of any 2 elements
**/
VOID
EFIAPI
PerformQuickSort (
  IN OUT VOID            *BufferToSort,
  IN CONST UINTN         Count,
  IN CONST UINTN         ElementSize,
  IN       SORT_COMPARE  CompareFunction
  )
{
  VOID  *Buffer;

  ASSERT (BufferToSort     != NULL);
  ASSERT (CompareFunction  != NULL);

  Buffer = AllocateZeroPool (ElementSize);
  ASSERT (Buffer != NULL);

  QuickSort (
    BufferToSort,
    Count,
    ElementSize,
    CompareFunction,
    Buffer
    );

  FreePool (Buffer);
  return;
}

/**
  Function to compare 2 device paths for use in QuickSort.

  @param[in] Buffer1            pointer to Device Path poiner to compare
  @param[in] Buffer2            pointer to second DevicePath pointer to compare

  @retval 0                     Buffer1 equal to Buffer2
  @retval <0                    Buffer1 is less than Buffer2
  @retval >0                    Buffer1 is greater than Buffer2
**/
INTN
EFIAPI
DevicePathCompare (
  IN  CONST VOID  *Buffer1,
  IN  CONST VOID  *Buffer2
  )
{
  EFI_DEVICE_PATH_PROTOCOL  *DevicePath1;
  EFI_DEVICE_PATH_PROTOCOL  *DevicePath2;
  CHAR16                    *TextPath1;
  CHAR16                    *TextPath2;
  EFI_STATUS                Status;
  INTN                      RetVal;

  DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL **)Buffer1;
  DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL **)Buffer2;

  if (DevicePath1 == NULL) {
    if (DevicePath2 == NULL) {
      return 0;
    }

    return -1;
  }

  if (DevicePath2 == NULL) {
    return 1;
  }

  if (mUnicodeCollation == NULL) {
    Status = gBS->LocateProtocol (
                    &gEfiUnicodeCollation2ProtocolGuid,
                    NULL,
                    (VOID **)&mUnicodeCollation
                    );

    ASSERT_EFI_ERROR (Status);
  }

  TextPath1 = ConvertDevicePathToText (
                DevicePath1,
                FALSE,
                FALSE
                );

  TextPath2 = ConvertDevicePathToText (
                DevicePath2,
                FALSE,
                FALSE
                );

  if (TextPath1 == NULL) {
    RetVal = -1;
  } else if (TextPath2 == NULL) {
    RetVal = 1;
  } else {
    RetVal = mUnicodeCollation->StriColl (
                                  mUnicodeCollation,
                                  TextPath1,
                                  TextPath2
                                  );
  }

  USL_FREE_NON_NULL (TextPath1);
  USL_FREE_NON_NULL (TextPath2);

  return (RetVal);
}

/**
  Function to compare 2 strings without regard to case of the characters.

  @param[in] Buffer1            Pointer to String to compare.
  @param[in] Buffer2            Pointer to second String to compare.

  @retval 0                     Buffer1 equal to Buffer2.
  @retval <0                    Buffer1 is less than Buffer2.
  @retval >0                    Buffer1 is greater than Buffer2.
**/
INTN
EFIAPI
StringNoCaseCompare (
  IN  CONST VOID  *Buffer1,
  IN  CONST VOID  *Buffer2
  )
{
  EFI_STATUS  Status;

  if (mUnicodeCollation == NULL) {
    Status = gBS->LocateProtocol (
                    &gEfiUnicodeCollation2ProtocolGuid,
                    NULL,
                    (VOID **)&mUnicodeCollation
                    );

    ASSERT_EFI_ERROR (Status);
  }

  return (mUnicodeCollation->StriColl (
                               mUnicodeCollation,
                               *(CHAR16 **)Buffer1,
                               *(CHAR16 **)Buffer2
                               ));
}

/**
  Function to compare 2 strings.

  @param[in] Buffer1            Pointer to String to compare (CHAR16**).
  @param[in] Buffer2            Pointer to second String to compare (CHAR16**).

  @retval 0                     Buffer1 equal to Buffer2.
  @retval <0                    Buffer1 is less than Buffer2.
  @retval >0                    Buffer1 is greater than Buffer2.
**/
INTN
EFIAPI
StringCompare (
  IN  CONST VOID  *Buffer1,
  IN  CONST VOID  *Buffer2
  )
{
  return (StrCmp (
            *(CHAR16 **)Buffer1,
            *(CHAR16 **)Buffer2
            ));
}