From 704153c34cb845569104beba5e78e370aa737229 Mon Sep 17 00:00:00 2001
From: Igor Kushnir <igorkuo@gmail.com>
Date: Wed, 13 May 2015 20:58:04 +0300
Subject: [PATCH 1/1] Optimized sorting wallpapers.

---
 src/xfce-backdrop.c | 55 +++++++++++++++++++++++++----------------------------
 1 file changed, 26 insertions(+), 29 deletions(-)

diff --git a/src/xfce-backdrop.c b/src/xfce-backdrop.c
index b9dd798..cb1ae79 100644
--- a/src/xfce-backdrop.c
+++ b/src/xfce-backdrop.c
@@ -270,8 +270,7 @@ xfdesktop_backdrop_clear_directory_monitor(XfceBackdrop *backdrop)
 }
 
 /* we compare by the collate key so the image listing is the same as how
- * xfdesktop-settings displays the images. The symantics between glist
- * sorting and qsort require two functions */
+ * xfdesktop-settings displays the images */
 static gint
 glist_compare_by_collate_key(const gchar *a, const gchar *b)
 {
@@ -287,22 +286,18 @@ glist_compare_by_collate_key(const gchar *a, const gchar *b)
     return ret;
 }
 
-/* we compare by the collate key so the image listing is the same as how
- * xfdesktop-settings displays the images. The symantics between glist
- * sorting and qsort require two functions */
-static int
-qsort_compare_by_collate_key(const void *a, const void *b)
+typedef struct
 {
-    gint ret;
-    gchar *a_key = g_utf8_collate_key_for_filename(* (char * const *)a, -1);
-    gchar *b_key = g_utf8_collate_key_for_filename(* (char * const *)b, -1);
-
-    ret = g_strcmp0(a_key, b_key);
-
-    g_free(a_key);
-    g_free(b_key);
+    gchar *key;
+    gchar *string;
+} KeyStringPair;
 
-    return ret;
+static int
+qsort_compare_pair_by_key(const void *a, const void *b)
+{
+    const gchar *a_key = ((const KeyStringPair *)a)->key;
+    const gchar *b_key = ((const KeyStringPair *)b)->key;
+    return g_strcmp0(a_key, b_key);
 }
 
 static void
@@ -396,33 +391,35 @@ cb_xfce_backdrop_image_files_changed(GFileMonitor     *monitor,
     }
 }
 
-/* Equivalent to, but faster than
- * g_list_sort(list, (GCompareFunc)compare_by_collate_key) */
+/* Equivalent to (except for not being a stable sort), but faster than
+ * g_list_sort(list, (GCompareFunc)glist_compare_by_collate_key) */
 static GList *
 sort_image_list(GList *list, guint list_size)
 {
-    gchar **array;
+    KeyStringPair *array;
     guint i;
     GList *l;
 
     TRACE("entering");
 
     g_assert(g_list_length(list) == list_size);
-    /* Create an array of the same size as list */
+    /* Allocate an array of the same size as list */
     array = g_malloc(list_size * sizeof(array[0]));
 
-    /* Copy list contents to the array */
-    for(l = list, i = 0; l; l = l->next, ++i)
-        array[i] = l->data;
+    /* Copy list contents to the array and generate collation keys */
+    for(l = list, i = 0; l; l = l->next, ++i) {
+        array[i].string = l->data;
+        array[i].key = g_utf8_collate_key_for_filename(array[i].string, -1);
+    }
 
     /* Sort the array */
-    qsort(array, list_size, sizeof(array[0]),
-          qsort_compare_by_collate_key);
-
+    qsort(array, list_size, sizeof(array[0]), qsort_compare_pair_by_key);
 
-    /* Copy sorted array back to the list */
-    for(l = list, i = 0; l; l = l->next, ++i)
-        l->data = array[i];
+    /* Copy sorted array back to the list and deallocate the collation keys */
+    for(l = list, i = 0; l; l = l->next, ++i) {
+        l->data = array[i].string;
+        g_free(array[i].key);
+    }
 
     g_free(array);
 
-- 
2.3.7