[evolution-patches] vFolder shutdown speed issues

[Not Zed <notzed ximian com>]

If you have a bunch of big folders, that are matched by very large
vFolder rules, shutting down the mailer can be very slow/cpu intensive.

This patch fixes the main case of linear removal of array members, which
runs O(N^2).  Well on my machine it was taking 5-10 seconds to run
through this (about 120K messages in the unread folder), but now its
negligable.

Also changed the folder rebuilding code which runs when the vFolder
query is changed.  Should speed up some cases of that anyway.

Index: ChangeLog
===================================================================
RCS file: /cvs/gnome/evolution/camel/ChangeLog,v
retrieving revision 1.1830
diff -u -3 -r1.1830 ChangeLog
--- ChangeLog	17 Jun 2003 03:20:56 -0000	1.1830
+++ ChangeLog	17 Jun 2003 07:13:49 -0000
@@ -1,3 +1,14 @@
+2003-06-17  Not Zed  <NotZed Ximian com>
+
+	* camel-vee-folder.c (vee_folder_remove_folder): Calculate ranges
+	to remove folder info's more efficiently.  affects shutdown
+	performance on big vfolders signifinantly.
+	(vee_folder_build_folder): do the same here, when rebuilding a
+	folder's definition.
+
+	* camel-folder-summary.c (camel_folder_summary_remove_index): new
+	function to drop a range of index entries in one hit.
+
 2003-06-16  Not Zed  <NotZed Ximian com>
 
 	** See bug #44322
