[Users] [PATCH] Optimize remove_numbered_files_not_in_list() complexity from O(n^2) to O(n)

[Igor Mammedov]

If imap folder holds more then 55K messages, claws-mail may freeze for 5 or
more seconds scanning folder. Following call chain has
O(n^2) complexity: 
  folder_item_scan_full()
   -> imap_get_num_list()
       -> remove_numbered_files_not_in_list()

Converting it to O(n) significantly[1] cuts amount of executed
instructions and reduces folder re-scanning time to ~1sec.

 1) instruction fetch cut by factor 85, execution time cut from 44 to 0.7%.

Signed-off-by: Igor Mammedov <imammedo at redhat.com>
---

Index: src/common/utils.c
===================================================================
RCS file: //claws/src/common/utils.c,v
retrieving revision 1.36.2.201
diff -u -r1.36.2.201 utils.c
--- src/common/utils.c	12 Sep 2012 09:23:13 -0000	1.36.2.201
+++ src/common/utils.c	9 Oct 2012 20:06:13 -0000
@@ -2378,6 +2378,7 @@
 	const gchar *dir_name;
 	gchar *prev_dir;
 	gint file_no;
+	GHashTable *file_no_tbl;
 
 	prev_dir = g_get_current_dir();
 
@@ -2393,18 +2394,25 @@
 		return -1;
 	}
 
+	file_no_tbl = g_hash_table_new(g_direct_hash, g_direct_equal);
 	while ((dir_name = g_dir_read_name(dp)) != NULL) {
 		file_no = to_number(dir_name);
-		if (file_no > 0 && (g_slist_find(numberlist,
GINT_TO_POINTER(file_no)) == NULL)) {
-			debug_print("removing unwanted file %d from %s\n",
file_no, dir);
-			if (is_dir_exist(dir_name))
-				continue;
+		if (is_dir_exist(dir_name))
+			continue;
+		if (file_no > 0)
+		       	g_hash_table_insert(file_no_tbl,
GINT_TO_POINTER(file_no), GINT_TO_POINTER(1));
+	}
+
+	do {
+		if (g_hash_table_lookup(file_no_tbl, numberlist->data)) {
+			debug_print("removing unwanted file %d from %s\n",
GPOINTER_TO_INT(numberlist->data), dir); if (claws_unlink(dir_name) < 0)
 				FILE_OP_ERROR(dir_name, "unlink");
 		}
-	}
+	} while ((numberlist = g_slist_next(numberlist)));
 
 	g_dir_close(dp);
+	g_hash_table_destroy(file_no_tbl);
 
 	if (g_chdir(prev_dir) < 0) {
 		FILE_OP_ERROR(prev_dir, "chdir");


-- 
Regards,
  Igor