[gnome-shell] Define stable ordering for application favorites and running apps

[Colin Walters <walters src gnome org>]

commit 687a87d3d090283b0404b44a2159bd063f4fa20c
Author: Colin Walters <walters verbum org>
Date:   Sat Aug 8 10:03:08 2009 -0400

    Define stable ordering for application favorites and running apps
    
    For both of these, because of optimizations a few patches ago, we
    ended up relying on hash table ordering which caused instability
    in the application well among other things. Define an ordering
    for both.
    
    The favorites is just the order of the GConf keys, and new items
    get appended.  In the future we should allow insertion at any
    point which the grid could use.
    
    For running applications order, define a new "initially_seen_sequence"
    transient variable which is just an monotonically incrementing
    integer assigned to an application for the first time we saw it
    running in this session.  When an application is closed, it's reset.

 src/shell-app-monitor.c |   55 +++++++++++++++++++++++++++++++++++++++---
 src/shell-app-system.c  |   61 +++++++++++++++++++++++++++--------------------
 2 files changed, 86 insertions(+), 30 deletions(-)
---
diff --git a/src/shell-app-monitor.c b/src/shell-app-monitor.c
index 7359e02..b4d61b5 100644
--- a/src/shell-app-monitor.c
+++ b/src/shell-app-monitor.c
@@ -115,6 +115,9 @@ struct _ShellAppMonitor
   gboolean currently_idle;
   gboolean enable_monitoring;
 
+  /* See comment in AppUsage below */
+  guint initially_seen_sequence;
+
   GSList *previously_running;
 
   long watch_start_time;
@@ -138,6 +141,12 @@ struct AppUsage
   /* how many windows are currently open; in terms of persistence we only save
    * whether the app had any windows or not. */
   guint window_count;
