linux-kernel - [PATCH 2/3] staging: greybus: loopback.c: do insertion in O(n) instead of O(n lg n)

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-Id: <20181005142826.26108-2-linux@rasmusvillemoes.dk>
Date:   Fri,  5 Oct 2018 16:28:25 +0200
From:   Rasmus Villemoes <linux@...musvillemoes.dk>
To:     "Bryan O'Donoghue" <pure.logic@...us-software.ie>,
        Johan Hovold <johan@...nel.org>, Alex Elder <elder@...nel.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>
Cc:     Rasmus Villemoes <linux@...musvillemoes.dk>,
        greybus-dev@...ts.linaro.org, devel@...verdev.osuosl.org,
        linux-kernel@...r.kernel.org
Subject: [PATCH 2/3] staging: greybus: loopback.c: do insertion in O(n) instead of O(n lg n)

"Append to the list and do a merge sort" is not really an insertion
sort. While a few more lines of code, we can keep the list sorted doing
at most n comparisons by iterating until we find the first element
strictly greater than gb.

Signed-off-by: Rasmus Villemoes <linux@...musvillemoes.dk>
---
I have no idea if the performance matters (it probably doesn't). Feel
free to ignore this and the followup cleanup.

 drivers/staging/greybus/loopback.c | 16 +++++++++++++---
 1 file changed, 13 insertions(+), 3 deletions(-)

diff --git a/drivers/staging/greybus/loopback.c b/drivers/staging/greybus/loopback.c
index 7080294f705c..89c3f6fd8ddf 100644
--- a/drivers/staging/greybus/loopback.c
+++ b/drivers/staging/greybus/loopback.c
@@ -1013,9 +1013,19 @@ static int gb_loopback_bus_id_compare(void *priv, struct list_head *lha,
 
 static void gb_loopback_insert_id(struct gb_loopback *gb)
 {
-	/* perform an insertion sort */
-	list_add_tail(&gb->entry, &gb_dev.list);
-	list_sort(NULL, &gb_dev.list, gb_loopback_bus_id_compare);
+	struct gb_loopback *gb_list;
+
+	/*
+	 * Keep the list sorted. Insert gb before the first element it
+	 * compares strictly less than. If no such element exists, the
+	 * loop terminates with &gb_list->entry being &gb_dev.list,
+	 * and we thus insert at the end.
+	 */
+	list_for_each_entry(gb_list, &gb_dev.list, entry) {
+		if (gb_loopback_bus_id_compare(NULL, &gb->entry, &gb_list->entry) < 0)
+			break;
+	}
+	list_add_tail(&gb->entry, &gb_list->entry);
 }
 
 #define DEBUGFS_NAMELEN 32
-- 
2.19.0