From 6893c4c5532de1d3798f8605079340df1bcbd59b Mon Sep 17 00:00:00 2001 From: Jan Janssen Date: Wed, 5 Jan 2022 10:33:00 +0100 Subject: [PATCH] boot: Switch to insertion sort We can do a little better than bubble sort without ramping up the code complexity. --- src/boot/efi/boot.c | 8 +------- src/boot/efi/util.c | 20 ++++++++------------ 2 files changed, 9 insertions(+), 19 deletions(-) diff --git a/src/boot/efi/boot.c b/src/boot/efi/boot.c index fac31abc44b..b8779c8b28a 100644 --- a/src/boot/efi/boot.c +++ b/src/boot/efi/boot.c @@ -1644,12 +1644,6 @@ static INTN config_entry_compare(const ConfigEntry *a, const ConfigEntry *b) { return 0; } -static void config_sort_entries(Config *config) { - assert(config); - - sort_pointer_array((void**) config->entries, config->entry_count, (compare_pointer_func_t) config_entry_compare); -} - static UINTN config_entry_find(Config *config, const CHAR16 *needle) { assert(config); @@ -2345,7 +2339,7 @@ static void config_load_all_entries( config_load_xbootldr(config, loaded_image->DeviceHandle); /* sort entries after version number */ - config_sort_entries(config); + sort_pointer_array((void **) config->entries, config->entry_count, (compare_pointer_func_t) config_entry_compare); /* if we find some well-known loaders, add them to the end of the list */ config_entry_add_osx(config); diff --git a/src/boot/efi/util.c b/src/boot/efi/util.c index ab47e108989..ab21d774a25 100644 --- a/src/boot/efi/util.c +++ b/src/boot/efi/util.c @@ -529,21 +529,17 @@ void sort_pointer_array( return; for (UINTN i = 1; i < n_members; i++) { - BOOLEAN more = FALSE; + UINTN k; + void *entry = array[i]; - for (UINTN k = 0; k < n_members - i; k++) { - void *entry; + for (k = i; k > 0; k--) { + if (compare(array[k - 1], entry) <= 0) + break; - if (compare(array[k], array[k+1]) <= 0) - continue; - - entry = array[k]; - array[k] = array[k+1]; - array[k+1] = entry; - more = TRUE; + array[k] = array[k - 1]; } - if (!more) - break; + + array[k] = entry; } } -- 2.47.3