Messages in this thread Patch in this message | | | From | Rasmus Villemoes <> | Subject | [PATCH 2/3] staging: greybus: loopback.c: do insertion in O(n) instead of O(n lg n) | Date | Fri, 5 Oct 2018 16:28:25 +0200 |
| |
"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
| |