[glib/wip/gdesktopappinfo: 17/20] desktop files: add sort function for searching

[Ryan Lortie <desrt src gnome org>]

commit 799bd603aa86b3ab95a00f07751ce00628bebcae
Author: Ryan Lortie <desrt desrt ca>
Date:   Thu Sep 19 13:06:34 2013 -0400

    desktop files: add sort function for searching
    
    Also, clean up the implementation of searching to make more-conventional
    use of GSList since it ends up being easier in the end.

 gio/gdesktopappinfo.c |  297 +++++++++++++++++++++++++++----------------------
 gio/gdesktopappinfo.h |    5 +-
 2 files changed, 166 insertions(+), 136 deletions(-)
---
diff --git a/gio/gdesktopappinfo.c b/gio/gdesktopappinfo.c
index c61db90..35cce6d 100644
--- a/gio/gdesktopappinfo.c
+++ b/gio/gdesktopappinfo.c
@@ -478,10 +478,10 @@ desktop_file_dir_unindexed_get_all (DesktopFileDir *dir,
 }
 
 static void
-desktop_file_dir_unindexed_search (DesktopFileDir *dir,
-                                   GSList         *categories,
-                                   const gchar    *term,
-                                   gint            max_hits)
+desktop_file_dir_unindexed_search (DesktopFileDir  *dir,
+                                   GSList         **categories,
+                                   const gchar     *term,
+                                   gint             max_hits)
 {
   /* TODO */
 }
@@ -740,110 +740,97 @@ desktop_file_dir_indexed_get_all (DesktopFileDir *dir,
 }
 
 static void
