From nobody Sat Feb 7 20:58:17 2026 Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com [209.85.214.170]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id AABBF33D6F9 for ; Sun, 1 Feb 2026 13:03:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.214.170 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769951037; cv=none; b=JvwfN0RnkCt62skmohGikc2Ke2qHjLeQwC10vY61paVaniQjgVfKRdql50dKjH96XoQiLrL1wanqQuAdPZn+agi2OlWx8KbClQEhwEweqqVVzrn85+QUnMZVVWb/cQSrxIOP4krPOrjQIgGdkwgXTY1iAE++qCbY+jYzYLS1ohk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1769951037; c=relaxed/simple; bh=jkJFaSw+4QB88At9pISwIN/7R4HhlxcEMlc2qyYUNjo=; h=From:To:Cc:Subject:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=Mz3/V1kt62ZFR8qaRzWADBVTUPS+ExQyCkkWOQ10ISYaa5k78B6Mk1JvUSFwe77WJWNNegiGVZVpvGx5D9eB0/Cx0/h562P7cKCAdCKqDPw26SlPD7df1DkGaZcMtTHjes+5XXAV20PctE9QthofbQPUUDVJrjIO2AUmx4e1vrw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com; spf=pass smtp.mailfrom=gmail.com; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b=bfD/in+C; arc=none smtp.client-ip=209.85.214.170 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=gmail.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.b="bfD/in+C" Received: by mail-pl1-f170.google.com with SMTP id d9443c01a7336-29f2676bb21so33131715ad.0 for ; Sun, 01 Feb 2026 05:03:49 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1769951027; x=1770555827; darn=vger.kernel.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=zpTdJ6kU9128Bplq2Lsam/HvuOJViBWd2y7vXvIt9P8=; b=bfD/in+CcQ6LU7k70toJqin7m6NIf00XTdyWIjzRcg5sWKYuEyO4QUqt6vc3KNFaA/ nTT0KxrD/+RawiKEy3+WHxiedOLspzhyMX7vxEi6FGN79O8CwCB31Gq7A8FxqdTFfaBW x3Iq4VFQ9pfEy1dZG7TyQFl2qHjW3lctux8YINlMYyLmQsefM9VQV70pzQgOMzk7Ub9Z ws438n67DWrmBC8z2/2zvOwPkrYbrP14ULorDhoA5XBoRNzEq1id/RnaHXXq3ZpgTBVF CkroBdNJmcfItuGUMpS9YTMc96gZAcjhCGR+VA/lubuOUM9rcb6XFv3mSWgCYh3FUf2y Ux8A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1769951027; x=1770555827; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-gg:x-gm-message-state:from :to:cc:subject:date:message-id:reply-to; bh=zpTdJ6kU9128Bplq2Lsam/HvuOJViBWd2y7vXvIt9P8=; b=aWwKT35P5kHMZbKzasNy/HSnIz9tId2AplcEww9O5OCgBbs4VagBKyi1LmgYPK2hvC qskW0++JdDomurmBSd4hL411k8IV2fmKVIHw3mnykTe6vQA/Kb6oiIuK0mmAeqCDqKpu OgNFACJLJJzHdE5naQYTINxLyYTctCuPKIO1FaB+zJFuOYG7kpO+eCkskMjv10vi3aQs lSrPVnZXVNlDm4G9Z7bNPounc33OhM09T+XMHCPnB39WQZvRKhCmS4qr43QIVc3eEqUF Yp6LLDgkiAkitKKwx5W7nN6hAQ11f1M5IQZEAqtXGRUGBh5JmOuB8s9HiYh9fmJMzrQH zj9A== X-Forwarded-Encrypted: i=1; AJvYcCURHQOLw2gurTu7eZBxYrJUoti4lyGQdhcwVQZ9dMirkURUFggnmivDryCI4dvI1OiwDzT6rHykErHT1og=@vger.kernel.org X-Gm-Message-State: AOJu0YywfwTXh67SomwL7rRSzXLa7LOiqjoCZl6doiwtuqkXuAnOpA+e kILILq0wuiwDegF5Ur/RzP8gCY9sNcwPp+oNgen9cB0Q7djaIxSiz/sj X-Gm-Gg: AZuq6aI6Q3gJdYiNE3YtQWGcNYULd8HfhyLZC6f5AfdASFFPF5+P5/d9Gwn9iMavc5L YdAfDxvhAhqBo6b3hSorenOtIp1rhisl59xPRlIe6hWlSICn5iDrL4xaPAx+mbU6zEZTvrPlWOM rt+BMdO5xhwdo5tO9TABosE6CcKrzJ/WkPf/hl5SpHc+nRpKfxAg/PyFvb03ZfITt+tcqUN0rVs C3pBbpFnRZBxElYKMHTpquikPj7PK1lLvidya5K6IWKkMU2eHcN7Pp2QRfad5fzYoVKG3xIQJkb aiyRFR4j7PIeLgSDO+1G/lol4nE7IUmz7sGe5xEO7846PGobbkByTa+ngHbYvGu+RWmkTTYEykK uvqil0aSkINIObmkigs7hhUpj7R5vjhjaVhkjaF7KxvgvO9jNsffRx+RXwkRvDN4O8A2QDfyyNs iIeGpggVBSAOGHXQIPehQb+IY8JhV4LhXn9DMmRVIYZ2tbR2x2sc3hZhe4Uu//wK96svwu0FnEb 9IYReAdJA== X-Received: by 2002:a17:902:cf10:b0:29d:65ed:f481 with SMTP id d9443c01a7336-2a8d8946eabmr94972755ad.0.1769951027197; Sun, 01 Feb 2026 05:03:47 -0800 (PST) Received: from nickhuang.. (2001-b400-e28b-f958-90c5-2a29-7d9f-5524.emome-ip6.hinet.net. [2001:b400:e28b:f958:90c5:2a29:7d9f:5524]) by smtp.gmail.com with ESMTPSA id d9443c01a7336-2a8bd74e9bbsm96831045ad.95.2026.02.01.05.03.44 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sun, 01 Feb 2026 05:03:46 -0800 (PST) From: Nick Huang To: "Rafael J . Wysocki" , Robert Moore Cc: Len Brown , linux-acpi@vger.kernel.org, acpica-devel@lists.linux.dev, linux-kernel@vger.kernel.org, paladin@ntub.edu.tw, kusogame68@gmail.com, ceyanglab@gmail.com, n1136402@ntub.edu.tw, Nick Huang Subject: [PATCH 1/2] =?UTF-8?q?ACPI:=20nsrepair2:=20Replace=20O(n=C2=B2)?= =?UTF-8?q?=20bubble=20sort=20with=20O(n=20log=20n)=20sort=5Fr()?= Date: Sun, 1 Feb 2026 13:03:33 +0000 Message-ID: <20260201130334.3107-2-sef1548@gmail.com> X-Mailer: git-send-email 2.43.0 In-Reply-To: <20260201130334.3107-1-sef1548@gmail.com> References: <20260201130334.3107-1-sef1548@gmail.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Replace the O(n=C2=B2) bubble sort implementation in acpi_ns_sort_list() with the kernel's sort_r() function which uses heapsort, providing O(n log n) time complexity. This improves performance for large ACPI package lists while also reducing code complexity by leveraging the existing kernel sort API. Signed-off-by: Nick Huang --- drivers/acpi/acpica/nsrepair2.c | 87 +++++++++++++++++++++++---------- 1 file changed, 62 insertions(+), 25 deletions(-) diff --git a/drivers/acpi/acpica/nsrepair2.c b/drivers/acpi/acpica/nsrepair= 2.c index 8dbb870f4..a39ef59fe 100644 --- a/drivers/acpi/acpica/nsrepair2.c +++ b/drivers/acpi/acpica/nsrepair2.c @@ -9,6 +9,7 @@ *************************************************************************= ****/ =20 #include +#include #include "accommon.h" #include "acnamesp.h" =20 @@ -84,6 +85,14 @@ acpi_ns_check_sorted_list(struct acpi_evaluate_info *inf= o, static void acpi_ns_remove_element(union acpi_operand_object *obj_desc, u32 index); =20 +/* Context structure for sort comparison function */ +struct acpi_sort_context { + u32 sort_index; + u8 sort_direction; +}; + +static int acpi_ns_sort_cmp(const void *a, const void *b, const void *priv= ); + static void acpi_ns_sort_list(union acpi_operand_object **elements, u32 count, u32 index, u8 sort_direction); @@ -851,6 +860,52 @@ acpi_ns_check_sorted_list(struct acpi_evaluate_info *i= nfo, return (AE_OK); } =20 +/*************************************************************************= ***** + * + * FUNCTION: acpi_ns_sort_cmp + * + * PARAMETERS: a - First element to compare + * b - Second element to compare + * priv - Pointer to sort context (acpi_sort_conte= xt) + * + * RETURN: -1, 0, or 1 depending on sort order + * + * DESCRIPTION: Comparison function for sort_r() API. Compares the integer + * values at the specified index within package elements. + * + *************************************************************************= ****/ + +static int acpi_ns_sort_cmp(const void *a, const void *b, const void *priv) +{ + union acpi_operand_object *obj_a =3D *(union acpi_operand_object **)a; + union acpi_operand_object *obj_b =3D *(union acpi_operand_object **)b; + const struct acpi_sort_context *ctx =3D priv; + union acpi_operand_object *value_a; + union acpi_operand_object *value_b; + u64 a_val; + u64 b_val; + + value_a =3D obj_a->package.elements[ctx->sort_index]; + value_b =3D obj_b->package.elements[ctx->sort_index]; + + a_val =3D value_a->integer.value; + b_val =3D value_b->integer.value; + + if (ctx->sort_direction =3D=3D ACPI_SORT_ASCENDING) { + if (a_val < b_val) + return -1; + if (a_val > b_val) + return 1; + } else { + if (a_val > b_val) + return -1; + if (a_val < b_val) + return 1; + } + + return 0; +} + /*************************************************************************= ***** * * FUNCTION: acpi_ns_sort_list @@ -873,31 +928,13 @@ static void acpi_ns_sort_list(union acpi_operand_object **elements, u32 count, u32 index, u8 sort_direction) { - union acpi_operand_object *obj_desc1; - union acpi_operand_object *obj_desc2; - union acpi_operand_object *temp_obj; - u32 i; - u32 j; - - /* Simple bubble sort */ - - for (i =3D 1; i < count; i++) { - for (j =3D (count - 1); j >=3D i; j--) { - obj_desc1 =3D elements[j - 1]->package.elements[index]; - obj_desc2 =3D elements[j]->package.elements[index]; - - if (((sort_direction =3D=3D ACPI_SORT_ASCENDING) && - (obj_desc1->integer.value > - obj_desc2->integer.value)) - || ((sort_direction =3D=3D ACPI_SORT_DESCENDING) - && (obj_desc1->integer.value < - obj_desc2->integer.value))) { - temp_obj =3D elements[j - 1]; - elements[j - 1] =3D elements[j]; - elements[j] =3D temp_obj; - } - } - } + struct acpi_sort_context ctx; + + ctx.sort_index =3D index; + ctx.sort_direction =3D sort_direction; + + sort_r(elements, count, sizeof(union acpi_operand_object *), + acpi_ns_sort_cmp, NULL, &ctx); } =20 /*************************************************************************= ***** --=20 2.43.0