[nautilus/gnome-3-20] file-undo-operations: use queue for storing sources and destinations

[Carlos Soriano Sánchez <csoriano src gnome org>]

commit a49d600b5a2c2bc6a8e330f4876df48e53cf6556
Author: Razvan Chitu <razvan ch95 gmail com>
Date:   Thu May 5 15:33:20 2016 +0300

    file-undo-operations: use queue for storing sources and destinations
    
    When copying, moving or linking files, original sources and their destinations
    are stored in an information structure used for undoing the operation. The
    sources and destinations were appended at the end of a list. Due to append
    taking linear time, these file operations would have a resulting quadratic
    complexity depending on the number of files. When operating on thousands of
    files, this would lead to a significant decrease in speed. In order to fix
    this, the sources and destinations are stored in a queue that allows appending
    in constant time.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=757747

 .../nautilus-file-undo-operations.c                |   69 ++++++++++++-------
 1 files changed, 43 insertions(+), 26 deletions(-)
---
diff --git a/libnautilus-private/nautilus-file-undo-operations.c 
b/libnautilus-private/nautilus-file-undo-operations.c
index 9e96b35..01f27f3 100644
--- a/libnautilus-private/nautilus-file-undo-operations.c
+++ b/libnautilus-private/nautilus-file-undo-operations.c
@@ -322,8 +322,8 @@ G_DEFINE_TYPE (NautilusFileUndoInfoExt, nautilus_file_undo_info_ext, NAUTILUS_TY
 struct _NautilusFileUndoInfoExtDetails {
        GFile *src_dir;
        GFile *dest_dir;
-       GList *sources;      /* Relative to src_dir */
-       GList *destinations; /* Relative to dest_dir */
+        GQueue *sources;      /* Relative to src_dir */
+        GQueue *destinations; /* Relative to dest_dir */
 };
 
 static char *
@@ -332,7 +332,7 @@ ext_get_first_target_short_name (NautilusFileUndoInfoExt *self)
        GList *targets_first;
        char *file_name = NULL;
 
-       targets_first = g_list_first (self->priv->destinations);
+        targets_first = g_queue_peek_head_link (self->priv->destinations);
 
        if (targets_first != NULL &&
            targets_first->data != NULL) {
@@ -471,35 +471,47 @@ static void
 ext_create_link_redo_func (NautilusFileUndoInfoExt *self,
                           GtkWindow *parent_window)
 {
-       nautilus_file_operations_link (self->priv->sources, NULL,
-                                      self->priv->dest_dir, parent_window,
-                                      file_undo_info_transfer_callback, self);
+        nautilus_file_operations_link (g_queue_peek_head_link (self->priv->sources),
+                                       NULL,
+                                       self->priv->dest_dir,
+                                       parent_window,
+                                       file_undo_info_transfer_callback,
+                                       self);
 }
 
 static void
 ext_duplicate_redo_func (NautilusFileUndoInfoExt *self,
                         GtkWindow *parent_window)
 {
-       nautilus_file_operations_duplicate (self->priv->sources, NULL, parent_window,
-                                           file_undo_info_transfer_callback, self);
+        nautilus_file_operations_duplicate (g_queue_peek_head_link (self->priv->sources),
+                                            NULL,
+                                            parent_window,
+                                            file_undo_info_transfer_callback,
+                                            self);
 }
 
 static void
 ext_copy_redo_func (NautilusFileUndoInfoExt *self,
                    GtkWindow *parent_window)
 {
-       nautilus_file_operations_copy (self->priv->sources, NULL,
-                                      self->priv->dest_dir, parent_window,
-                                      file_undo_info_transfer_callback, self);
+        nautilus_file_operations_copy (g_queue_peek_head_link (self->priv->sources),
+                                       NULL,
+                                       self->priv->dest_dir,
+                                       parent_window,
+                                       file_undo_info_transfer_callback,
+                                       self);
 }
 
 static void
 ext_move_restore_redo_func (NautilusFileUndoInfoExt *self,
                            GtkWindow *parent_window)
 {
-       nautilus_file_operations_move (self->priv->sources, NULL,
-                                      self->priv->dest_dir, parent_window,
-                                      file_undo_info_transfer_callback, self);
+        nautilus_file_operations_move (g_queue_peek_head_link (self->priv->sources),
+                                       NULL,
+                                       self->priv->dest_dir,
+                                       parent_window,
+                                       file_undo_info_transfer_callback,
+                                       self);
 }
 
 static void
@@ -527,8 +539,10 @@ static void
 ext_restore_undo_func (NautilusFileUndoInfoExt *self,
                       GtkWindow *parent_window)
 {
-       nautilus_file_operations_trash_or_delete (self->priv->destinations, parent_window,
-                                                 file_undo_info_delete_callback, self);
+        nautilus_file_operations_trash_or_delete (g_queue_peek_head_link (self->priv->destinations),
+                                                  parent_window,
+                                                  file_undo_info_delete_callback,
+                                                  self);
 }
 
 
@@ -536,9 +550,12 @@ static void
 ext_move_undo_func (NautilusFileUndoInfoExt *self,
                    GtkWindow *parent_window)
 {
-       nautilus_file_operations_move (self->priv->destinations, NULL,
-                                      self->priv->src_dir, parent_window,
-                                      file_undo_info_transfer_callback, self);
+        nautilus_file_operations_move (g_queue_peek_head_link (self->priv->destinations),
+                                       NULL,
+                                       self->priv->src_dir,
+                                       parent_window,
+                                       file_undo_info_transfer_callback,
+                                       self);
 }
 
 static void
@@ -547,7 +564,7 @@ ext_copy_duplicate_undo_func (NautilusFileUndoInfoExt *self,
 {
        GList *files;
 
-       files = g_list_copy (self->priv->destinations);
+        files = g_list_copy (g_queue_peek_head_link (self->priv->destinations));
        files = g_list_reverse (files); /* Deleting must be done in reverse */
 
        nautilus_file_operations_delete (files, parent_window,
@@ -589,11 +606,11 @@ nautilus_file_undo_info_ext_finalize (GObject *obj)
        NautilusFileUndoInfoExt *self = NAUTILUS_FILE_UNDO_INFO_EXT (obj);
 
        if (self->priv->sources) {
-               g_list_free_full (self->priv->sources, g_object_unref);
+                g_queue_free_full (self->priv->sources, g_object_unref);
        }
 
        if (self->priv->destinations) {
-               g_list_free_full (self->priv->destinations, g_object_unref);
+                g_queue_free_full (self->priv->destinations, g_object_unref);
        }
 
        g_clear_object (&self->priv->src_dir);
@@ -632,6 +649,8 @@ nautilus_file_undo_info_ext_new (NautilusFileUndoOp op_type,
 
        retval->priv->src_dir = g_object_ref (src_dir);
        retval->priv->dest_dir = g_object_ref (target_dir);
+        retval->priv->sources = g_queue_new ();
+        retval->priv->destinations = g_queue_new ();
 
        return NAUTILUS_FILE_UNDO_INFO (retval);
 }
@@ -641,10 +660,8 @@ nautilus_file_undo_info_ext_add_origin_target_pair (NautilusFileUndoInfoExt *sel
                                                    GFile                   *origin,
                                                    GFile                   *target)
 {
-       self->priv->sources =
-               g_list_append (self->priv->sources, g_object_ref (origin));
-       self->priv->destinations =
-               g_list_append (self->priv->destinations, g_object_ref (target));
+        g_queue_push_tail (self->priv->sources, g_object_ref (origin));
+        g_queue_push_tail (self->priv->destinations, g_object_ref (target));
 }
 
 /* create new file/folder */