[nautilus] nautilus-directory: Implement monitor list with hash table

[Carlos Soriano <csoriano src gnome org>]

commit 4d99764f29a2e910f15a2511cbe76ca40f1f4771
Author: Xiang Fan <sfanxiang gmail com>
Date:   Wed Dec 5 19:09:36 2018 +0800

    nautilus-directory: Implement monitor list with hash table
    
    The original linked list can be O(n^2) (n = the number of files)
    in the worst case.

 src/nautilus-directory-async.c   | 243 +++++++++++++++++++++++++++------------
 src/nautilus-directory-private.h |   2 +-
 src/nautilus-directory.c         |  16 ++-
 3 files changed, 187 insertions(+), 74 deletions(-)
---
diff --git a/src/nautilus-directory-async.c b/src/nautilus-directory-async.c
index fc22bd042..d4124d469 100644
--- a/src/nautilus-directory-async.c
+++ b/src/nautilus-directory-async.c
@@ -287,16 +287,22 @@ nautilus_directory_verify_request_counts (NautilusDirectory *directory)
     RequestCounter counters;
     int i;
     gboolean fail;
+    GHashTableIter monitor_iter;
+    gpointer value;
 
     fail = FALSE;
     for (i = 0; i < REQUEST_TYPE_LAST; i++)
     {
         counters[i] = 0;
     }