-insert_into_list (GSList      *categories,
-                  const gchar *item,
-                  gint         into_bucket,
-                  gint         max_hits)
+insert_into_list (GSList      **categories,
+                  const gchar  *item,
+                  gint          into_bucket,
+                  gint          max_hits)
 {
-  GSList *before_node;
-  GSList **ptr;
-  gint i = 0;
-
-  if (into_bucket < DESKTOP_KEY_NUM_MATCH_CATEGORIES - 1)
-    before_node = &categories[into_bucket + 1];
-  else
-    before_node = NULL;
+  gint n_hits = 0;
+  gint i;
 
-  for (ptr = &categories; *ptr != before_node; ptr = &(*ptr)->next)
+  for (i = 0; i <= into_bucket; i++)
     {
-      GSList *node = *ptr;
+      GSList *node;
+
+      /* If we have enough hits from previous categories, stop.
+       *
+       * Note.  This check will not be applied after counting up the
+       * hits in categories[into_bucket] and that's intentional: we
+       * don't want to toss out our new item if it has the same score as
+       * items we're already returning.
+       *
+       * That might mean that we get more than max_hits items, but
+       * that's the desired behaviour.
+       */
+      if (max_hits >= 0 && n_hits >= max_hits)
+        return;
 
-      if (node->data)
+      /* We want to do the dup-checking in all cases, though */
+      for (node = categories[i]; node; node = node->next)
         {
-          /* This item is already in the list, at higher priority.
-           *
-           * Note; pointer compare works for two reasons:
-           *
-           *  - within a given index, a string only appears once
-           *
-           *  - we use masking to prevent seeing the same application
-           *    from multiple different directories
+          /* Pointer comparison is good enough because we're using the
+           * name from the desktop index (where it is unique) and
+           * because we'll never see the same desktop file name across
+           * multiple indexes due to our use of masking.
            */
           if (node->data == item)
             return;
 
-          g_assert_cmpstr (node->data, !=, item);
-
-          /* Some other item.  Count it. */
-          i++;
+          n_hits++;
         }
-
-      /* We already have enough higher-ranking hits */
-      if (i == max_hits)
-        return;
     }
 
-  /* Add and count ourselves... */
-  *ptr = g_slist_prepend (*ptr, (gchar *) item);
-  ptr = &(*ptr)->next;
-  i++;
+  /* No duplicate found at this level or any before, and not too many
+   * items in earlier buckets, so add our item.
+   */
+  categories[into_bucket] = g_slist_prepend (categories[into_bucket], (gchar *) item);
+  n_hits++;
 
-  /* We may have to remove an item now:
+  /* We may need to remove ourselves from a later category if we already
+   * had a weaker hit for this item.
    *
-   *  - if the item we inserted already comes later in the list, we must
-   *    remove that one
-   *
-   *  - if we went over max_hits, we need to remove some other item
-   *
-   * This loop will skip past non-duplicates until we hit the maximum
-   * number of items (in which case the next item, duplicate-or-not will
-   * be the one we remove).
+   * We may also need to blow away an entire category if n_hits is big
+   * enough.
    */
-  while (i != max_hits)
+  for (i = into_bucket + 1; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
     {
-      GSList *node = *ptr;
-
-      /* End of list before we had enough hits */
-      if (node == NULL)
-        return;
+      if (!categories[i])
+        continue;
 
-      if (node->data == item)
+      if (max_hits >= 0 && n_hits >= max_hits)
         {
-          /* A later version of ourselves.  Remove it. */
-          *ptr = g_slist_delete_link (node, node);
-
-          /* We added one item and removed one item, so we definitely
-           * didn't grow the list past the max.  We can stop now.
-           */
-          return;
+          g_slist_free (categories[i]);
+          categories[i] = NULL;
         }
-
-      if (node->data)
-        i++;
-
-      ptr = &node->next;
-    }
-
-  /* Now we delete the first item we find (if there is one) */
-  while (*ptr)
-    {
-      GSList *node = *ptr;
-
-      if (node->data)
+      else
         {
-          *ptr = g_slist_delete_link (node, node);
-          return;
+          GSList **ptr;
+
+          for (ptr = &categories[i]; *ptr; ptr = &(*ptr)->next)
+            if ((*ptr)->data == item)
+              {
+                /* Found us! */
+                *ptr = g_slist_delete_link (*ptr, *ptr);
+                n_hits--;
+
+                /* Since we effectively didn't add any items this time
+                 * around, we know we will not need to blow away later
+                 * categories.  We also know that we will not appear in
+                 * a later category, since we appeared here.
+                 *
+                 * So, we're done.
+                 */
+                return;
+              }
         }
-
-      ptr = &(*ptr)->next;
     }
 }
 
 static void
-desktop_file_dir_indexed_search (DesktopFileDir *dir,
-                                 GSList         *categories,
-                                 const gchar    *term,
-                                 gint            max_hits)
+desktop_file_dir_indexed_search (DesktopFileDir  *dir,
+                                 GSList         **categories,
+                                 const gchar     *term,
+                                 gint             max_hits)
 {
   const struct dfi_pointer_array *text_indexes;
   const struct dfi_string_list *app_names;
@@ -1081,10 +1068,10 @@ desktop_file_dir_get_all (DesktopFileDir *dir,
  * Finds the names of applications in @dir that match @term.
  */
 static void
-desktop_file_dir_search (DesktopFileDir *dir,
-                         GSList         *categories,
-                         const gchar    *term,
-                         gint            max_hits)
+desktop_file_dir_search (DesktopFileDir  *dir,
+                         GSList         **categories,
+                         const gchar     *term,
+                         gint             max_hits)
 {
   if (dir->dfi)
     desktop_file_dir_indexed_search (dir, categories, term, max_hits);
@@ -3758,21 +3745,28 @@ g_app_info_get_default_for_uri_scheme (const char *uri_scheme)
 
 /* "Get all" API {{{2 */
 
+/**
+ * g_desktop_app_info_search:
+ * @token: the search token
+ * @sort_by: (scope call): a string sorting function
+ * @user_data: (closure sort_by): user_data for @sort_by
+ * @max_hits: the maximum number of hits, or -1
+ *
+ * Searches desktop files for ones that match @token.
+ *
+ * @token must be a casefolded single word.
+ *
+ * Returns: (transfer full): the names of desktop files that match
+ */
 gchar **
-g_desktop_app_info_search (const char *token,
-                           gint        max_hits)
+g_desktop_app_info_search (const char             *token,
+                           GStringCompareDataFunc  sort_by,
+                           gpointer                user_data,
+                           gint                    max_hits)
 {
-  GSList categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES];
-  GSList *node;
+  GSList *categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES] = { NULL, };
   gchar **results;
-  gint i, n;
-
-  for (i = 0; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
-    {
-      categories[i].next = &categories[i + 1];
-      categories[i].data = NULL;
-    }
-  categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES - 1].next = NULL;
+  gint i, j, n;
 
   desktop_file_dirs_lock ();
 
@@ -3782,45 +3776,77 @@ g_desktop_app_info_search (const char *token,
   /* Must hold lock while processing results because otherwise strings
    * could go missing out from under us.
    */
-  node = &categories[0];
-  n = g_slist_length (categories) - DESKTOP_KEY_NUM_MATCH_CATEGORIES;
+  n = 0;
+  for (i = 0; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
+    {
+      if (sort_by)
+        categories[i] = g_slist_sort_with_data (categories[i], (GCompareDataFunc) sort_by, user_data);
+
+      n += g_slist_length (categories[i]);
+
+      if (max_hits >= 0 && n >= max_hits)
+        {
+          n = max_hits;
+          break;
+        }
+    }
+
   results = g_new (gchar *, n + 1);
-  i = 0;
-  while (node)
+  j = 0; /* j used to fill 'results' */
+
+  for (i = 0; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
     {
-      GSList *next = node->next;
+      GSList *node = categories[i];
 
-      if (node->data)
+      while (node && j < n)
         {
-          results[i++] = g_strdup (node->data);
+          GSList *next = node->next;
+
+          results[j++] = g_strdup (node->data);
           g_slist_free_1 (node);
+          node = next;
         }
 
-      node = next;
+      /* Clean up any leftovers */
+      g_slist_free (node);
     }
 
-  g_assert_cmpint (i, ==, n);
-  results[i] = NULL;
+  g_assert_cmpint (j, ==, n);
+  results[j] = NULL;
 
   desktop_file_dirs_unlock ();
 
   return results;
 }
 
+/**
+ * g_desktop_app_info_search_full: (skip)
+ * @token: the token to search for
+ * @max_hits: the approximate maximum number of hits to return, or -1
+ *
+ * Searches desktop files for ones that match @token.
+ *
+ * @token must be a casefolded single word.
+ *
+ * The return value is an array of strvs.  Each strv contains a list of
+ * applications that matched @token with an equal score.  The outer list
+ * is sorted by score so that the first strv contains the best-matching
+ * applications, and so on.
+ *
+ * This function will either return all items that matched with the same
+ * score, or none of them.  It is therefore possible that more than
+ * @max_hits items will be returned.
+ *
+ * Returns: a list of strvs.  Free each item with g_strfreev() and free
+ *   the outer list with g_free().
+ */
 gchar ***
 g_desktop_app_info_search_full (const gchar *token,
                                 gint         max_hits)
 {
-  GSList categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES];
+  GSList *categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES] = { NULL, };
   gchar ***results;
-  gint i, j;
-
-  for (i = 0; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
-    {
-      categories[i].next = &categories[i + 1];
-      categories[i].data = NULL;
-    }
-  categories[DESKTOP_KEY_NUM_MATCH_CATEGORIES - 1].next = NULL;
+  gint i, k;
 
   desktop_file_dirs_lock ();
 
@@ -3829,30 +3855,31 @@ g_desktop_app_info_search_full (const gchar *token,
 
   /* As above, must hold the lock. */
   results = g_new (gchar **, DESKTOP_KEY_NUM_MATCH_CATEGORIES + 1);
-  j = 0;
+  k = 0; /* Used to fill 'results' */
 
+  /* Convert each 'category' into a strv and store in 'results' */
   for (i = 0; i < DESKTOP_KEY_NUM_MATCH_CATEGORIES; i++)
     {
-      gchar **list;
-      GSList *node;
-      gint n;
+      gint length = g_slist_length (categories[i]);
 
-      n = 0;
-      for (node = categories[i].next; node && node->data; node = node->next)
-        n++;
-
-      if (n == 0)
-        continue;
+      /* Don't bother storing empty sublists */
+      if (length > 0)
+        {
+          GSList *node;
+          gint j;
 
-      list = g_new (gchar *, n + 1);
-      n = 0;
-      for (node = categories[i].next; node && node->data; node = node->next)
-        list[n++] = g_strdup (node->data);
-      list[n] = NULL;
+          results[k] = g_new (gchar *, length + 1);
 
-      results[j++] = list;
+          j = 0;
+          for (node = categories[i]; node; node = node->next)
+            results[k][j++] = g_strdup (node->data);
+          g_assert_cmpint (j, ==, length);
+          results[k][j] = NULL;
+          k++;
+        }
     }
-  results[j] = NULL;
+  g_assert_cmpint (k, <=, DESKTOP_KEY_NUM_MATCH_CATEGORIES);
+  results[k] = NULL;
 
   desktop_file_dirs_unlock ();
 
diff --git a/gio/gdesktopappinfo.h b/gio/gdesktopappinfo.h
index 749dfb1..69cc810 100644
--- a/gio/gdesktopappinfo.h
+++ b/gio/gdesktopappinfo.h
@@ -166,7 +166,10 @@ gboolean    g_desktop_app_info_launch_uris_as_manager (GDesktopAppInfo
 
 
 GLIB_AVAILABLE_IN_2_30
-gchar ** g_desktop_app_info_search (const gchar *term, gint max_hits);
+gchar ** g_desktop_app_info_search (const gchar *term,
+                                    GStringCompareDataFunc sort_by,
+                                    gpointer user_data,
+                                    gint max_hits);
 GLIB_AVAILABLE_IN_2_30
 gchar *** g_desktop_app_info_search_full (const gchar *term, gint max_hits);