From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mga12.intel.com (mga12.intel.com [192.55.52.136]) by mx.groups.io with SMTP id smtpd.web09.30738.1634522325522664272 for ; Sun, 17 Oct 2021 18:58:45 -0700 Authentication-Results: mx.groups.io; dkim=pass header.i=@intel.onmicrosoft.com header.s=selector2-intel-onmicrosoft-com header.b=YsdKfNG1; spf=pass (domain: intel.com, ip: 192.55.52.136, mailfrom: ianx.kuo@intel.com) X-IronPort-AV: E=McAfee;i="6200,9189,10140"; a="208258464" X-IronPort-AV: E=Sophos;i="5.85,380,1624345200"; d="scan'208";a="208258464" Received: from fmsmga008.fm.intel.com ([10.253.24.58]) by fmsmga106.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 17 Oct 2021 18:58:41 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.85,380,1624345200"; d="scan'208";a="529981520" Received: from orsmsx602.amr.corp.intel.com ([10.22.229.15]) by fmsmga008.fm.intel.com with ESMTP; 17 Oct 2021 18:58:41 -0700 Received: from orsmsx612.amr.corp.intel.com (10.22.229.25) by ORSMSX602.amr.corp.intel.com (10.22.229.15) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2242.12; Sun, 17 Oct 2021 18:58:41 -0700 Received: from orsmsx606.amr.corp.intel.com (10.22.229.19) by ORSMSX612.amr.corp.intel.com (10.22.229.25) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2242.12; Sun, 17 Oct 2021 18:58:40 -0700 Received: from orsedg603.ED.cps.intel.com (10.7.248.4) by orsmsx606.amr.corp.intel.com (10.22.229.19) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.2242.12 via Frontend Transport; Sun, 17 Oct 2021 18:58:40 -0700 Received: from NAM11-DM6-obe.outbound.protection.outlook.com (104.47.57.176) by edgegateway.intel.com (134.134.137.100) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.2242.12; Sun, 17 Oct 2021 18:58:40 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=BDda/QSXurxvDeLVSc+o7mOaUGSIMUK7Opq0FIuSir2iX1lSUytxCblWhCLzlgLJUjvgp961NMT4HQaYSoSNkzR5JS95ze/h4NjwNDuzOWDDsG6lipt1IqkhW1FYdJyjwjogQ7WA3pbn5qGxNE0VaqxjHugUd7rhHVbG7rFlvA+TCDuuOAUHcxE/PsvZIpUQCunfBomhlNR2eAF+CVqFnZWDAC7mCekUwvCn0CIT+LOjxyMBLTohZHvwAvX0WVwP7+DMEZeGU/kmvmqq4J6YKHwHT6jPqVBhEIMYxNTtuDvWrRIP3fNtHnyS9HV0heKeCQPXTx4yHq+SXqTBZ06a2w== 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=UkfkDJveaWeA0Dr73rvhmQ7WxnYIRpHJ36avyudi/ck=; b=Blyp3ALd3B566z7MeN7ec+b6eqce1wtz4otlTG92XFIjfCxOMZ1gc/MEkdqEIdWEpY9K6UBJ8LQXxQYRXZItHLPkdjVUuG1w5rCxQNO1x+8qESjqbeVRhwKXnfi4Dar9Bg68iTQnaNd2n3hCYsdeeKwBgQUvI5cYMbmRJFel7MddzmVEXzxAk3RfUccSjvGCDSb+lcZPDJkENVpRV1XhE3VGyICPnFQwbadW0VayCO0vyhgwHxx+0d3/5WtFohsq8UDoT/oryymoOFQz8yHrZgyt3QEHL39LBHfxHlCUl90FFpV+7XpfTpxfaoK3GXsLSZBj+7LmR59WPJunrpANzQ== 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=UkfkDJveaWeA0Dr73rvhmQ7WxnYIRpHJ36avyudi/ck=; b=YsdKfNG1mFf5KW94vo7ZVzpp1jHGBxjZJhdchAWF1HWR9ovWRgbBcl/iN+YX4w1WFS4YIE2eLCZUZ4aSuty1J1dqLozBD/ui4/APLXvoLMgFG7cPnEuha9ofWHd+Lu9okZ9LsIISJkmQBVrSK+P2rfl4Hwdud+QzJsYDypSNprA= Received: from PH0PR11MB5174.namprd11.prod.outlook.com (2603:10b6:510:3b::12) by PH0PR11MB5110.namprd11.prod.outlook.com (2603:10b6:510:3f::13) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.4608.16; Mon, 18 Oct 2021 01:58:39 +0000 Received: from PH0PR11MB5174.namprd11.prod.outlook.com ([fe80::4435:90ac:24fe:b6a6]) by PH0PR11MB5174.namprd11.prod.outlook.com ([fe80::4435:90ac:24fe:b6a6%6]) with mapi id 15.20.4608.018; Mon, 18 Oct 2021 01:58:39 +0000 From: "IanX Kuo" To: "devel@edk2.groups.io" , "Wang, Jian J" , Liming Gao CC: "Chan, Amy" , "Ni, Ray" Subject: Re: [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib Thread-Topic: [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on BaseLib Thread-Index: AQHXwt31MCC60/VcqU6bM3dw0E7jcavYAVgg Date: Mon, 18 Oct 2021 01:58:39 +0000 Message-ID: References: <20211016223406.935-1-ianx.kuo@intel.com> <20211016223406.935-2-ianx.kuo@intel.com> In-Reply-To: <20211016223406.935-2-ianx.kuo@intel.com> Accept-Language: en-AS, zh-TW, en-US X-Mentions: jian.j.wang@intel.com,gaoliming@byosoft.com.cn X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: edk2.groups.io; dkim=none (message not signed) header.d=none;edk2.groups.io; dmarc=none action=none header.from=intel.com; x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 20d1aeb0-b19a-474d-3732-08d991dacdd9 x-ms-traffictypediagnostic: PH0PR11MB5110: x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:7219; x-ms-exchange-senderadcheck: 1 x-ms-exchange-antispam-relay: 0 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: +33eOItVEhj4TwqMbx8Jpv+aXbNMkdYCU5PnFthd+BtnigYYr/qvP927TwiumR42c/6EgaAjf5cnuIB8Q+W/IJFbIalg7tX1GDINwCqS17qkJawhcwTGhGmi6FP8kz/AkGx7wxs0k4g1hpscuU5489oYeueWOUUfIswpYpLAowtjagFqlepUp9Pt33PJvhbpjKllFCEq5Vcr+g5XD6JfcG8teHoH4HmVoCCRZFfLH11miurYCOEK0Ky3AYFIXpg/x9LRSIXKnkIpzXdtgqMJWmj4z1xU0jAisGuyB3Ld/nIsjFjUzvxVVKNl6W9nM4vj4BIzvUVuELibDH22tgTntXGclb/QG0c5pxku/2alkaqUyQhGgX3Z5b1OI1noyvVGGdpOzETAin+Eyk8F9B/e2ZjLVNI2YU7e+HTSkXWQ+dotX5r7EYDvFVBJpuUx0nQ8L/neeFQI0bPLo9CEBy2frcKxSjZT9e+hBGKVPpEIBsTSRm5XL2gLeOJpr+2r7bb0O9sZBjzqmOOkgOSutkd3/iEssJ6F+1n33I2aoMCdZ3A6rVy0AZzCXcqbEbSiUcoYU4NH6nLCTObpSPu5FTnxzRVZvGHFXbE6peAyi1bpZSjfA0eBpNDWntj3uh1USZJKiLnGJ+LjXG5ewk48uSw1bAe300t64NSm+wiEJ1/o5lO3Yy3+6LRJEN5PCXTRgFL/F3HfekiPwWqfrjDybfLvL1xng7yvPxNwbDF6dZ3/AA5+VqQtoqZPuvryzwoB4mjd4zn8QAkVRSmy8wwd9fkBWHR7lrTE+PCl67Kuaq9JjeA= x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:PH0PR11MB5174.namprd11.prod.outlook.com;PTR:;CAT:NONE;SFS:(366004)(2906002)(38070700005)(66946007)(66556008)(66446008)(33656002)(64756008)(52536014)(966005)(54906003)(110136005)(82960400001)(316002)(5660300002)(4326008)(7696005)(107886003)(76116006)(83380400001)(53546011)(86362001)(8936002)(38100700002)(6506007)(26005)(71200400001)(55016002)(8676002)(508600001)(186003)(9686003)(66476007)(122000001);DIR:OUT;SFP:1102; x-ms-exchange-antispam-messagedata-chunkcount: 1 x-ms-exchange-antispam-messagedata-0: =?us-ascii?Q?ikIbGojFFPpmSYqmRM9QDRJaizVCXeCPbKkJsX5utx0WgS3IAq4VydIQjgFw?= =?us-ascii?Q?4aFeI+0iNTSGYV+a/AuSjNoAlHsIustUfKGwvKtreQKbIc7w83VPrbcokyfR?= =?us-ascii?Q?KdvZM00KL6B0Gzrnr8wvz0IM9Lymkrl+enbOYFNT9ITKThmytlW+RTnG0zxr?= =?us-ascii?Q?N6cHgzhGg878IddHwVFXFExJ32++gsyM4Evsu9oNjD711gpwyABRiK/1Veqq?= =?us-ascii?Q?umSd/SjBtw37jqCySF3OPEyjalK+126rRVegDPDDi9C3pxZje/XU9lY1F0st?= =?us-ascii?Q?DtvdcBj8sL0mOfqa2hL7L38+YjhKaqy4C7fcwiY2Ar6lyClwlZOvnbZbPvuN?= =?us-ascii?Q?zAG5BoWODhQBgT3x/5TQT4Uts/WlomsDV7XXRIjVJF6IpqilwdOjOvIQwfyA?= =?us-ascii?Q?e9H+cCzUGQTPjf1I793Z68YmMuBIg9EPemvgcsiXkBLoqAsvxU5w+zbQWYiT?= =?us-ascii?Q?UJJi35i1c+qud9urhImtWRoKrWh9Ar45Fvef39L3QIWEce0FqfsGkNAutIcz?= =?us-ascii?Q?3LcAQygEWIQaYf/fgwn7YNyoMqmuGLqPql+daDdClB7Jki/HQs4YEBGjJP6o?= =?us-ascii?Q?HLrrA8enis/acEld+25VtGNo5Bd3D85978J8oUovgw2cZpKUgDrIdu3rhvAw?= =?us-ascii?Q?8ZnCtZhg0MHt84/67rAKVHJZE+SsBiBc91swjmJt8RnmkDYSYcbOd7J6QUge?= =?us-ascii?Q?G4GI/QOXocD+DAAH/zgqAL4FoPSmMHGRQxqTL7xo4hfiJ6H/TvpkrPZNOGTo?= =?us-ascii?Q?RyQl+pAGu1IgTq48gbRu2FwilUuuq65IU4ZwrntgIB2ZDAwveHR9z48qX1QT?= =?us-ascii?Q?+XFyZuukOogKqxmkSzi3vBKJwtxScdH1nWXvLGRZ3tR+dllOaOzBoMGRtTeX?= =?us-ascii?Q?RMdOCsUBtiC5ahDOsC5jCLWDtgjXVtIrXjp+36GupQGUzssiB2/ToqFSKRNM?= =?us-ascii?Q?mtGetkmbpOFwdLYG73tzc/pWDoB5PIqTS7XZInbvBT3+PI2wFqLy3R2883NT?= =?us-ascii?Q?cAm4ZGo6lSJqAvr5+/kG4FXvOQo9Z3Q0ONsEEIolpHkqQLC04d8YpwVQAdgZ?= =?us-ascii?Q?D5vXMV4LTvcq6SZafJK7oz1YU3SxNjHP5V53OocKW2MrhUMUFuydSCgKNqTF?= =?us-ascii?Q?4p9pN8wsztALtpU2JTP7ydnOb8PAFKinJpYtJQHns/WO2r59/b39RfYEjrNN?= =?us-ascii?Q?1j9mU+RMZpSxajoXKrE+eP6lUvOavq/v7IyZkFybXO1Qo0qKU6twrJ+nn/P4?= =?us-ascii?Q?n47bpw/pscsBnglLt8OwJdf8KADmanwSHwr1/6BqrOgo1GLj3mxwp0+RpE8/?= =?us-ascii?Q?JFXMk6WKemy1lu2Ye1kr7G2/?= MIME-Version: 1.0 X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: PH0PR11MB5174.namprd11.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 20d1aeb0-b19a-474d-3732-08d991dacdd9 X-MS-Exchange-CrossTenant-originalarrivaltime: 18 Oct 2021 01:58:39.1162 (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: JMZNam1SM8GTc42YsQTH4ZgIjJHDfG8YeE0/xk/WVGNbYWIRy9CNGS8mNsW6+JCURdQUQ5Zqz9jHjOtO/shpSg== X-MS-Exchange-Transport-CrossTenantHeadersStamped: PH0PR11MB5110 Return-Path: ianx.kuo@intel.com X-OriginatorOrg: intel.com Content-Language: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable @Liming Gao or @Wang, Jian J Sorry to bother you. May I get one of your help to review the code change from maintainer side ? Thanks, Ian Kuo -----Original Message----- From: Kuo, IanX =20 Sent: Sunday, October 17, 2021 6:34 AM To: devel@edk2.groups.io Cc: Chan, Amy ; Ni, Ray ; Kuo, IanX <= ianx.kuo@intel.com>; Wang, Jian J ; Liming Gao Subject: [PATCH v3 1/3] MdeModulePkg/SortLib: Add QuickSort function on Bas= eLib From: IanX Kuo REF: https://bugzilla.tianocore.org/show_bug.cgi?id=3D3675 Use QuickSort instead of QuickSortWorker 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(-) 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 Library used for sorting routines. =20 - Copyright (c) 2009 - 2018, Intel Corporation. All rights reserved.
+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
SPDX-License-Identifier: BSD-2-Clause-Patent =20 **/ @@ -13,114 +13,6 @@ #include #include =20 -/** - Worker function for QuickSorting. This function is identical to Perform= QuickSort, - except that is uses the pre-allocated buffer so the in place sorting doe= s not need to - allocate and free buffers constantly. - - Each element must be equal sized. - - if BufferToSort is NULL, then ASSERT. - if CompareFunction is NULL, then ASSERT. - if Buffer 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) ele= ments - on return a buffer of sorted elements - @param[in] Count the number of elements in the buffer to s= ort - @param[in] ElementSize Size of an element in bytes - @param[in] CompareFunction The function to call to perform the compa= rison - of any 2 elements - @param[in] Buffer Buffer of size ElementSize for use in swa= pping -**/ -VOID -EFIAPI -QuickSortWorker ( - IN OUT VOID *BufferToSort, - IN CONST UINTN Count, - IN CONST UINTN ElementSize, - IN SORT_COMPARE CompareFunction, - IN VOID *Buffer - ) -{ - VOID *Pivot; - UINTN LoopCount; - UINTN NextSwapLocation; - - ASSERT(BufferToSort !=3D NULL); - ASSERT(CompareFunction !=3D NULL); - ASSERT(Buffer !=3D NULL); - - if ( Count < 2 - || ElementSize < 1 - ){ - return; - } - - NextSwapLocation =3D 0; - - // - // pick a pivot (we choose last element) - // - Pivot =3D ((UINT8*)BufferToSort+((Count-1)*ElementSize)); - - // - // Now get the pivot such that all on "left" are below it - // and everything "right" are above it - // - for ( LoopCount =3D 0 - ; LoopCount < Count -1 - ; LoopCount++ - ){ - // - // if the element is less than the pivot - // - if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementS= ize)),Pivot) <=3D 0){ - // - // swap - // - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize)= , ElementSize); - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8= *)BufferToSort+((LoopCount)*ElementSize), ElementSize); - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, Ele= mentSize); - - // - // increment NextSwapLocation - // - NextSwapLocation++; - } - } - // - // swap pivot to it's final position (NextSwapLocaiton) - // - CopyMem (Buffer, Pivot, ElementSize); - CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Ele= mentSize); - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, El= ementSize); - - // - // Now recurse on 2 paritial lists. neither of these will have the 'piv= ot' element - // IE list is sorted left half, pivot element, sorted right half... - // - if (NextSwapLocation >=3D 2) { - QuickSortWorker( - BufferToSort, - NextSwapLocation, - ElementSize, - CompareFunction, - Buffer); - } - - if ((Count - NextSwapLocation - 1) >=3D 2) { - QuickSortWorker( - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize, - Count - NextSwapLocation - 1, - ElementSize, - CompareFunction, - Buffer); - } - return; -} /** Function to perform a Quick Sort alogrithm on a buffer of comparable ele= ments. =20 @@ -156,12 +48,13 @@ PerformQuickSort ( Buffer =3D AllocateZeroPool(ElementSize); ASSERT(Buffer !=3D NULL); =20 - QuickSortWorker( + QuickSort ( BufferToSort, Count, ElementSize, CompareFunction, - Buffer); + Buffer + ); =20 FreePool(Buffer); return; 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 Library used for sorting routines. =20 - Copyright (c) 2009 - 2014, Intel Corporation. All rights reserved.
+ Copyright (c) 2009 - 2021, Intel Corporation. All rights reserved.
SPDX-License-Identifier: BSD-2-Clause-Patent =20 **/ @@ -29,115 +29,6 @@ STATIC EFI_UNICODE_COLLATION_PROTOCOL *mUnicodeCollat= ion =3D NULL; } \ } =20 -/** - Worker function for QuickSorting. This function is identical to Perform= QuickSort, - except that is uses the pre-allocated buffer so the in place sorting doe= s not need to - allocate and free buffers constantly. - - Each element must be equal sized. - - if BufferToSort is NULL, then ASSERT. - if CompareFunction is NULL, then ASSERT. - if Buffer 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) ele= ments - on return a buffer of sorted elements - @param[in] Count the number of elements in the buffer to s= ort - @param[in] ElementSize Size of an element in bytes - @param[in] CompareFunction The function to call to perform the compa= rison - of any 2 elements - @param[in] Buffer Buffer of size ElementSize for use in swa= pping -**/ -VOID -EFIAPI -QuickSortWorker ( - IN OUT VOID *BufferToSort, - IN CONST UINTN Count, - IN CONST UINTN ElementSize, - IN SORT_COMPARE CompareFunction, - IN VOID *Buffer - ) -{ - VOID *Pivot; - UINTN LoopCount; - UINTN NextSwapLocation; - - ASSERT(BufferToSort !=3D NULL); - ASSERT(CompareFunction !=3D NULL); - ASSERT(Buffer !=3D NULL); - - if ( Count < 2 - || ElementSize < 1 - ){ - return; - } - - NextSwapLocation =3D 0; - - // - // pick a pivot (we choose last element) - // - Pivot =3D ((UINT8*)BufferToSort+((Count-1)*ElementSize)); - - // - // Now get the pivot such that all on "left" are below it - // and everything "right" are above it - // - for ( LoopCount =3D 0 - ; LoopCount < Count -1 - ; LoopCount++ - ){ - // - // if the element is less than the pivot - // - if (CompareFunction((VOID*)((UINT8*)BufferToSort+((LoopCount)*ElementS= ize)),Pivot) <=3D 0){ - // - // swap - // - CopyMem (Buffer, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize)= , ElementSize); - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), (UINT8= *)BufferToSort+((LoopCount)*ElementSize), ElementSize); - CopyMem ((UINT8*)BufferToSort+((LoopCount)*ElementSize), Buffer, Ele= mentSize); - - // - // increment NextSwapLocation - // - NextSwapLocation++; - } - } - // - // swap pivot to it's final position (NextSwapLocaiton) - // - CopyMem (Buffer, Pivot, ElementSize); - CopyMem (Pivot, (UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Ele= mentSize); - CopyMem ((UINT8*)BufferToSort+(NextSwapLocation*ElementSize), Buffer, El= ementSize); - - // - // Now recurse on 2 paritial lists. neither of these will have the 'piv= ot' element - // IE list is sorted left half, pivot element, sorted right half... - // - if (NextSwapLocation >=3D 2) { - QuickSortWorker( - BufferToSort, - NextSwapLocation, - ElementSize, - CompareFunction, - Buffer); - } - - if ((Count - NextSwapLocation - 1) >=3D 2) { - QuickSortWorker( - (UINT8 *)BufferToSort + (NextSwapLocation+1) * ElementSize, - Count - NextSwapLocation - 1, - ElementSize, - CompareFunction, - Buffer); - } - - return; -} /** Function to perform a Quick Sort alogrithm on a buffer of comparable ele= ments. =20 @@ -173,12 +64,13 @@ PerformQuickSort ( Buffer =3D AllocateZeroPool(ElementSize); ASSERT(Buffer !=3D NULL); =20 - QuickSortWorker( + QuickSort ( BufferToSort, Count, ElementSize, CompareFunction, - Buffer); + Buffer + ); =20 FreePool(Buffer); return; --=20 2.30.0.windows.1