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

/** @file\r
  Library used for sorting routines.\r
\r
  Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>\r
  This program and the accompanying materials\r
  are licensed and made available under the terms and conditions of the BSD License\r
  which accompanies this distribution.  The full text of the license may be found at\r
  http://opensource.org/licenses/bsd-license.php\r
\r
  THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
  WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
\r
**/\r
\r
#include <Uefi.h>\r
\r
#include <Protocol/UnicodeCollation.h>\r
#include <Protocol/DevicePath.h>\r
\r
#include <Library/UefiBootServicesTableLib.h>\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
#include <Library/DevicePathLib.h>\r
\r
STATIC EFI_UNICODE_COLLATION_PROTOCOL   *mUnicodeCollation = NULL;\r
\r
#define USL_FREE_NON_NULL(Pointer)  \\r
{                                     \\r
  if ((Pointer) != NULL) {            \\r
  FreePool((Pointer));                \\r
  (Pointer) = NULL;                   \\r
  }                                   \\r
}\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
\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
  Function to compare 2 device paths for use in QuickSort.\r
\r
  @param[in] Buffer1            pointer to Device Path poiner to compare\r
  @param[in] Buffer2            pointer to second DevicePath pointer to compare\r
\r
  @retval 0                     Buffer1 equal to Buffer2\r
  @retval <0                    Buffer1 is less than Buffer2\r
  @retval >0                    Buffer1 is greater than Buffer2\r