+
+  /* Transient data */
+  guint initially_seen_sequence; /* Arbitrary ordered integer for when we first saw
+                                  * this application in this session.  Used to order
+                                  * the open applications.
+                                  */
 };
 
 enum {
@@ -153,6 +162,9 @@ static void shell_app_monitor_finalize (GObject *object);
 static void on_session_status_changed (DBusGProxy *proxy, guint status, ShellAppMonitor *monitor);
 static void on_focus_window_changed (MetaDisplay *display, GParamSpec *spec, ShellAppMonitor *monitor);
 static void ensure_queued_save (ShellAppMonitor *monitor);
+static AppUsage * get_app_usage_for_context_and_id (ShellAppMonitor *monitor,
+                                                    const char      *context,
+                                                    const char      *appid);
 
 static gboolean idle_save_application_usage (gpointer data);
 
@@ -316,8 +328,8 @@ get_usages_for_context (ShellAppMonitor *monitor,
 
 static AppUsage *
 get_app_usage_for_context_and_id (ShellAppMonitor *monitor,
-                                   const char      *context,
-                                   const char      *appid)
+                                  const char      *context,
+                                  const char      *appid)
 {
   AppUsage *usage;
   GHashTable *context_usages;
@@ -329,6 +341,7 @@ get_app_usage_for_context_and_id (ShellAppMonitor *monitor,
     return usage;
 
   usage = g_new0 (AppUsage, 1);
+  usage->initially_seen_sequence = ++monitor->initially_seen_sequence;
   g_hash_table_insert (context_usages, g_strdup (appid), usage);
 
   return usage;
@@ -497,6 +510,8 @@ track_window (ShellAppMonitor *self,
    * when it switches between 0 and 1 we emit a changed signal.
    */
   usage->window_count++;
+  if (usage->initially_seen_sequence == 0)
+    usage->initially_seen_sequence = ++self->initially_seen_sequence;
   usage->last_seen = get_time ();
   if (usage->window_count == 1)
     g_signal_emit (self, signals[CHANGED], 0);
@@ -535,7 +550,10 @@ shell_app_monitor_on_window_removed (MetaWorkspace   *workspace,
   g_hash_table_remove (self->window_to_app, window);
 
   if (usage->window_count == 0)
-    g_signal_emit (self, signals[CHANGED], 0);
+    {
+      usage->initially_seen_sequence = 0;
+      g_signal_emit (self, signals[CHANGED], 0);
+    }
 }
 
 static void
@@ -787,6 +805,31 @@ shell_app_monitor_get_window_app (ShellAppMonitor *monitor,
   return info;
 }
 
+typedef struct {
+  ShellAppMonitor *self;
+  const char *context_id;
+} AppOpenSequenceSortData;
+
+static int
+sort_apps_by_open_sequence (gconstpointer a,
+                            gconstpointer b,
+                            gpointer datap)
+{
+  AppOpenSequenceSortData *data = datap;
+  const char *id_a = a;
+  const char *id_b = b;
+  AppUsage *usage_a;
+  AppUsage *usage_b;
+
+  usage_a = get_app_usage_for_context_and_id (data->self, data->context_id, id_a);
+  usage_b = get_app_usage_for_context_and_id (data->self, data->context_id, id_b);
+  if (usage_a->initially_seen_sequence == usage_b->initially_seen_sequence)
+    return 0;
+  if (usage_a->initially_seen_sequence < usage_b->initially_seen_sequence)
+    return -1;
+  return 1;
+}
+
 /**
  * shell_app_monitor_get_running_app_ids:
  * @monitor: An app monitor instance
@@ -807,6 +850,7 @@ shell_app_monitor_get_running_app_ids (ShellAppMonitor *monitor,
   const char *id;
   AppUsage *usage;
   GSList *ret;
+  AppOpenSequenceSortData data;
 
   usage_iterator_init (monitor, &iter);
 
@@ -820,7 +864,9 @@ shell_app_monitor_get_running_app_ids (ShellAppMonitor *monitor,
         ret = g_slist_prepend (ret, (char*)id);
     }
 
-  return ret;
+  data.self = monitor;
+  data.context_id = context;
+  return g_slist_sort_with_data (ret, sort_apps_by_open_sequence, &data);
 }
 
 static gboolean
@@ -1132,6 +1178,7 @@ shell_app_monitor_start_element_handler  (GMarkupParseContext *context,
       usage_table = get_usages_for_context (data->monitor, data->context);
 
       usage = g_new0 (AppUsage, 1);
+      usage->initially_seen_sequence = 0;
       g_hash_table_insert (usage_table, appid, usage);
 
       for (attribute = attribute_names, value = attribute_values; *attribute; attribute++, value++)
diff --git a/src/shell-app-system.c b/src/shell-app-system.c
index a8910ca..cee5fc8 100644
--- a/src/shell-app-system.c
+++ b/src/shell-app-system.c
@@ -41,7 +41,7 @@ struct _ShellAppSystemPrivate {
 
   GSList *cached_settings; /* ShellAppInfo */
 
-  GHashTable *cached_favorites; /* <utf8,integer> */
+  GList *cached_favorites; /* utf8 */
 
   gint app_monitor_id;
 };
@@ -125,10 +125,6 @@ shell_app_system_init (ShellAppSystem *self)
                                                    SHELL_TYPE_APP_SYSTEM,
                                                    ShellAppSystemPrivate);
 
-  priv->cached_favorites = g_hash_table_new_full (g_str_hash, g_str_equal,
-                                                  (GDestroyNotify)g_free,
-                                                  NULL);
-
   /* The key is owned by the value */
   priv->app_id_to_app = g_hash_table_new_full (g_str_hash, g_str_equal,
                                                NULL, (GDestroyNotify) shell_app_info_unref);
@@ -174,7 +170,7 @@ shell_app_system_finalize (GObject *object)
   g_slist_free (priv->cached_settings);
   priv->cached_settings = NULL;
 
-  g_hash_table_destroy (priv->cached_favorites);
+  g_list_free (priv->cached_favorites);
 
   gconf_client_notify_remove (gconf_client_get_default (), priv->app_monitor_id);
 
@@ -327,12 +323,13 @@ on_tree_changed (GMenuTree *monitor, gpointer user_data)
   reread_menus (self);
 }
 
-static void
-copy_gconf_value_string_list_to_hashset (GConfValue *value,
-                                         GHashTable *dest)
+static GList *
+convert_gconf_value_string_list_to_list_uniquify (GConfValue *value )
 {
   GSList *list;
   GSList *tmp;
+  GList *result = NULL;
+  GHashTable *tmp_table = g_hash_table_new (g_str_hash, g_str_equal);
 
   list = gconf_value_get_list (value);
 
@@ -342,8 +339,16 @@ copy_gconf_value_string_list_to_hashset (GConfValue *value,
       char *str = g_strdup (gconf_value_get_string (value));
       if (!str)
         continue;
-      g_hash_table_insert (dest, str, GUINT_TO_POINTER(1));
+      if (g_hash_table_lookup (tmp_table, str))
+        {
+          g_free (str);
+          continue;
+        }
+      g_hash_table_insert (tmp_table, str, GUINT_TO_POINTER(1));
+      result = g_list_prepend (result, str);
     }
+  g_hash_table_destroy (tmp_table);
+  return g_list_reverse (result);
 }
 
 static void
@@ -357,8 +362,9 @@ reread_favorite_apps (ShellAppSystem *system)
   if (!(val && val->type == GCONF_VALUE_LIST && gconf_value_get_list_type (val) == GCONF_VALUE_STRING))
     return;
 
-  g_hash_table_remove_all (system->priv->cached_favorites);
-  copy_gconf_value_string_list_to_hashset (val, system->priv->cached_favorites);
+  g_list_foreach (system->priv->cached_favorites, (GFunc) g_free, NULL);
+  g_list_free (system->priv->cached_favorites);
+  system->priv->cached_favorites = convert_gconf_value_string_list_to_list_uniquify (val);
 
   gconf_value_free (val);
 }
