[RFC PATCH v3 2/5] grub-mkconfig linux_xen: Fix quadratic algorithm for sorting menu items

[Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>]

The current implementation of the 20_linux_xen script implements its
menu items sorting in bash with a quadratic algorithm, calling "sed",
"sort", "head", and "grep" to compare versions between individual lines,
which is annoyingly slow for kernel developers who can easily end up
with 50-100 kernels in their boot partition.

This fix is ported from the 10_linux script, which has a similar
quadratic code pattern.

[ Note: this is untested. I would be grateful if anyone with a Xen
  environment could test it before it is merged. ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
Cc: xen-devel@xxxxxxxxxxxxxxxxxxxx
---
 util/grub.d/20_linux_xen.in | 18 ++++++++++--------
 1 file changed, 10 insertions(+), 8 deletions(-)

diff --git a/util/grub.d/20_linux_xen.in b/util/grub.d/20_linux_xen.in
index f45559ff8..3178eb430 100644
--- a/util/grub.d/20_linux_xen.in
+++ b/util/grub.d/20_linux_xen.in
@@ -237,11 +237,17 @@ esac
 # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
 submenu_indentation=""
 
+# Perform a reverse version sort on the entire xen_list and linux_list.
+# Temporarily replace the '.old' suffix by ' 1' and append ' 2' for all
+# other files to order the '.old' files after their non-old counterpart
+# in reverse-sorted order.
+
+reverse_sorted_xen_list=$(echo ${xen_list} | tr ' ' '\n' | sed -e 's/\.old$/ 
1/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 's/ 2$//')
+reverse_sorted_linux_list=$(echo ${linux_list} | tr ' ' '\n' | sed -e 
's/\.old$/ 1/' -e '/ 1$/! s/$/ 2/' | version_sort -r | sed -e 's/ 1$/.old/' -e 
's/ 2$//')
+
 is_top_level=true
 
-while [ "x${xen_list}" != "x" ] ; do
-    list="${linux_list}"
-    current_xen=`version_find_latest $xen_list`
+for current_xen in ${reverse_sorted_xen_list}; do
     xen_basename=`basename ${current_xen}`
     xen_dirname=`dirname ${current_xen}`
     rel_xen_dirname=`make_system_path_relative_to_its_root $xen_dirname`
@@ -273,8 +279,7 @@ while [ "x${xen_list}" != "x" ] ; do
        fi
     done
 
-    while [ "x$list" != "x" ] ; do
-       linux=`version_find_latest $list`
+    for linux in ${reverse_sorted_linux_list}; do
        gettext_printf "Found linux image: %s\n" "$linux" >&2
        basename=`basename $linux`
        dirname=`dirname $linux`
@@ -349,13 +354,10 @@ while [ "x${xen_list}" != "x" ] ; do
            linux_entry "${OS}" "${version}" "${xen_version}" recovery \
                "${GRUB_CMDLINE_LINUX_RECOVERY} ${GRUB_CMDLINE_LINUX}" 
"${GRUB_CMDLINE_XEN}"
        fi
-
-       list=`echo $list | tr ' ' '\n' | fgrep -vx "$linux" | tr '\n' ' '`
     done
     if [ x"$is_top_level" != xtrue ]; then
        echo '  }'
     fi
-    xen_list=`echo $xen_list | tr ' ' '\n' | fgrep -vx "$current_xen" | tr 
'\n' ' '`
 done
 
 # If at least one kernel was found, then we need to
-- 
2.30.2