From 30100c46326e2eac275e0af13116636701d2537e Mon Sep 17 00:00:00 2001
From: Eric Wong <e@80x24.org>
Date: Wed, 5 Oct 2016 23:47:29 +0000
Subject: thread: use hash + array instead of hand-rolled linked list

This starts to show noticeable performance improvements when
attempting to thread over 400 messages; but the improvement
may not be measurable with less.

However, the resulting code is much shorter and (IMHO)
much easier to understand.
---
 t/thread-cycle.t | 86 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 86 insertions(+)
 create mode 100644 t/thread-cycle.t

(limited to 't')

diff --git a/t/thread-cycle.t b/t/thread-cycle.t
new file mode 100644
index 00000000..4d60f7e3
--- /dev/null
+++ b/t/thread-cycle.t
@@ -0,0 +1,86 @@
+# Copyright (C) 2016 all contributors <meta@public-inbox.org>
+# License: AGPL-3.0+ <https://www.gnu.org/licenses/agpl-3.0.txt>
+use strict;
+use warnings;
+use Test::More;
+use_ok('PublicInbox::SearchMsg');
+use_ok('PublicInbox::SearchThread');
+use Email::Simple;
+my $mt = eval {
+	require Mail::Thread;
+	no warnings 'once';
+	$Mail::Thread::nosubject = 1;
+	$Mail::Thread::noprune = 1;
+};
+my @check;
+my @msgs = map {
+	my $msg = $_;
+	$msg->{references} =~ s/\s+/ /sg if $msg->{references};
+	my $simple = Email::Simple->create(header => [
+		'Message-Id' => "<$msg->{mid}>",
+		'References' => $msg->{references},
+	]);
+	push @check, $simple;
+	bless $msg, 'PublicInbox::SearchMsg'
+} (
+
+# data from t/testbox-6 in Mail::Thread 2.55:
+	{ mid => '20021124145312.GA1759@nlin.net' },
+	{ mid => 'slrnau448m.7l4.markj+0111@cloaked.freeserve.co.uk',
+	  references => '<20021124145312.GA1759@nlin.net>',
+	},
+	{ mid => '15842.10677.577458.656565@jupiter.akutech-local.de',
+	  references => '<20021124145312.GA1759@nlin.net>
+			<slrnau448m.7l4.markj+0111@cloaked.freeserve.co.uk>',
+	},
+	{ mid => '20021125171807.GK8236@somanetworks.com',
+	  references => '<20021124145312.GA1759@nlin.net>
+			<slrnau448m.7l4.markj+0111@cloaked.freeserve.co.uk>
+			<15842.10677.577458.656565@jupiter.akutech-local.de>',
+	},
+	{ mid => '15843.12163.554914.469248@jupiter.akutech-local.de',
+	  references => '<20021124145312.GA1759@nlin.net>
+			<slrnau448m.7l4.markj+0111@cloaked.freeserve.co.uk>
+			<15842.10677.577458.656565@jupiter.akutech-local.de>
+			<E18GPHf-0000zp-00@cloaked.freeserve.co.uk>',
+	},
+	{ mid => 'E18GPHf-0000zp-00@cloaked.freeserve.co.uk',
+	  references => '<20021124145312.GA1759@nlin.net>
+			<slrnau448m.7l4.markj+0111@cloaked.freeserve.co.uk>
+			<15842.10677.577458.656565@jupiter.akutech-local.de>'
+	}
+);
+
+my $th = PublicInbox::SearchThread->new(\@msgs);
+$th->thread;
+$th->order(sub { [ sort { $a->{id} cmp $b->{id} } @{$_[0]} ] });
+my $st = '';
+my @q = map { (0, $_) } @{$th->{rootset}};
+while (@q) {
+	my $level = shift @q;
+	my $node = shift @q or next;
+	$st .= (" "x$level). "$node->{id}\n";
+	my $cl = $level + 1;
+	unshift @q, map { ($cl, $_) } @{$node->{children}}
+}
+
+SKIP: {
+	skip 'Mail::Thread missing', 1 unless $mt;
+	$mt = Mail::Thread->new(@check);
+	$mt->thread;
+	$mt->order(sub { sort { $a->messageid cmp $b->messageid } @_ });
+	my $check = '';
+
+	@q = map { (0, $_) } $mt->rootset;
+	while (@q) {
+		my $level = shift @q;
+		my $node = shift @q or next;
+		$check .= (" "x$level) . $node->messageid . "\n";
+		unshift @q, $level + 1, $node->child, $level, $node->next;
+	}
+	is($check, $st, 'Mail::Thread output matches');
+}
+
+done_testing();
+
+1;
-- 
cgit v1.2.3-24-ge0c7