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

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