Index: camel-vee-folder.c
===================================================================
RCS file: /cvs/gnome/evolution/camel/camel-vee-folder.c,v
retrieving revision 1.56
diff -u -3 -r1.56 camel-vee-folder.c
--- camel-vee-folder.c	16 May 2003 18:47:49 -0000	1.56
+++ camel-vee-folder.c	17 Jun 2003 07:13:50 -0000
@@ -896,7 +896,7 @@
 static void
 vee_folder_remove_folder(CamelVeeFolder *vf, CamelFolder *source, int killun)
 {
-	int i, count, n, still;
+	int i, count, n, still, start, last;
 	char *oldkey;
 	CamelFolder *folder = (CamelFolder *)vf;
 	char hash[8];
@@ -921,21 +921,34 @@
 
 	/* See if we just blow all uid's from this folder away from unmatched, regardless */
 	if (killun) {
+		start = -1;
+		last = -1;
 		count = camel_folder_summary_count(((CamelFolder *)folder_unmatched)->summary);
 		for (i=0;i<count;i++) {
 			CamelVeeMessageInfo *mi = (CamelVeeMessageInfo *)camel_folder_summary_index(((CamelFolder *)folder_unmatched)->summary, i);
 			
 			if (mi) {
 				if (mi->folder == source) {
-					camel_folder_summary_remove_index(((CamelFolder *)folder_unmatched)->summary, i);
 					camel_folder_change_info_remove_uid(folder_unmatched->changes, camel_message_info_uid(mi));
-					i--;
+					if (last == -1) {
+						last = start = i;
+					} else if (last+1 == i) {
+						last = i;
+					} else {
+						camel_folder_summary_remove_range(((CamelFolder *)folder_unmatched)->summary, start, last);
+						i -= (last-start)+1;
+						start = last = i;
+					}
 				}
 				camel_folder_summary_info_free(((CamelFolder *)folder_unmatched)->summary, (CamelMessageInfo *)mi);
 			}
 		}
+		if (last != -1)
+			camel_folder_summary_remove_range(((CamelFolder *)folder_unmatched)->summary, start, last);
 	}
 
+	start = -1;
+	last = -1;
 	count = camel_folder_summary_count(folder->summary);
 	for (i=0;i<count;i++) {
 		CamelVeeMessageInfo *mi = (CamelVeeMessageInfo *)camel_folder_summary_index(folder->summary, i);
@@ -944,8 +957,16 @@
 				const char *uid = camel_message_info_uid(mi);
 
 				camel_folder_change_info_remove_uid(vf->changes, uid);
-				camel_folder_summary_remove_index(folder->summary, i);
-				i--;
+
+				if (last == -1) {
+					last = start = i;
+				} else if (last+1 == i) {
+					last = i;
+				} else {
+					camel_folder_summary_remove_range(folder->summary, start, last);
+					i -= (last-start)+1;
+					start = last = i;
+				}
 				if ((vf->flags & CAMEL_STORE_FOLDER_PRIVATE) == 0) {
 					if (still) {
 						if (g_hash_table_lookup_extended(unmatched_uids, uid, (void **)&oldkey, (void **)&n)) {
@@ -970,6 +991,9 @@
 		}
 	}
 
+	if (last != -1)
+		camel_folder_summary_remove_range(folder->summary, start, last);
+
 	if (camel_folder_change_info_changed(folder_unmatched->changes)) {
 		unmatched_changes = folder_unmatched->changes;
 		folder_unmatched->changes = camel_folder_change_info_new();
@@ -1051,7 +1075,7 @@
 	GHashTable *allhash, *matchhash;
 	CamelFolder *f = source;
 	CamelFolder *folder = (CamelFolder *)vf;
-	int i, n, count;
+	int i, n, count, start, last;
 	struct _update_data u;
 	CamelFolderChangeInfo *vf_changes = NULL, *unmatched_changes = NULL;
 
@@ -1088,6 +1112,8 @@
 	CAMEL_VEE_FOLDER_LOCK(folder_unmatched, summary_lock);
 
 	/* scan, looking for "old" uid's to be removed */
+	start = -1;
+	last = -1;
 	count = camel_folder_summary_count(folder->summary);
 	for (i=0;i<count;i++) {
 		CamelVeeMessageInfo *mi = (CamelVeeMessageInfo *)camel_folder_summary_index(folder->summary, i);
@@ -1097,9 +1123,16 @@
 				char *uid = (char *)camel_message_info_uid(mi), *oldkey;
 
 				if (g_hash_table_lookup(matchhash, uid+8) == NULL) {
-					camel_folder_summary_remove_index(folder->summary, i);
+					if (last == -1) {
+						last = start = i;
+					} else if (last+1 == i) {
+						last = i;
+					} else {
+						camel_folder_summary_remove_range(folder->summary, start, last);
+						i -= (last-start)+1;
+						start = last = i;
+					}
 					camel_folder_change_info_remove_uid(vf->changes, camel_message_info_uid(mi));
-					i--;
 					if (!CAMEL_IS_VEE_FOLDER(source)
 					    && g_hash_table_lookup_extended(unmatched_uids, uid, (void **)&oldkey, (void **)&n)) {
 						if (n == 1) {
@@ -1116,6 +1149,8 @@
 			camel_folder_summary_info_free(folder->summary, (CamelMessageInfo *)mi);
 		}
 	}
+	if (last != -1)
+		camel_folder_summary_remove_range(folder->summary, start, last);
 
 	/* now matchhash contains any new uid's, add them, etc */
 	g_hash_table_foreach(matchhash, (GHFunc)folder_added_uid, &u);
Index: camel-folder-summary.c
===================================================================
RCS file: /cvs/gnome/evolution/camel/camel-folder-summary.c,v
retrieving revision 1.120
diff -u -3 -r1.120 camel-folder-summary.c
--- camel-folder-summary.c	20 May 2003 15:59:55 -0000	1.120
+++ camel-folder-summary.c	17 Jun 2003 07:13:51 -0000
@@ -1186,6 +1186,48 @@
 	}
 }
 
+/**
+ * camel_folder_summary_remove_range:
+ * @s: 
+ * @start: initial index
+ * @end: last index to remove
+ * 
+ * Removes an indexed range of info records.
+ **/
+void camel_folder_summary_remove_range(CamelFolderSummary *s, int start, int end)
+{
+	if (end <= start+1)
+		return;
+
+	CAMEL_SUMMARY_LOCK(s, summary_lock);
+	if (start < s->messages->len) {
+		CamelMessageInfo **infos;
+		int i;
+
+		end = MIN(end+1, s->messages->len);
+		infos = g_malloc((end-start)*sizeof(infos[0]));
+
+		for (i=start;i<end;i++) {
+			CamelMessageInfo *info = s->messages->pdata[i];
+
+			infos[i-start] = info;
+			g_hash_table_remove(s->messages_uid, camel_message_info_uid(info));
+		}
+
+		memmove(s->messages->pdata+start, s->messages->pdata+end, (s->messages->len-end)*sizeof(s->messages->pdata[0]));
+		g_ptr_array_set_size(s->messages, s->messages->len - (end - start));
+		s->flags |= CAMEL_SUMMARY_DIRTY;
+
+		CAMEL_SUMMARY_UNLOCK(s, summary_lock);
+
+		for (i=start;i<end;i++)
+			camel_folder_summary_info_free(s, infos[i-start]);
+		g_free(infos);
+	} else {
+		CAMEL_SUMMARY_UNLOCK(s, summary_lock);
+	}
+}
+
 /* should be sorted, for binary search */
 /* This is a tokenisation mechanism for strings written to the
    summary - to save space.
Index: camel-folder-summary.h
===================================================================
RCS file: /cvs/gnome/evolution/camel/camel-folder-summary.h,v
retrieving revision 1.65
diff -u -3 -r1.65 camel-folder-summary.h
--- camel-folder-summary.h	5 Aug 2002 13:37:15 -0000	1.65
+++ camel-folder-summary.h	17 Jun 2003 07:13:51 -0000
@@ -255,6 +255,7 @@
 void camel_folder_summary_remove(CamelFolderSummary *s, CamelMessageInfo *info);
 void camel_folder_summary_remove_uid(CamelFolderSummary *s, const char *uid);
 void camel_folder_summary_remove_index(CamelFolderSummary *s, int);
+void camel_folder_summary_remove_range(CamelFolderSummary *s, int, int);
 /* remove all items */
 void camel_folder_summary_clear(CamelFolderSummary *s);