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

[Mathieu Desnoyers <mathieu.desnoyers@efficios.com>]

The current implementation of the 10_hurd 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 Hurd
  environment could test it before it is merged. ]

Signed-off-by: Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
Cc: Samuel Thibault <samuel.thibault@ens-lyon.org>
---
 util/grub.d/10_hurd.in | 14 +++++++++-----
 1 file changed, 9 insertions(+), 5 deletions(-)

diff --git a/util/grub.d/10_hurd.in b/util/grub.d/10_hurd.in
index 2ab3a97e6..e0f290ae8 100644
--- a/util/grub.d/10_hurd.in
+++ b/util/grub.d/10_hurd.in
@@ -195,11 +195,17 @@ title_correction_code=
 # Extra indentation to add to menu entries in a submenu. We're not in a submenu
 # yet, so it's empty. In a submenu it will be equal to '\t' (one tab).
 submenu_indentation=""
-is_top_level=true
 
-while [ "x$kernels" != "x" ] ; do
-  kernel=`version_find_latest $kernels`
+# Perform a reverse version sort on the entire kernels 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_kernels=$(echo ${kernels} | 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
+
+for kernel in ${reverse_sorted_kernels}; do
   # The GRUB_DISABLE_SUBMENU option used to be different than others since it was
   # mentioned in the documentation that has to be set to 'y' instead of 'true' to
   # enable it. This caused a lot of confusion to users that set the option to 'y',
@@ -219,8 +225,6 @@ while [ "x$kernels" != "x" ] ; do
 
   hurd_entry "$kernel" advanced
   hurd_entry "$kernel" recovery
-
-  kernels=`echo $kernels | tr ' ' '\n' | fgrep -vx "$kernel" | tr '\n' ' '`
 done
 
 # If at least one kernel was found, then we need to
-- 
2.30.2