faster subject/sender/date sorting

[Don Lewis]

--0-1804289383-1049701158=:4804
Content-Type: TEXT/plain; charset=us-ascii

Attached is a quick patch to file off the N^2 loop in the subject+date
and sender+date case.  I'm actually amazed at how much faster the this
sort is now.  My 43K message folder went from a sort time of a minute or
a bit more down to a second or two.  It's now too fast for me to time it
by watching the "top" display and the performance is now very
acceptable.

I think the sort could be improved even more by making the sort data
persistent and updating it incrementally as new messages arrive.

I'm actually more interested in the threaded case, but that's too
complicated for me to attack in the time I have available right now. The
subject+date sort is OK for my big folders though.

If feels like time to declare victory and go to sleep.
--0-1804289383-1049701158=:4804
Content-Type: TEXT/plain; name=fast_sort
Content-Disposition: attachment; filename=fast_sort

--- lib/ratFolder.c.orig	Mon Apr 22 21:42:42 2002
+++ lib/ratFolder.c	Mon Apr  7 00:04:07 2003
@@ -673,7 +673,9 @@
     int i, j, k, pi, pj, snarf, numParm, seen, *tmpPtr, first, last,
 	*p=infoPtr->presentationOrder,
 	needDate=0, needSubject=0, needSender=0, needIds = 0, needSize = 0,
-	*uniqList, uniqListUsed, *subList, *lengthList;
+	*uniqList, uniqListUsed, *subList, *lengthList, newEntry;
+    Tcl_HashTable uniqTable;
+    Tcl_HashEntry *uniqEntry;
     SortData *dataPtr, *dPtr;
     Tcl_Obj *oPtr, *o2Ptr;
 
@@ -996,24 +998,25 @@
 	 * - Finally we build to result array.
 	 */
 	uniqList = (int*)ckalloc(2*infoPtr->number*sizeof(*uniqList));
+	Tcl_InitHashTable(&uniqTable, TCL_STRING_KEYS);
 	subList = &uniqList[infoPtr->number];
 	lengthList = &uniqList[2*infoPtr->number];
 	for (i=uniqListUsed=0; i<infoPtr->number; i++) {
-	    for (j=0; j<uniqListUsed; j++) {
-		if (infoPtr->sortOrder == SORT_SUBJDATE ?
-			!strcmp(dataPtr[i].subject,
-			dataPtr[uniqList[j]].subject) : !strcmp(
-			dataPtr[i].sender, dataPtr[uniqList[j]].sender)) {
-		    dataPtr[i].nextPtr = dataPtr[uniqList[j]].nextPtr;
-		    dataPtr[uniqList[j]].nextPtr = &dataPtr[i];
-		    break;
-		}
-	    }
-	    if (j == uniqListUsed) {
+	    uniqEntry = Tcl_CreateHashEntry(&uniqTable,
+				          infoPtr->sortOrder == SORT_SUBJDATE ?
+					  dataPtr[i].subject :
+					  dataPtr[i].sender, &newEntry);
+	    if (newEntry) {
 		dataPtr[i].nextPtr = NULL;
 		uniqList[uniqListUsed++] = i;
+		Tcl_SetHashValue(uniqEntry, &dataPtr[i]);
+	    } else {
+		dPtr = Tcl_GetHashValue(uniqEntry);
+		dataPtr[i].nextPtr = dPtr->nextPtr;
+		dPtr->nextPtr = &dataPtr[i];
 	    }
 	}
+	Tcl_DeleteHashTable(&uniqTable);
 	for (i=0; i<uniqListUsed; i++) {
 	    if (NULL != dataPtr[uniqList[i]].nextPtr) {
 		for (j = 0, dPtr = &dataPtr[uniqList[i]]; dPtr;

--0-1804289383-1049701158=:4804--