-    for (l = directory->details->monitor_list; l != NULL; l = l->next)
+    g_hash_table_iter_init (&monitor_iter, directory->details->monitor_table);
+    while (g_hash_table_iter_next (&monitor_iter, NULL, &value))
     {
-        Monitor *monitor = l->data;
-        request_counter_add_request (counters, monitor->request);
+        for (l = value; l; l = l->next)
+        {
+            Monitor *monitor = l->data;
+            request_counter_add_request (counters, monitor->request);
+        }
     }
     for (i = 0; i < REQUEST_TYPE_LAST; i++)
     {
@@ -605,37 +611,90 @@ monitor_key_compare (gconstpointer a,
     return 0;
 }
 
-static GList *
+static Monitor *
 find_monitor (NautilusDirectory *directory,
               NautilusFile      *file,
               gconstpointer      client)
 {
-    Monitor monitor;
+    GList *l;
+
+    l = g_hash_table_lookup (directory->details->monitor_table, file);
+
+    if (l)
+    {
+        Monitor key = {};
+        key.client = client;
+        key.file = file;
 
-    monitor.client = client;
-    monitor.file = file;
+        l = g_list_find_custom (l, &key, monitor_key_compare);
+        return l ? l->data : NULL;
+    }
 
-    return g_list_find_custom (directory->details->monitor_list,
-                               &monitor,
-                               monitor_key_compare);
+    return NULL;
 }
 
-static void
-remove_monitor_link (NautilusDirectory *directory,
-                     GList             *link)
+static gboolean
+insert_new_monitor (NautilusDirectory *directory,
+                    Monitor           *monitor)
 {
-    Monitor *monitor;
+    GList *list;
 
-    if (link != NULL)
+    if (find_monitor (directory, monitor->file, monitor->client) != NULL)
     {
-        monitor = link->data;
-        request_counter_remove_request (directory->details->monitor_counters,
-                                        monitor->request);
-        directory->details->monitor_list =
-            g_list_remove_link (directory->details->monitor_list, link);
-        g_free (monitor);
-        g_list_free_1 (link);
+        return FALSE;
+    }
+
+    list = g_hash_table_lookup (directory->details->monitor_table, monitor->file);
+    if (list == NULL)
+    {
+        list = g_list_append (list, monitor);
+        g_hash_table_insert (directory->details->monitor_table,
+                             monitor->file,
+                             list);
+    }
+    else
+    {
+        list = g_list_append (list, monitor);
+    }
+
+    request_counter_add_request (directory->details->monitor_counters,
+                                 monitor->request);
+    return TRUE;
+}
+
+static Monitor *
+remove_monitor_from_table (NautilusDirectory *directory,
+                           NautilusFile      *file,
+                           gconstpointer      client)
+{
+    GList *list, *l, *new_list;
+    Monitor *monitor = NULL;
+
+    list = g_hash_table_lookup (directory->details->monitor_table, file);
+    if (list)
+    {
+        Monitor key = {};
+        key.client = client;
+        key.file = file;
+
+        l = g_list_find_custom (list, &key, monitor_key_compare);
+        monitor = l ? l->data : NULL;
+    }
+
+    if (monitor != NULL)
+    {
+        new_list = g_list_delete_link (list, l);
+        if (new_list == NULL)
+        {
+            g_hash_table_remove (directory->details->monitor_table, file);
+        }
+        else
+        {
+            g_hash_table_replace (directory->details->monitor_table, file, new_list);
+        }
     }
+
+    return monitor;
 }
 
 static void
@@ -643,7 +702,16 @@ remove_monitor (NautilusDirectory *directory,
                 NautilusFile      *file,
                 gconstpointer      client)
 {
-    remove_monitor_link (directory, find_monitor (directory, file, client));
+    Monitor *monitor;
+
+    monitor = remove_monitor_from_table (directory, file, client);
+
+    if (monitor != NULL)
+    {
+        request_counter_remove_request (directory->details->monitor_counters,
+                                        monitor->request);
+        g_free (monitor);
+    }
 }
 
 Request
@@ -754,10 +822,8 @@ nautilus_directory_monitor_add_internal (NautilusDirectory         *directory,
     {
         REQUEST_SET_TYPE (monitor->request, REQUEST_FILE_LIST);
     }
-    directory->details->monitor_list =
-        g_list_prepend (directory->details->monitor_list, monitor);
-    request_counter_add_request (directory->details->monitor_counters,
-                                 monitor->request);
+
+    insert_new_monitor (directory, monitor);
 
     if (callback != NULL)
     {
@@ -1162,7 +1228,7 @@ nautilus_directory_monitor_remove_internal (NautilusDirectory *directory,
     remove_monitor (directory, file, client);
 
     if (directory->details->monitor != NULL
-        && directory->details->monitor_list == NULL)
+        && g_hash_table_size (directory->details->monitor_table) == 0)
     {
         nautilus_monitor_cancel (directory->details->monitor);
         directory->details->monitor = NULL;
@@ -1177,28 +1243,26 @@ FileMonitors *
 nautilus_directory_remove_file_monitors (NautilusDirectory *directory,
                                          NautilusFile      *file)
 {
-    GList *result, **list, *node, *next;
+    GList *result, *node;
     Monitor *monitor;
 
     g_assert (NAUTILUS_IS_DIRECTORY (directory));
     g_assert (NAUTILUS_IS_FILE (file));
     g_assert (file->details->directory == directory);
 
-    result = NULL;
+    result = g_hash_table_lookup (directory->details->monitor_table, file);
 
-    list = &directory->details->monitor_list;
-    for (node = directory->details->monitor_list; node != NULL; node = next)
+    if (result != NULL)
     {
-        next = node->next;
-        monitor = node->data;
+        g_hash_table_remove (directory->details->monitor_table, file);
 
-        if (monitor->file == file)
+        for (node = result; node; node = node->next)
         {
-            *list = g_list_remove_link (*list, node);
-            result = g_list_concat (node, result);
+            monitor = node->data;
             request_counter_remove_request (directory->details->monitor_counters,
                                             monitor->request);
         }
+        result = g_list_reverse (result);
     }
 
     /* XXX - do we need to remove anything from the work queue? */
@@ -1213,7 +1277,6 @@ nautilus_directory_add_file_monitors (NautilusDirectory *directory,
                                       NautilusFile      *file,
                                       FileMonitors      *monitors)
 {
-    GList **list;
     GList *l;
     Monitor *monitor;
 
@@ -1229,12 +1292,12 @@ nautilus_directory_add_file_monitors (NautilusDirectory *directory,
     for (l = (GList *) monitors; l != NULL; l = l->next)
     {
         monitor = l->data;
-        request_counter_add_request (directory->details->monitor_counters,
-                                     monitor->request);
+
+        remove_monitor (directory, monitor->file, monitor->client);
+        insert_new_monitor (directory, monitor);
     }
 
-    list = &directory->details->monitor_list;
-    *list = g_list_concat (*list, (GList *) monitors);
+    g_list_free ((GList *) monitors);
 
     nautilus_directory_add_file_to_work_queue (directory, file);
 
@@ -1631,18 +1694,19 @@ nautilus_async_destroying_file (NautilusFile *file)
     }
 
     /* Check for monitors. */
-    for (node = directory->details->monitor_list; node != NULL; node = next)
+    node = g_hash_table_lookup (directory->details->monitor_table, file);
+    if (node != NULL)
     {
-        next = node->next;
-        monitor = node->data;
-
-        if (monitor->file == file)
+        /* Client should have removed monitor earlier. */
+        g_warning ("destroyed file still being monitored");
+        for (; node; node = next)
         {
-            /* Client should have removed monitor earlier. */
-            g_warning ("destroyed file still being monitored");
-            remove_monitor_link (directory, node);
-            changed = TRUE;
+            next = node->next;
+            monitor = node->data;
+
+            remove_monitor (directory, monitor->file, monitor->client);
         }
+        changed = TRUE;
     }
 
     /* Check if it's a file that's currently being worked on.
@@ -1968,13 +2032,29 @@ call_ready_callbacks (NautilusDirectory *directory)
     return found_any;
 }
 
+static GList *
+lookup_monitors (GHashTable   *monitor_table,
+                 NautilusFile *file)
+{
+    /* To find monitors monitoring all files, use lookup_all_files_monitors. */
+    g_assert (file);
+
+    return g_hash_table_lookup (monitor_table, file);
+}
+
+static GList *
+lookup_all_files_monitors (GHashTable *monitor_table)
+{
+    /* monitor->file == NULL means monitor all files. */
+    return g_hash_table_lookup (monitor_table, NULL);
+}
+
 gboolean
 nautilus_directory_has_active_request_for_file (NautilusDirectory *directory,
                                                 NautilusFile      *file)
 {
     GList *node;
     ReadyCallback *callback;
-    Monitor *monitor;
 
     for (node = directory->details->call_when_ready_list;
          node != NULL; node = node->next)
@@ -1987,15 +2067,13 @@ nautilus_directory_has_active_request_for_file (NautilusDirectory *directory,
         }
     }
 
-    for (node = directory->details->monitor_list;
-         node != NULL; node = node->next)
+    if (lookup_monitors (directory->details->monitor_table, file) != NULL)
     {
-        monitor = node->data;
-        if (monitor->file == file ||
-            monitor->file == NULL)
-        {
-            return TRUE;
-        }
+        return TRUE;
+    }
+    if (lookup_all_files_monitors (directory->details->monitor_table) != NULL)
+    {
+        return TRUE;
     }
 
     return FALSE;
@@ -2327,6 +2405,7 @@ monitor_includes_file (const Monitor *monitor,
     {
         return TRUE;
     }
+    /* monitor->file == NULL means monitor all files. */
     if (monitor->file != NULL)
     {
         return FALSE;
@@ -2339,6 +2418,27 @@ monitor_includes_file (const Monitor *monitor,
                                       monitor->monitor_hidden_files);
 }
 
+static gboolean
+is_wanted_by_monitor (NautilusFile *file,
+                      GList        *monitors,
+                      RequestType   request_type_wanted) {
+    GList *node;
+
+    for (node = monitors; node; node = node->next)
+    {
+        Monitor *monitor = node->data;
+        if (REQUEST_WANTS_TYPE (monitor->request, request_type_wanted))
+        {
+            if (monitor_includes_file (monitor, file))
+            {
+                return TRUE;
+            }
+        }
+    }
+
+    return FALSE;
+}
+
 static gboolean
 is_needy (NautilusFile *file,
           FileCheck     check_missing,
@@ -2347,7 +2447,6 @@ is_needy (NautilusFile *file,
     NautilusDirectory *directory;
     GList *node;
     ReadyCallback *callback;
-    Monitor *monitor;
 
     if (!(*check_missing)(file))
     {
@@ -2379,19 +2478,21 @@ is_needy (NautilusFile *file,
 
     if (directory->details->monitor_counters[request_type_wanted] > 0)
     {
-        for (node = directory->details->monitor_list;
-             node != NULL; node = node->next)
+        GList *monitors;
+
+        monitors = lookup_monitors (directory->details->monitor_table, file);
+        if (is_wanted_by_monitor (file, monitors, request_type_wanted))
         {
-            monitor = node->data;
-            if (REQUEST_WANTS_TYPE (monitor->request, request_type_wanted))
-            {
-                if (monitor_includes_file (monitor, file))
-                {
-                    return TRUE;
-                }
-            }
+            return TRUE;
+        }
+
+        monitors = lookup_all_files_monitors (directory->details->monitor_table);
+        if (is_wanted_by_monitor (file, monitors, request_type_wanted))
+        {
+            return TRUE;
         }
     }
+
     return FALSE;
 }
 
diff --git a/src/nautilus-directory-private.h b/src/nautilus-directory-private.h
index 54d3f0465..8f1a23590 100644
--- a/src/nautilus-directory-private.h
+++ b/src/nautilus-directory-private.h
@@ -79,7 +79,7 @@ struct NautilusDirectoryDetails
         */
        GList *call_when_ready_list;
        RequestCounter call_when_ready_counters;
-       GList *monitor_list;
+       GHashTable *monitor_table;
        RequestCounter monitor_counters;
        guint call_ready_idle_id;
 
diff --git a/src/nautilus-directory.c b/src/nautilus-directory.c
index a1db06b0b..3b1556a37 100644
--- a/src/nautilus-directory.c
+++ b/src/nautilus-directory.c
@@ -174,11 +174,22 @@ nautilus_directory_finalize (GObject *object)
     nautilus_directory_cancel (directory);
     g_assert (directory->details->count_in_progress == NULL);
 
-    if (directory->details->monitor_list != NULL)
+    if (g_hash_table_size (directory->details->monitor_table) != 0)
     {
+        GHashTableIter iter;
+        gpointer value;
+
         g_warning ("destroying a NautilusDirectory while it's being monitored");
-        g_list_free_full (directory->details->monitor_list, g_free);
+
+        g_hash_table_iter_init (&iter, directory->details->monitor_table);
+        while (g_hash_table_iter_next (&iter, NULL, &value))
+        {
+            GList *list = value;
+            g_list_free_full (list, g_free);
+        }
+        g_hash_table_remove_all (directory->details->monitor_table);
     }
+    g_hash_table_destroy (directory->details->monitor_table);
 
     if (directory->details->monitor != NULL)
     {
@@ -334,6 +345,7 @@ nautilus_directory_init (NautilusDirectory *directory)
     directory->details->high_priority_queue = nautilus_file_queue_new ();
     directory->details->low_priority_queue = nautilus_file_queue_new ();
     directory->details->extension_queue = nautilus_file_queue_new ();
+    directory->details->monitor_table = g_hash_table_new (NULL, NULL);
 }
 
 NautilusDirectory *