lkml.org 
[lkml]   [2018]   [Oct]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
Subject[PATCH 2/3] staging: greybus: loopback.c: do insertion in O(n) instead of O(n lg n)
Date
"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@rasmusvillemoes.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
\
 
 \ /
  Last update: 2018-10-05 16:29    [W:0.318 / U:0.040 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site