@@ -476,12 +482,12 @@ shell_app_system_get_default ()
  * Return the list of applications which have been explicitly added to the
  * favorites.
  *
- * Return value: (transfer container) (element-type utf8): List of favorite application ids
+ * Return value: (transfer none) (element-type utf8): List of favorite application ids
  */
 GList *
 shell_app_system_get_favorites (ShellAppSystem *system)
 {
-  return g_hash_table_get_keys (system->priv->cached_favorites);
+  return system->priv->cached_favorites;
 }
 
 static void
@@ -503,22 +509,25 @@ set_gconf_value_string_list (GConfValue *val, GList *items)
   g_slist_free (tmp);
 }
 
+
+
 void
 shell_app_system_add_favorite (ShellAppSystem *system, const char *id)
 {
   GConfClient *client = gconf_client_get_default ();
   GConfValue *val;
-  GList *favorites;
+  GList *iter;
+
+  iter = g_list_find_custom (system->priv->cached_favorites, id, (GCompareFunc)strcmp);
+  if (iter)
+    return;
 
   val = gconf_value_new (GCONF_VALUE_LIST);
   gconf_value_set_list_type (val, GCONF_VALUE_STRING);
 
-  g_hash_table_insert (system->priv->cached_favorites, g_strdup (id), GUINT_TO_POINTER (1));
-
-  favorites = g_hash_table_get_keys (system->priv->cached_favorites);
-  set_gconf_value_string_list (val, favorites);
-  g_list_free (favorites);
+  system->priv->cached_favorites = g_list_append (system->priv->cached_favorites, g_strdup (id));
 
+  set_gconf_value_string_list (val, system->priv->cached_favorites);
   gconf_client_set (client, SHELL_APP_FAVORITES_KEY, val, NULL);
 }
 
@@ -527,18 +536,18 @@ shell_app_system_remove_favorite (ShellAppSystem *system, const char *id)
 {
   GConfClient *client = gconf_client_get_default ();
   GConfValue *val;
-  GList *favorites;
+  GList *iter;
 
-  if (!g_hash_table_remove (system->priv->cached_favorites, id))
+  iter = g_list_find_custom (system->priv->cached_favorites, id, (GCompareFunc)strcmp);
+  if (!iter)
     return;
+  g_free (iter->data);
+  system->priv->cached_favorites = g_list_delete_link (system->priv->cached_favorites, iter);
 
   val = gconf_value_new (GCONF_VALUE_LIST);
   gconf_value_set_list_type (val, GCONF_VALUE_STRING);
 
-  favorites = g_hash_table_get_keys (system->priv->cached_favorites);
-  set_gconf_value_string_list (val, favorites);
-  g_list_free (favorites);
-
+  set_gconf_value_string_list (val, system->priv->cached_favorites);
   gconf_client_set (client, SHELL_APP_FAVORITES_KEY, val, NULL);
 }