From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mga17.intel.com (mga17.intel.com [192.55.52.151]) by mx.groups.io with SMTP id smtpd.web12.3245.1634700008812335635 for ; Tue, 19 Oct 2021 20:20:09 -0700 Authentication-Results: mx.groups.io; dkim=pass header.i=@intel.onmicrosoft.com header.s=selector2-intel-onmicrosoft-com header.b=usxaAIwO; spf=pass (domain: intel.com, ip: 192.55.52.151, mailfrom: jian.j.wang@intel.com) X-IronPort-AV: E=McAfee;i="6200,9189,10142"; a="209475739" X-IronPort-AV: E=Sophos;i="5.87,165,1631602800"; d="scan'208";a="209475739" Received: from orsmga008.jf.intel.com ([10.7.209.65]) by fmsmga107.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 19 Oct 2021 20:20:07 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.87,165,1631602800"; d="scan'208";a="494423194" Received: from fmsmsx606.amr.corp.intel.com ([10.18.126.86]) by orsmga008.jf.intel.com with ESMTP; 19 Oct 2021 20:20:07 -0700 Received: from fmsmsx602.amr.corp.intel.com (10.18.126.82) by fmsmsx606.amr.corp.intel.com (10.18.126.86) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2242.12; Tue, 19 Oct 2021 20:20:06 -0700 Received: from fmsedg602.ED.cps.intel.com (10.1.192.136) by fmsmsx602.amr.corp.intel.com (10.18.126.82) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2242.12 via Frontend Transport; Tue, 19 Oct 2021 20:20:06 -0700 Received: from NAM10-MW2-obe.outbound.protection.outlook.com (104.47.55.105) by edgegateway.intel.com (192.55.55.71) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.2242.12; Tue, 19 Oct 2021 20:20:06 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=OqQkv2+XkDluYi3CKMuPKzVlirEmJwwbtyoU7TZcYuP2M87RIEMEXEM/e+AenhKxZPRnLXf+ZlFxWpDUOx3Jb7AsqcOPZDQnkp9p3I+ogsybR2gKhGs3MSNy1dN65heJPOPEWkG/mTTQVoUZg08Idx8ukD3/T567d99hsKHGuxHZgbKyoBC5flDNtFkI0tIcNfGjesbRqvNy5yALPi3u9ssBIcOkINpo3NKm3HaVp4vYqnXA4xNOV1SAlYluMCqxM1mIHRGgGu6xShai54hEHM1lA/tDvMZVjWERfpOxqnrcfCCaBdtZzuevDAqOl8YX9rauou+ECMcgtoEOTcOAUQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-AntiSpam-MessageData-ChunkCount:X-MS-Exchange-AntiSpam-MessageData-0:X-MS-Exchange-AntiSpam-MessageData-1; bh=lQYl/9iGV+1P5rsE07+QaVIg0knfXy798fA+ilcTelw=; b=Qvoa/t9+spnR1VzzDiuDt3MIbu4PBmzYdr0kH5+SAsYC53HmvUaqEYOEmSaAidXspU6sxwSsWJOPtIF0rFQN/QfMOlBts5esXmqVJA2Mo0QK3FbZ5Tzg420+OVrh7NKDBtdn5yUqlXnsxWUBmU7JQXELSyZJOhSBqqKMbrxGKmb5T4SnSWl4IYh+bTRzD/JiYVErpZut99VekKBsa3GzRZ0ZwjtaZhnjuyYD1M3krMpb2fq+L0DSmeS/5qsdRqDpyGHfYJJ8qmBNePuBJ2Bgn/Ir1qLbGPA2xixL9nL4IO9ovHsu3ZQOaF/NZ201L5XVXAYH4xPKjWawHWBCnebIpQ== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=intel.com; dmarc=pass action=none header.from=intel.com; dkim=pass header.d=intel.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=intel.onmicrosoft.com; s=selector2-intel-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=lQYl/9iGV+1P5rsE07+QaVIg0knfXy798fA+ilcTelw=; b=usxaAIwOlZ1f34bIiXVp6fRDu/OPhcw8fqh/ef/MlSgczoHFa7c4H6LjL06CVu1H5Uh2ejmsxaQ+dsALfuEKgab7Fe0x0uBHF1QyJ9fb1tWObgSanjqI1N/FyzJNozh3eT4ein+iTgXHWmKEGMwRzBf3b/FIalt9P+5GZ6N35Cg= Received: from CO1PR11MB4945.namprd11.prod.outlook.com (2603:10b6:303:9c::8) by CO1PR11MB5106.namprd11.prod.outlook.com (2603:10b6:303:93::17) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4608.18; Wed, 20 Oct 2021 03:20:00 +0000 Received: from CO1PR11MB4945.namprd11.prod.outlook.com ([fe80::752d:e1b:2ca:978f]) by CO1PR11MB4945.namprd11.prod.outlook.com ([fe80::752d:e1b:2ca:978f%9]) with mapi id 15.20.4608.018; Wed, 20 Oct 2021 03:20:00 +0000 From: "Wang, Jian J" To: "Kuo, IanX" , "devel@edk2.groups.io" CC: "Chan, Amy" , "Ni, Ray" , Liming Gao Subject: Re: [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib Thread-Topic: [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib Thread-Index: AQHXw9eokoodeHqnYU2a1LNa+wb2FqvbOquw Date: Wed, 20 Oct 2021 03:20:00 +0000 Message-ID: References: <20211018042127.1306-1-ianx.kuo@intel.com> <20211018042127.1306-2-ianx.kuo@intel.com> In-Reply-To: <20211018042127.1306-2-ianx.kuo@intel.com> Accept-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-reaction: no-action dlp-version: 11.6.200.16 dlp-product: dlpe-windows authentication-results: intel.com; dkim=none (message not signed) header.d=none;intel.com; dmarc=none action=none header.from=intel.com; x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 47713940-41d6-4ab1-1761-08d993788024 x-ms-traffictypediagnostic: CO1PR11MB5106: x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:8273; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: sjR2gUllEvCrDYanGdEhjFjO6gV8b8Q7FPF0A4r1LlwJg7KmDoNr8m811MibOR4nJ74WuF4QFY4pn3Nr4Dg047zG5v3UWzdwljR3qXy4/gTVTupDR2H27GyL+407Z26MolGo9c1D27L1UVnyTZqShxmwSAYBOLxq8LCVqt1HjI1vf8lei9QSh/+mXSOWHPlpxlz3fXXvRwr/kv2UP9jv1aLJVhLcfNrzAtfmUxmyfkJLXxIuPUfTLqsqOnCrAZX+UrzfjJoeVYS8ch9YYUqDVOhDmvRqk+ZYUiycBrWRwB459cD+VjW9b4Qly1YRFVm4k2YkfCrLnuO0xN4RY6zEAaiXKnw4YpI37L4wMr+IRmfdn8QTL+v7VsymT6N0O9q6wUQTgg92t6ASJSGBYCr9J5DU7nt4vLNy1UUU9VMxTLA/3mKOLajsgl6bFRU+kjcc7B0p5RJF7P1qa5REslTGCJYDchXHfu369nBBu4V6KGnxvPMrY0o2p7inmmrHdOQ+wTZuUzft00TETNCrJXk6jh9wDeMnKLywH+YKZjFEt39dDSFkIm6nHoXdp3oS78QtCXrlw8IZdfOZsaWv5GZMNnMuM4mABtOfDyK54tOiUvYXynEOL5tjJVZcDEZ668eLMETe9z0O+/BmSEVYR8Hh0XVsS2rl2bra2TMa8mJ179tv7EhlxWDjwsL0lk3Vm+X8qRIqZPMWAS/BdGtGXJ/58wWXpzHDc6R4UjY0wzRRH+WnxzGw3JGOdAr7vc5iTOYFVOYDOSyfmDHOwOBeRElqjzXLwaZfdP2ren+5nMHytC4= x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:CO1PR11MB4945.namprd11.prod.outlook.com;PTR:;CAT:NONE;SFS:(366004)(508600001)(966005)(53546011)(6506007)(110136005)(76116006)(54906003)(71200400001)(26005)(83380400001)(82960400001)(5660300002)(52536014)(8676002)(8936002)(66476007)(186003)(66556008)(66946007)(86362001)(4326008)(9686003)(316002)(38100700002)(38070700005)(2906002)(122000001)(33656002)(64756008)(55016002)(7696005)(66446008);DIR:OUT;SFP:1102; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?2dW0vZ1zjlneVTUHrb+p9e4LvcKcDA6VnF21VPUyF7F8mE84DciWs03CYfMg?= =?us-ascii?Q?8ydwno3irJ83ftOjBnqXTHlwAqCs5wF1Rc3syxuMfRB2DrCvitir/36CiYSI?= =?us-ascii?Q?EZEQSV9R9eGzn6IiO8rIBdKBHktDNgSLWDvoJacCOJ4QtBfXHtromMl0YKr5?= =?us-ascii?Q?HgxGPcvUwsqsIkfstkHrURHZAHdawYWkU5zRDXsbTTxey2ZJzwrZjJEmreaG?= =?us-ascii?Q?ybjXHvbKUBd0qy3l7Pdv4n6KfDo6aVvcAckHiOcsWirpx3BvD0KVcfFuYdds?= =?us-ascii?Q?uS0pt+Naj04mQZ5Odw0ja7NayL6q67Y4dIzHosE3b90miVRVAyxrn1MkqLsA?= =?us-ascii?Q?TNIZOhZKlPyNjWVYwmN8dyE2HyXa5wllUOZdBfSz85+8bJLuiv6OO/I8cQcm?= =?us-ascii?Q?0n8rRtPTj2kG4mNsHr94rYjo0vZ/9KGpNp5gGNPH0bny6spxcB8TEwrC5+Ib?= =?us-ascii?Q?ig53FYbAFXiwIRmIvjKsJtQJa+v6el3UdxYAxe1QQ8g+hmu7WYQ/JGjoLWuF?= =?us-ascii?Q?q3vc343S4kZb8zFYpgfSvmQX9t2RQgmU4+opZnp4aL6+NX64cXzz9QWtwHcJ?= =?us-ascii?Q?mNKYZPmqEhXsCjDYYcactaIMRaChRqW4r8i3x+QrxOxHeQdkbOW5x+kj1dtO?= =?us-ascii?Q?W8fYAdLuvqM9zn4TjK37tjSjSMqrbc7VsVrh6vsVdFdw7MZUny+qwsRw1BKA?= =?us-ascii?Q?AIOS4xM9lzNf6mrb/Kln4kh07HhtymfzcryBwvC2lcR82qud13jqGyIsL7FA?= =?us-ascii?Q?s4WaK0dC7k8DdmSTxA95X+SIniYKOlwX0Pqx/5nHvhESfKTKLL87MportGma?= =?us-ascii?Q?WqYVE+EvJ19gFzZU2DUP3JclyF6yIv3q3YzJpfNwae+focTj6Nldg2M6uKCn?= =?us-ascii?Q?Qz++c008eJFEP8GGvZrodus62hTpBZ7NP9aIhUMyMmSBbF3/FDa+6jmAfLnA?= =?us-ascii?Q?daAvp3OWPaOxRO+mDcukU+JH8XCCAKVRf5lolhoBNCqQjsyfZDgDHTj2P6uc?= =?us-ascii?Q?H+HUKyyP0ittxMjWinXB6Hhj0wCRWhsv4HWVvI2LPf04sgDQ74TlutqHA5QU?= =?us-ascii?Q?xe7XLDpCZLF8n4htj2f2TY/HAlTPBK+PbMjw9QN7P3Ueqppoum7GFrqJIgWY?= =?us-ascii?Q?Z9cqEzbCXJpyRZlkZ867e6Pt1ABNWXzLJBIPGzXMC6TlF8TjulAhcG5G/4Fo?= =?us-ascii?Q?opOwuk/IIzze9WpVYV9oM3rSAjVnmtVpryaVzx9V9pWrHxmkozMI5Lf2HuRY?= =?us-ascii?Q?KTpvNMpKwbZKTg/q4xwM7WGnzwyJA1XE+8v8bqgMXdLH8bOE6AsqcpONzmdR?= =?us-ascii?Q?fZwAERbGETi09G+HOwHTBvMZ?= MIME-Version: 1.0 X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: CO1PR11MB4945.namprd11.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 47713940-41d6-4ab1-1761-08d993788024 X-MS-Exchange-CrossTenant-originalarrivaltime: 20 Oct 2021 03:20:00.3310 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 46c98d88-e344-4ed4-8496-4ed7712e255d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: AWJY5Q8a+EGMMJzKm6iB3Gzg6CmJdJQ2vNj6EMgscq22HuAjsssXk3vpzksNaH342Ck5rSC/mJ2NDKYVapfBhA== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CO1PR11MB5106 Return-Path: jian.j.wang@intel.com X-OriginatorOrg: intel.com Content-Language: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Reviewed-by: Jian J Wang Regards, Jian > -----Original Message----- > From: Kuo, IanX > Sent: Monday, October 18, 2021 12:21 PM > To: devel@edk2.groups.io > Cc: Chan, Amy ; Ni, Ray ; Kuo, IanX > ; Wang, Jian J ; Liming Gao > > Subject: [PATCH v6 1/3] MdeModulePkg/SortLib: Add QuickSort function on > BaseLib >=20 > From: IanX Kuo >=20 > REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675 >=20 > Use QuickSort instead of QuickSortWorker >=20 > Cc: Ray Ni > Cc: Jian J Wang > Cc: Liming Gao > Signed-off-by: IanX Kuo > --- > .../Library/BaseSortLib/BaseSortLib.c | 115 +---------------- > .../Library/UefiSortLib/UefiSortLib.c | 116 +----------------- > 2 files changed, 8 insertions(+), 223 deletions(-) >=20 > diff --git a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c > b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c > index a12c7bc0ec..0903943ee4 100644 > --- a/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c > +++ b/MdeModulePkg/Library/BaseSortLib/BaseSortLib.c > @@ -1,7 +1,7 @@ > /** @file >=20 > Library used for sorting routines. >=20 >=20 >=20 > - Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved. >=20 > + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. >=20 > SPDX-License-Identifier: BSD-2-Clause-Patent >=20 >=20 >=20 > **/ >=20 > @@ -13,114 +13,6 @@ > #include >=20 > #include >=20 >=20 >=20 > -/** >=20 > - Worker function for QuickSorting. This function is identical to > PerformQuickSort, >=20 > - except that is uses the pre-allocated buffer so the in place sorting d= oes not > need to >=20 > - allocate and free buffers constantly. >=20 > - >=20 > - Each element must be equal sized. >=20 > - >=20 > - if BufferToSort is NULL, then ASSERT. >=20 > - if CompareFunction is NULL, then ASSERT. >=20 > - if Buffer is NULL, then ASSERT. >=20 > - >=20 > - if Count is < 2 then perform no action. >=20 > - if Size is < 1 then perform no action. >=20 > - >=20 > - @param[in, out] BufferToSort on call a Buffer of (possibly sorted) e= lements >=20 > - on return a buffer of sorted elements >=20 > - @param[in] Count the number of elements in the buffer to= sort >=20 > - @param[in] ElementSize Size of an element in bytes >=20 > - @param[in] CompareFunction The function to call to perform the > comparison >=20 > - of any 2 elements >=20 > - @param[in] Buffer Buffer of size ElementSize for use in s= wapping >=20 > -**/ >=20 > -VOID >=20 > -EFIAPI >=20 > -QuickSortWorker ( >=20 > - IN OUT VOID *BufferToSort, >=20 > - IN CONST UINTN Count, >=20 > - IN CONST UINTN ElementSize, >=20 > - IN SORT_COMPARE CompareFunction, >=20 > - IN VOID *Buffer >=20 > - ) >=20 > -{ >=20 > - VOID *Pivot; >=20 > - UINTN LoopCount; >=20 > - UINTN NextSwapLocation; >=20 > - >=20 > - ASSERT(BufferToSort !=3D NULL); >=20 > - ASSERT(CompareFunction !=3D NULL); >=20 > - ASSERT(Buffer !=3D NULL); >=20 > - >=20 > - if ( Count < 2 >=20 > - || ElementSize < 1 >=20 > - ){ >=20 > - return; >=20 > - } >=20 > - >=20 > - NextSwapLocation =3D 0; >=20 > - >=20 > - // >=20 > - // pick a pivot (we choose last element) >=20 > - // >=20 > - Pivot =3D ((UINT8*)BufferToSort+((Count-1)*ElementSize)); >=20 > - >=20 > - // >=20 > - // Now get the pivot such that all on "left" are below it >=20 > - // and everything "right" are above it >=20 > - // >=20 > - for ( LoopCount =3D 0 >=20 > - ; LoopCount < Count -1 >=20 > - ; LoopCount++ >=20 > - ){ >=20 > - // >=20 > - // if the element is less than the pivot >=20 > - // >=20 > - if > (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)), > Pivot) <=3D 0){ >=20 > - // >=20 > - // swap >=20 > - // >=20 > - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSiz= e), > ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, > ElementSize); >=20 > - >=20 > - // >=20 > - // increment NextSwapLocation >=20 > - // >=20 > - NextSwapLocation++; >=20 > - } >=20 > - } >=20 > - // >=20 > - // swap pivot to it's final position (NextSwapLocaiton) >=20 > - // >=20 > - CopyMem (Buffer, Pivot, ElementSize); >=20 > - CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, > ElementSize); >=20 > - >=20 > - // >=20 > - // Now recurse on 2 paritial lists. neither of these will have the 'p= ivot' element >=20 > - // IE list is sorted left half, pivot element, sorted right half... >=20 > - // >=20 > - if (NextSwapLocation >=3D 2) { >=20 > - QuickSortWorker( >=20 > - BufferToSort, >=20 > - NextSwapLocation, >=20 > - ElementSize, >=20 > - CompareFunction, >=20 > - Buffer); >=20 > - } >=20 > - >=20 > - if ((Count - NextSwapLocation - 1) >=3D 2) { >=20 > - QuickSortWorker( >=20 > - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize, >=20 > - Count - NextSwapLocation - 1, >=20 > - ElementSize, >=20 > - CompareFunction, >=20 > - Buffer); >=20 > - } >=20 > - return; >=20 > -} >=20 > /** >=20 > Function to perform a Quick Sort alogrithm on a buffer of comparable > elements. >=20 >=20 >=20 > @@ -156,12 +48,13 @@ PerformQuickSort ( > Buffer =3D AllocateZeroPool(ElementSize); >=20 > ASSERT(Buffer !=3D NULL); >=20 >=20 >=20 > - QuickSortWorker( >=20 > + QuickSort ( >=20 > BufferToSort, >=20 > Count, >=20 > ElementSize, >=20 > CompareFunction, >=20 > - Buffer); >=20 > + Buffer >=20 > + ); >=20 >=20 >=20 > FreePool(Buffer); >=20 > return; >=20 > diff --git a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c > b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c > index 46dc443638..29d8735c22 100644 > --- a/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c > +++ b/MdeModulePkg/Library/UefiSortLib/UefiSortLib.c > @@ -1,7 +1,7 @@ > /** @file >=20 > Library used for sorting routines. >=20 >=20 >=20 > - Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved. >=20 > + Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved. >=20 > SPDX-License-Identifier: BSD-2-Clause-Patent >=20 >=20 >=20 > **/ >=20 > @@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL > *mUnicodeCollation =3D NULL; > } \ >=20 > } >=20 >=20 >=20 > -/** >=20 > - Worker function for QuickSorting. This function is identical to > PerformQuickSort, >=20 > - except that is uses the pre-allocated buffer so the in place sorting d= oes not > need to >=20 > - allocate and free buffers constantly. >=20 > - >=20 > - Each element must be equal sized. >=20 > - >=20 > - if BufferToSort is NULL, then ASSERT. >=20 > - if CompareFunction is NULL, then ASSERT. >=20 > - if Buffer is NULL, then ASSERT. >=20 > - >=20 > - if Count is < 2 then perform no action. >=20 > - if Size is < 1 then perform no action. >=20 > - >=20 > - @param[in, out] BufferToSort on call a Buffer of (possibly sorted) e= lements >=20 > - on return a buffer of sorted elements >=20 > - @param[in] Count the number of elements in the buffer to= sort >=20 > - @param[in] ElementSize Size of an element in bytes >=20 > - @param[in] CompareFunction The function to call to perform the > comparison >=20 > - of any 2 elements >=20 > - @param[in] Buffer Buffer of size ElementSize for use in s= wapping >=20 > -**/ >=20 > -VOID >=20 > -EFIAPI >=20 > -QuickSortWorker ( >=20 > - IN OUT VOID *BufferToSort, >=20 > - IN CONST UINTN Count, >=20 > - IN CONST UINTN ElementSize, >=20 > - IN SORT_COMPARE CompareFunction, >=20 > - IN VOID *Buffer >=20 > - ) >=20 > -{ >=20 > - VOID *Pivot; >=20 > - UINTN LoopCount; >=20 > - UINTN NextSwapLocation; >=20 > - >=20 > - ASSERT(BufferToSort !=3D NULL); >=20 > - ASSERT(CompareFunction !=3D NULL); >=20 > - ASSERT(Buffer !=3D NULL); >=20 > - >=20 > - if ( Count < 2 >=20 > - || ElementSize < 1 >=20 > - ){ >=20 > - return; >=20 > - } >=20 > - >=20 > - NextSwapLocation =3D 0; >=20 > - >=20 > - // >=20 > - // pick a pivot (we choose last element) >=20 > - // >=20 > - Pivot =3D ((UINT8*)BufferToSort+((Count-1)*ElementSize)); >=20 > - >=20 > - // >=20 > - // Now get the pivot such that all on "left" are below it >=20 > - // and everything "right" are above it >=20 > - // >=20 > - for ( LoopCount =3D 0 >=20 > - ; LoopCount < Count -1 >=20 > - ; LoopCount++ >=20 > - ){ >=20 > - // >=20 > - // if the element is less than the pivot >=20 > - // >=20 > - if > (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementSize)), > Pivot) <=3D 0){ >=20 > - // >=20 > - // swap >=20 > - // >=20 > - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSiz= e), > ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > (UINT8*)BufferToSort+((LoopCount)*ElementSize), ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, > ElementSize); >=20 > - >=20 > - // >=20 > - // increment NextSwapLocation >=20 > - // >=20 > - NextSwapLocation++; >=20 > - } >=20 > - } >=20 > - // >=20 > - // swap pivot to it's final position (NextSwapLocaiton) >=20 > - // >=20 > - CopyMem (Buffer, Pivot, ElementSize); >=20 > - CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), > ElementSize); >=20 > - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, > ElementSize); >=20 > - >=20 > - // >=20 > - // Now recurse on 2 paritial lists. neither of these will have the 'p= ivot' element >=20 > - // IE list is sorted left half, pivot element, sorted right half... >=20 > - // >=20 > - if (NextSwapLocation >=3D 2) { >=20 > - QuickSortWorker( >=20 > - BufferToSort, >=20 > - NextSwapLocation, >=20 > - ElementSize, >=20 > - CompareFunction, >=20 > - Buffer); >=20 > - } >=20 > - >=20 > - if ((Count - NextSwapLocation - 1) >=3D 2) { >=20 > - QuickSortWorker( >=20 > - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize, >=20 > - Count - NextSwapLocation - 1, >=20 > - ElementSize, >=20 > - CompareFunction, >=20 > - Buffer); >=20 > - } >=20 > - >=20 > - return; >=20 > -} >=20 > /** >=20 > Function to perform a Quick Sort alogrithm on a buffer of comparable > elements. >=20 >=20 >=20 > @@ -173,12 +64,13 @@ PerformQuickSort ( > Buffer =3D AllocateZeroPool(ElementSize); >=20 > ASSERT(Buffer !=3D NULL); >=20 >=20 >=20 > - QuickSortWorker( >=20 > + QuickSort ( >=20 > BufferToSort, >=20 > Count, >=20 > ElementSize, >=20 > CompareFunction, >=20 > - Buffer); >=20 > + Buffer >=20 > + ); >=20 >=20 >=20 > FreePool(Buffer); >=20 > return; >=20 > -- > 2.30.0.windows.1