dupe: Eliminate O(n^2) code in dupe_files_add_queue_cb()

[geeqie.git] / src / dupe.c

diff --git a/src/dupe.c b/src/dupe.c
index e2c5057..95db214 100644 (file)
--- a/src/dupe.c
+++ b/src/dupe.c
@@ -107,6 +107,11 @@ static void dupe_notify_cb(FileData *fd, NotifyType type, gpointer data);
 
 static GtkWidget *submenu_add_export(GtkWidget *menu, GtkWidget **menu_item, GCallback func, gpointer data);
 static void dupe_pop_menu_export_cb(GtkWidget *widget, gpointer data);
+
+static void dupe_init_list_cache(DupeWindow *dw);
+static void dupe_destroy_list_cache(DupeWindow *dw);
+static gboolean dupe_insert_in_list_cache(DupeWindow *dw, FileData *fd);
+
 /*
  * ------------------------------------------------------------------
  * Window updates
@@ -1893,6 +1898,7 @@ static void dupe_check_stop(DupeWindow *dw)
                {
                g_source_remove(dw->add_files_queue_id);
                dw->add_files_queue_id = 0;
+               dupe_destroy_list_cache(dw);
                gtk_widget_set_sensitive(dw->controls_box, TRUE);
                if (g_list_length(dw->add_files_queue) > 0)
                        {
@@ -2356,6 +2362,7 @@ static gboolean dupe_files_add_queue_cb(gpointer data)
        if (queue == NULL)
                {
                dw->add_files_queue_id = 0;
+               dupe_destroy_list_cache(dw);
                g_idle_add(dupe_check_start_cb, dw);
                gtk_widget_set_sensitive(dw->controls_box, TRUE);
                return FALSE;
@@ -2400,37 +2407,10 @@ static gboolean dupe_files_add_queue_cb(gpointer data)
        dupe_item_read_cache(di);
 
        /* Ensure images in the lists have unique FileDatas */
-       GList *work;
-       DupeItem *di_list;
-       work = g_list_first(dw->list);
-       while (work)
-               {
-               di_list = work->data;
-               if (di_list->fd == di->fd)
-                       {
-                       return TRUE;
-                       }
-               else
-                       {
-                       work = work->next;
-                       }
-               }
-
-       if (dw->second_list)
+       if (!dupe_insert_in_list_cache(dw, di->fd))
                {
-               work = g_list_first(dw->second_list);
-               while (work)
-                       {
-                       di_list = work->data;
-                       if (di_list->fd == di->fd)
-                               {
-                               return TRUE;
-                               }
-                       else
-                               {
-                               work = work->next;
-                               }
-                       }
+               dupe_item_free(di);
+               return TRUE;
                }
 
        if (dw->second_drop)
@@ -2449,6 +2429,7 @@ static gboolean dupe_files_add_queue_cb(gpointer data)
        else
                {
                dw->add_files_queue_id = 0;
+               dupe_destroy_list_cache(dw);
                g_idle_add(dupe_check_start_cb, dw);
                gtk_widget_set_sensitive(dw->controls_box, TRUE);
                return FALSE;
@@ -2546,6 +2527,44 @@ static void dupe_files_add(DupeWindow *dw, CollectionData *collection, CollectIn
                }
 }
 
+static void dupe_init_list_cache(DupeWindow *dw)
+{
+       dw->list_cache = g_hash_table_new(g_direct_hash, g_direct_equal);
+       dw->second_list_cache = g_hash_table_new(g_direct_hash, g_direct_equal);
+
+       for (GList *i = dw->list; i != NULL; i = i->next)
+               {
+                       DupeItem *di = i->data;
+
+                       g_hash_table_add(dw->list_cache, di->fd);
+               }
+
+       for (GList *i = dw->second_list; i != NULL; i = i->next)
+               {
+                       DupeItem *di = i->data;
+
+                       g_hash_table_add(dw->second_list_cache, di->fd);
+               }
+}
+
+static void dupe_destroy_list_cache(DupeWindow *dw)
+{
+       g_hash_table_destroy(dw->list_cache);
+       g_hash_table_destroy(dw->second_list_cache);
+}
+
+/* Return true if the fd was not in the cache */
+static gboolean dupe_insert_in_list_cache(DupeWindow *dw, FileData *fd)
+{
+       GHashTable *table =
+               dw->second_drop ? dw->second_list_cache : dw->list_cache;
+       /* We do this as a lookup + add as we don't want to overwrite
+          items as that would leak the old value. */
+       if (g_hash_table_lookup(table, fd) != NULL)
+               return TRUE;
+       return g_hash_table_add(table, fd);
+}
+
 void dupe_window_add_collection(DupeWindow *dw, CollectionData *collection)
 {
        CollectInfo *info;
@@ -2599,6 +2618,7 @@ void dupe_window_add_files(DupeWindow *dw, GList *list, gboolean recurse)
                gtk_progress_bar_set_pulse_step(GTK_PROGRESS_BAR(dw->extra_label), DUPE_PROGRESS_PULSE_STEP);
                gtk_progress_bar_set_text(GTK_PROGRESS_BAR(dw->extra_label), _("Loading file list"));
 
+               dupe_init_list_cache(dw);
                dw->add_files_queue_id = g_idle_add(dupe_files_add_queue_cb, dw);
                gtk_widget_set_sensitive(dw->controls_box, FALSE);
                }