From: short <>
Date: Tue, 14 Oct 2003 19:26:09 +0000 (+0000)
Subject: +muttsort
X-Git-Url: http://git.jankratochvil.net/?p=www.jankratochvil.net.git;a=commitdiff_plain;h=917afdca0e314198aabacd8f828c01d98ac9dd1d

+muttsort
---

diff --git a/configure.ac b/configure.ac
index c003d6e..8a41535 100644
--- a/configure.ac
+++ b/configure.ac
@@ -97,6 +97,7 @@ Makefile
 ./project/pgsqlsubstr/Makefile
 ./project/int13sniff/Makefile
 ./project/libtool/Makefile
+./project/muttsort/Makefile
 ])
 
 echo done.
diff --git a/project/Makefile.am b/project/Makefile.am
index c6e3047..9dc5d9b 100644
--- a/project/Makefile.am
+++ b/project/Makefile.am
@@ -79,7 +79,8 @@ SUBDIRS= \
 		MyWeb           \
 		pgsqlsubstr     \
 		int13sniff      \
-		libtool
+		libtool         \
+		muttsort
 
 EXTRA_DIST+= \
 		Index.html.pl \
diff --git a/project/muttsort/Index.html.pl b/project/muttsort/Index.html.pl
new file mode 100755
index 0000000..229ee2c
--- /dev/null
+++ b/project/muttsort/Index.html.pl
@@ -0,0 +1,45 @@
+#! /usr/bin/perl
+# 
+# $Id$
+# Main page of 'My::Project::muttsort'
+# Copyright (C) 2003 Jan Kratochvil <project-www.jankratochvil.net@jankratochvil.net>
+# 
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; exactly version 2 of June 1991 is required
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+
+package project::muttsort::Index;
+require 5.6.0;	# at least 'use warnings;' but we need some 5.6.0+ modules anyway
+our $VERSION=do { my @r=(q$Revision$=~/\d+/g); sprintf "%d.".("%03d"x$#r),@r; };
+our $CVS_ID=q$Id$;
+use strict;
+use warnings;
+
+BEGIN{ open F,"Makefile"; our $top_dir=pop @{[split /\s/,(grep /^top_srcdir/,<F>)[0]]}; eval "use lib '$top_dir'"; close F; }
+use My::Web;
+Wuse 'My::Project';
+Wuse 'project::muttsort::ListItem';
+
+
+My::Project->init_project(
+		"__PACKAGE__"=>__PACKAGE__,
+		"ListItem"=>\@project::muttsort::ListItem::ListItem,
+		);
+
+
+print <<"HERE";
+<p>Patch got integrated to <b>thread.c</b>, revision <b>2.16</b>.</p>
+HERE
+
+
+My::Web->footer();
diff --git a/project/muttsort/ListItem.pm b/project/muttsort/ListItem.pm
new file mode 100755
index 0000000..2512f85
--- /dev/null
+++ b/project/muttsort/ListItem.pm
@@ -0,0 +1,47 @@
+#! /usr/bin/perl
+# 
+# $Id$
+# Definition of 'My::Project::muttsort' for list.cgi.pl
+# Copyright (C) 2003 Jan Kratochvil <project-www.jankratochvil.net@jankratochvil.net>
+# 
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; exactly version 2 of June 1991 is required
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+
+package project::muttsort::ListItem;
+require 5.6.0;	# at least 'use warnings;' but we need some 5.6.0+ modules anyway
+our $VERSION=do { my @r=(q$Revision$=~/\d+/g); sprintf "%d.".("%03d"x$#r),@r; };
+our $CVS_ID=q$Id$;
+use strict;
+use warnings;
+
+use My::Web;
+
+
+our @ListItem=(
+		"name"=>a_href('http://www.mutt.org/','Mutt').' speedup',
+		"platform"=>"patch",
+		"priority"=>5,
+		"summary"=>'Mailbox reading phase acceleration',
+		"download-patch"=>'mutt-sort.diff',
+		"license"=>"GPL",
+		"maintenance"=>"accepted",
+		"language"=>"C patch",
+		"description"=><<"HERE",
+<p>Mutt is pretty slow when opening a mailbox. Phase "Reading..." is hard to
+speedup but "Sorting mailbox..." was rewritten from <i>(n^2)</i> complexity
+to <i>(n*log(n))</i>.
+HERE
+		);
+
+1;
diff --git a/project/muttsort/Makefile.am b/project/muttsort/Makefile.am
new file mode 100644
index 0000000..7d61eaf
--- /dev/null
+++ b/project/muttsort/Makefile.am
@@ -0,0 +1,23 @@
+# $Id$
+# automake source for the Makefile of project/muttsort/ subdir
+# Copyright (C) 2003 Jan Kratochvil <project-www.jankratochvil.net@jankratochvil.net>
+# 
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; exactly version 2 of June 1991 is required
+# 
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
+# 
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software
+# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+
+include $(top_srcdir)/Makefile-head.am
+
+EXTRA_DIST+= \
+	ListItem.pm \
+	Index.html.pl
diff --git a/project/muttsort/mutt-sort.diff b/project/muttsort/mutt-sort.diff
new file mode 100644
index 0000000..51bb02e
--- /dev/null
+++ b/project/muttsort/mutt-sort.diff
@@ -0,0 +1,109 @@
+Index: thread.c
+===================================================================
+RCS file: /home/roessler/cvs/mutt/thread.c,v
+retrieving revision 2.15
+diff -I! -ICVS -u -r2.15 thread.c
+--- thread.c	2001/04/25 22:08:41	2.15
++++ thread.c	2001/07/26 02:18:11
+@@ -535,23 +535,48 @@
+ 
+ HEADER *mutt_sort_subthreads (HEADER *hdr, sort_t *func)
+ {
+-  HEADER *top = NULL;
+-  HEADER *t;
++  static HEADER **array = NULL;
++  static unsigned array_size = 0, array_alloc = 0;
++  unsigned array_alloc_base;
++  unsigned items, item;
+   
+-  while (hdr)
++  if (!func || !hdr)
++    return hdr;
++
++  array_alloc_base = array_alloc;
++  for (item = array_alloc_base; hdr; hdr = hdr->next)
+   {
+-    t = hdr;
+-    hdr = hdr->next;
+-    insert_message (&top, t, func);
+-    if (t->child)
+-      t->child = mutt_sort_subthreads (t->child, func);
++    if (item >= array_size)
++    {
++      array_size = 2 * MAX(array_size, 0x100);
++      safe_realloc ((void **) &array, array_size * sizeof (*array));
++    }
++    array[item++] = hdr;
++    if (hdr->child)
++    {
++      array_alloc = item;
++      hdr->child = mutt_sort_subthreads (hdr->child, func);
++    }
+   }
+-  return top;
++  array_alloc = array_alloc_base;
++
++  items = item - array_alloc_base;
++  qsort ((void *) (array + array_alloc_base), items, sizeof (*array), func);
++
++  array[array_alloc_base          ]->prev = NULL;
++  array[array_alloc_base + items-1]->next = NULL;
++
++  for (item = array_alloc_base; item < array_alloc_base + items-1; item++)
++  {
++    array[item  ]->next = array[item+1];
++    array[item+1]->prev = array[item  ];
++  }
++
++  return array[array_alloc_base];
+ }
+ 
+ void mutt_sort_threads (CONTEXT *ctx, int init)
+ {
+-  sort_t *usefunc = NULL;
+   HEADER *tmp, *CUR;
+   int i, oldsort;
+   
+@@ -562,10 +587,6 @@
+   oldsort = Sort;
+   Sort = SortAux;
+   
+-  /* if the SORT_LAST bit is set, we save sorting for later */
+-  if (!(Sort & SORT_LAST))
+-    usefunc = mutt_get_sort_func (Sort);
+-
+   for (i = 0; i < ctx->msgcount; i++)
+   {
+     CUR = ctx->hdrs[i];
+@@ -580,7 +601,7 @@
+       CUR->subject_changed = 1;
+       unlink_message (&CUR->parent->child, CUR);
+       CUR->parent = NULL;
+-      insert_message (&ctx->tree, CUR, usefunc);
++      insert_message (&ctx->tree, CUR, NULL);
+     }
+     else if (!CUR->threaded)
+     {
+@@ -603,15 +624,19 @@
+ 	 * parent) during the initial threading.
+ 	 */
+ 	if (CUR->env->message_id)
+-	  move_descendants (tmp ? &tmp->child : &ctx->tree, CUR, usefunc);
++	  move_descendants (tmp ? &tmp->child : &ctx->tree, CUR, NULL);
+       }
+-      insert_message (tmp ? &tmp->child : &ctx->tree, CUR, usefunc);
++      insert_message (tmp ? &tmp->child : &ctx->tree, CUR, NULL);
+       CUR->threaded = 1;
+     }
+   }
+ 
+   if (!option (OPTSTRICTTHREADS))
+-    pseudo_threads (ctx, usefunc);
++    pseudo_threads (ctx, NULL);
++
++  /* if the SORT_LAST bit is not set, sort the whole tree now */
++  if (!(Sort & SORT_LAST))
++    ctx->tree = mutt_sort_subthreads (ctx->tree, mutt_get_sort_func (Sort));
+ 
+   /* now that the whole tree is put together, we can sort by last-* */
+   if (Sort & SORT_LAST)