**/\r
INTN\r
EFIAPI\r
DevicePathCompare (\r
  IN  CONST VOID             *Buffer1,\r
  IN  CONST VOID             *Buffer2\r
  )\r
{\r
  EFI_DEVICE_PATH_PROTOCOL  *DevicePath1;\r
  EFI_DEVICE_PATH_PROTOCOL  *DevicePath2;\r
  CHAR16                    *TextPath1;\r
  CHAR16                    *TextPath2;\r
  EFI_STATUS                Status;\r
  INTN                      RetVal;\r
\r
  DevicePath1 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer1;\r
  DevicePath2 = *(EFI_DEVICE_PATH_PROTOCOL**)Buffer2;\r
\r
  if (DevicePath1 == NULL) {\r
    if (DevicePath2 == NULL) {\r
      return 0;\r
    }\r
\r
    return -1;\r
  }\r
\r
  if (DevicePath2 == NULL) {\r
    return 1;\r
  }\r
\r
  if (mUnicodeCollation == NULL) {\r
    Status = gBS->LocateProtocol(\r
      &gEfiUnicodeCollation2ProtocolGuid,\r
      NULL,\r
      (VOID**)&mUnicodeCollation);\r
\r
    ASSERT_EFI_ERROR(Status);\r
  }\r
\r
  TextPath1 = ConvertDevicePathToText(\r
    DevicePath1,\r
    FALSE,\r
    FALSE);\r
\r
  TextPath2 = ConvertDevicePathToText(\r
    DevicePath2,\r
    FALSE,\r
    FALSE);\r
\r
  if (TextPath1 == NULL) {\r
    RetVal = -1;\r
  } else if (TextPath2 == NULL) {\r
    RetVal = 1;\r
  } else {\r
    RetVal = mUnicodeCollation->StriColl(\r
      mUnicodeCollation,\r
      TextPath1,\r
      TextPath2);\r
  }\r
\r
  USL_FREE_NON_NULL(TextPath1);\r
  USL_FREE_NON_NULL(TextPath2);\r
\r
  return (RetVal);\r
}\r
\r
/**\r
  Function to compare 2 strings without regard to case of the characters.\r
\r
  @param[in] Buffer1            Pointer to String to compare.\r
  @param[in] Buffer2            Pointer to second String to compare.\r
\r
  @retval 0                     Buffer1 equal to Buffer2.\r
  @retval <0                    Buffer1 is less than Buffer2.\r
  @retval >0                    Buffer1 is greater than Buffer2.\r
**/\r
INTN\r
EFIAPI\r
StringNoCaseCompare (\r
  IN  CONST VOID             *Buffer1,\r
  IN  CONST VOID             *Buffer2\r
  )\r
{\r
  EFI_STATUS                Status;\r
  if (mUnicodeCollation == NULL) {\r
    Status = gBS->LocateProtocol(\r
      &gEfiUnicodeCollation2ProtocolGuid,\r
      NULL,\r
      (VOID**)&mUnicodeCollation);\r
\r
    ASSERT_EFI_ERROR(Status);\r
  }\r
\r
  return (mUnicodeCollation->StriColl(\r
    mUnicodeCollation,\r
    *(CHAR16**)Buffer1,\r
    *(CHAR16**)Buffer2));\r
}\r
\r
\r
/**\r
  Function to compare 2 strings.\r
\r
  @param[in] Buffer1            Pointer to String to compare (CHAR16**).\r
  @param[in] Buffer2            Pointer to second String to compare (CHAR16**).\r
\r
  @retval 0                     Buffer1 equal to Buffer2.\r
  @retval <0                    Buffer1 is less than Buffer2.\r
  @retval >0                    Buffer1 is greater than Buffer2.\r
**/\r
INTN\r
EFIAPI\r
StringCompare (\r
  IN  CONST VOID                *Buffer1,\r
  IN  CONST VOID                *Buffer2\r
  )\r
{\r
  return (StrCmp(\r
    *(CHAR16**)Buffer1,\r
    *(CHAR16**)Buffer2));\r
}\r
Commit	Line	Data
	1	/** @file\r
	2	Library used for sorting routines.\r
	3	\r
	4	Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. <BR>\r
	5	This program and the accompanying materials\r
	6	are licensed and made available under the terms and conditions of the BSD License\r
	7	which accompanies this distribution. The full text of the license may be found at\r
	8	http://opensource.org/licenses/bsd-license.php\r
	9	\r
	10	THE PROGRAM IS DISTRIBUTED UNDER THE BSD LICENSE ON AN "AS IS" BASIS,\r
	11	WITHOUT WARRANTIES OR REPRESENTATIONS OF ANY KIND, EITHER EXPRESS OR IMPLIED.\r
	12	\r
	13	**/\r
	14	\r
	15	#include <Uefi.h>\r
	16	\r
	17	#include <Protocol/UnicodeCollation.h>\r
	18	#include <Protocol/DevicePath.h>\r
	19	\r
	20	#include <Library/UefiBootServicesTableLib.h>\r
	21	#include <Library/BaseLib.h>\r
	22	#include <Library/BaseMemoryLib.h>\r
	23	#include <Library/DebugLib.h>\r
	24	#include <Library/MemoryAllocationLib.h>\r
	25	#include <Library/SortLib.h>\r
	26	#include <Library/DevicePathLib.h>\r
	27	\r
	28	STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollation = NULL;\r
	29	\r
	30	#define USL_FREE_NON_NULL(Pointer) \\r
	31	{ \\r
	32	if ((Pointer) != NULL) { \\r
	33	FreePool((Pointer)); \\r
	34	(Pointer) = NULL; \\r
	35	} \\r
	36	}\r
	37	\r
	38	/**\r
	39	Worker function for QuickSorting. This function is identical to PerformQuickSort,\r
	40	except that is uses the pre-allocated buffer so the in place sorting does not need to\r
	41	allocate and free buffers constantly.\r
	42	\r
	43	Each element must be equal sized.\r
	44	\r
	45	if BufferToSort is NULL, then ASSERT.\r
	46	if CompareFunction is NULL, then ASSERT.\r
	47	if Buffer is NULL, then ASSERT.\r
	48	\r
	49	if Count is < 2 then perform no action.\r
	50	if Size is < 1 then perform no action.\r
	51	\r
	52	@param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r
	53	on return a buffer of sorted elements\r
	54	@param[in] Count the number of elements in the buffer to sort\r
	55	@param[in] ElementSize Size of an element in bytes\r
	56	@param[in] CompareFunction The function to call to perform the comparison\r
	57	of any 2 elements\r
	58	@param[in] Buffer Buffer of size ElementSize for use in swapping\r
	59	**/\r
	60	VOID\r
	61	EFIAPI\r
	62	QuickSortWorker (\r
	63	IN OUT VOID *BufferToSort,\r
	64	IN CONST UINTN Count,\r
	65	IN CONST UINTN ElementSize,\r
	66	IN SORT_COMPARE CompareFunction,\r
	67	IN VOID *Buffer\r
	68	)\r
	69	{\r
	70	VOID *Pivot;\r
	71	UINTN LoopCount;\r
	72	UINTN NextSwapLocation;\r
	73	\r
	74	ASSERT(BufferToSort != NULL);\r
	75	ASSERT(CompareFunction != NULL);\r
	76	ASSERT(Buffer != NULL);\r
	77	\r
	78	if ( Count < 2\r
	79	\|\| ElementSize < 1\r
	80	){\r
	81	return;\r
	82	}\r
	83	\r
	84	NextSwapLocation = 0;\r
	85	\r
	86	//\r
	87	// pick a pivot (we choose last element)\r
	88	//\r
	89	Pivot = ((UINT8)BufferToSort+((Count-1)ElementSize));\r
	90	\r
	91	//\r
	92	// Now get the pivot such that all on "left" are below it\r
	93	// and everything "right" are above it\r
	94	//\r
	95	for ( LoopCount = 0\r
	96	; LoopCount < Count -1\r
	97	; LoopCount++\r
	98	){\r
	99	//\r
	100	// if the element is less than the pivot\r
	101	//\r
	102	if (CompareFunction((VOID)((UINT8)BufferToSort+((LoopCount)*ElementSize)),Pivot) <= 0){\r
	103	//\r
	104	// swap\r
	105	//\r
	106	CopyMem (Buffer, (UINT8)BufferToSort+(NextSwapLocationElementSize), ElementSize);\r
	107	CopyMem ((UINT8)BufferToSort+(NextSwapLocationElementSize), (UINT8)BufferToSort+((LoopCount)ElementSize), ElementSize);\r
	108	CopyMem ((UINT8)BufferToSort+((LoopCount)ElementSize), Buffer, ElementSize);\r
	109	\r
	110	//\r
	111	// increment NextSwapLocation\r
	112	//\r
	113	NextSwapLocation++;\r
	114	}\r
	115	}\r
	116	//\r
	117	// swap pivot to it's final position (NextSwapLocaiton)\r
	118	//\r
	119	CopyMem (Buffer, Pivot, ElementSize);\r
	120	CopyMem (Pivot, (UINT8)BufferToSort+(NextSwapLocationElementSize), ElementSize);\r
	121	CopyMem ((UINT8)BufferToSort+(NextSwapLocationElementSize), Buffer, ElementSize);\r
	122	\r
	123	//\r
	124	// Now recurse on 2 paritial lists. neither of these will have the 'pivot' element\r
	125	// IE list is sorted left half, pivot element, sorted right half...\r
	126	//\r
	127	if (NextSwapLocation >= 2) {\r
	128	QuickSortWorker(\r
	129	BufferToSort,\r
	130	NextSwapLocation,\r
	131	ElementSize,\r
	132	CompareFunction,\r
	133	Buffer);\r
	134	}\r
	135	\r
	136	if ((Count - NextSwapLocation - 1) >= 2) {\r
	137	QuickSortWorker(\r
	138	(UINT8 )BufferToSort + (NextSwapLocation+1) ElementSize,\r
	139	Count - NextSwapLocation - 1,\r
	140	ElementSize,\r
	141	CompareFunction,\r
	142	Buffer);\r
	143	}\r
	144	\r
	145	return;\r
	146	}\r
	147	/**\r
	148	Function to perform a Quick Sort alogrithm on a buffer of comparable elements.\r
	149	\r
	150	Each element must be equal sized.\r
	151	\r
	152	if BufferToSort is NULL, then ASSERT.\r
	153	if CompareFunction is NULL, then ASSERT.\r
	154	\r
	155	if Count is < 2 then perform no action.\r
	156	if Size is < 1 then perform no action.\r
	157	\r
	158	@param[in, out] BufferToSort on call a Buffer of (possibly sorted) elements\r
	159	on return a buffer of sorted elements\r
	160	@param[in] Count the number of elements in the buffer to sort\r
	161	@param[in] ElementSize Size of an element in bytes\r
	162	@param[in] CompareFunction The function to call to perform the comparison\r
	163	of any 2 elements\r
	164	**/\r
	165	VOID\r
	166	EFIAPI\r
	167	PerformQuickSort (\r
	168	IN OUT VOID *BufferToSort,\r
	169	IN CONST UINTN Count,\r
	170	IN CONST UINTN ElementSize,\r
	171	IN SORT_COMPARE CompareFunction\r
	172	)\r
	173	{\r
	174	VOID *Buffer;\r
	175	\r
	176	ASSERT(BufferToSort != NULL);\r
	177	ASSERT(CompareFunction != NULL);\r
	178	\r
	179	Buffer = AllocateZeroPool(ElementSize);\r
	180	ASSERT(Buffer != NULL);\r
	181	\r
	182	QuickSortWorker(\r
	183	BufferToSort,\r
	184	Count,\r
	185	ElementSize,\r
	186	CompareFunction,\r
	187	Buffer);\r
	188	\r
	189	FreePool(Buffer);\r
	190	return;\r
	191	}\r
	192	\r
	193	/**\r
	194	Function to compare 2 device paths for use in QuickSort.\r
	195	\r
	196	@param[in] Buffer1 pointer to Device Path poiner to compare\r
	197	@param[in] Buffer2 pointer to second DevicePath pointer to compare\r
	198	\r
	199	@retval 0 Buffer1 equal to Buffer2\r
	200	@retval <0 Buffer1 is less than Buffer2\r
	201	@retval >0 Buffer1 is greater than Buffer2\r
	202	**/\r
	203	INTN\r
	204	EFIAPI\r
	205	DevicePathCompare (\r
	206	IN CONST VOID *Buffer1,\r
	207	IN CONST VOID *Buffer2\r
	208	)\r
	209	{\r
	210	EFI_DEVICE_PATH_PROTOCOL *DevicePath1;\r
	211	EFI_DEVICE_PATH_PROTOCOL *DevicePath2;\r
	212	CHAR16 *TextPath1;\r
	213	CHAR16 *TextPath2;\r
	214	EFI_STATUS Status;\r
	215	INTN RetVal;\r
	216	\r
	217	DevicePath1 = (EFI_DEVICE_PATH_PROTOCOL*)Buffer1;\r
	218	DevicePath2 = (EFI_DEVICE_PATH_PROTOCOL*)Buffer2;\r
	219	\r
	220	if (DevicePath1 == NULL) {\r
	221	if (DevicePath2 == NULL) {\r
	222	return 0;\r
	223	}\r
	224	\r
	225	return -1;\r
	226	}\r
	227	\r
	228	if (DevicePath2 == NULL) {\r
	229	return 1;\r
	230	}\r
	231	\r
	232	if (mUnicodeCollation == NULL) {\r
	233	Status = gBS->LocateProtocol(\r
	234	&gEfiUnicodeCollation2ProtocolGuid,\r
	235	NULL,\r
	236	(VOID**)&mUnicodeCollation);\r
	237	\r
	238	ASSERT_EFI_ERROR(Status);\r
	239	}\r
	240	\r
	241	TextPath1 = ConvertDevicePathToText(\r
	242	DevicePath1,\r
	243	FALSE,\r
	244	FALSE);\r
	245	\r
	246	TextPath2 = ConvertDevicePathToText(\r
	247	DevicePath2,\r
	248	FALSE,\r
	249	FALSE);\r
	250	\r
	251	if (TextPath1 == NULL) {\r
	252	RetVal = -1;\r
	253	} else if (TextPath2 == NULL) {\r
	254	RetVal = 1;\r
	255	} else {\r
	256	RetVal = mUnicodeCollation->StriColl(\r
	257	mUnicodeCollation,\r
	258	TextPath1,\r
	259	TextPath2);\r
	260	}\r
	261	\r
	262	USL_FREE_NON_NULL(TextPath1);\r
	263	USL_FREE_NON_NULL(TextPath2);\r
	264	\r
	265	return (RetVal);\r
	266	}\r
	267	\r
	268	/**\r
	269	Function to compare 2 strings without regard to case of the characters.\r
	270	\r
	271	@param[in] Buffer1 Pointer to String to compare.\r
	272	@param[in] Buffer2 Pointer to second String to compare.\r
	273	\r
	274	@retval 0 Buffer1 equal to Buffer2.\r
	275	@retval <0 Buffer1 is less than Buffer2.\r
	276	@retval >0 Buffer1 is greater than Buffer2.\r
	277	**/\r
	278	INTN\r
	279	EFIAPI\r
	280	StringNoCaseCompare (\r
	281	IN CONST VOID *Buffer1,\r
	282	IN CONST VOID *Buffer2\r
	283	)\r
	284	{\r
	285	EFI_STATUS Status;\r
	286	if (mUnicodeCollation == NULL) {\r
	287	Status = gBS->LocateProtocol(\r
	288	&gEfiUnicodeCollation2ProtocolGuid,\r
	289	NULL,\r
	290	(VOID**)&mUnicodeCollation);\r
	291	\r
	292	ASSERT_EFI_ERROR(Status);\r
	293	}\r
	294	\r
	295	return (mUnicodeCollation->StriColl(\r
	296	mUnicodeCollation,\r
	297	(CHAR16*)Buffer1,\r
	298	(CHAR16*)Buffer2));\r
	299	}\r
	300	\r
	301	\r
	302	/**\r
	303	Function to compare 2 strings.\r
	304	\r
	305	@param[in] Buffer1 Pointer to String to compare (CHAR16**).\r
	306	@param[in] Buffer2 Pointer to second String to compare (CHAR16**).\r
	307	\r
	308	@retval 0 Buffer1 equal to Buffer2.\r
	309	@retval <0 Buffer1 is less than Buffer2.\r
	310	@retval >0 Buffer1 is greater than Buffer2.\r
	311	**/\r
	312	INTN\r
	313	EFIAPI\r
	314	StringCompare (\r
	315	IN CONST VOID *Buffer1,\r
	316	IN CONST VOID *Buffer2\r
	317	)\r
	318	{\r
	319	return (StrCmp(\r
	320	(CHAR16*)Buffer1,\r
	321	(CHAR16*)Buffer2));\r
	322	}\r