1
/* $Id: Threading.cpp,v 1.13 2004/08/24 21:52:39 terpstra Exp $
3
* Threading.h - Helper which can load a thread tree
5
* Copyright (C) 2002 - Wesley W. Terpstra
9
* Authors: 'Wesley W. Terpstra' <wesley@terpstra.ca>
11
* This program is free software; you can redistribute it and/or modify
12
* it under the terms of the GNU General Public License as published by
13
* the Free Software Foundation; version 2.
15
* This program is distributed in the hope that it will be useful,
16
* but WITHOUT ANY WARRANTY; without even the implied warranty of
17
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18
* GNU General Public License for more details.
20
* You should have received a copy of the GNU General Public License
21
* along with this program; if not, write to the Free Software
22
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25
#define _XOPEN_SOURCE 500
26
#define _FILE_OFFSET_BITS 64
28
#include "Threading.h"
35
#define DAY_GAP_FOR_NEW_THREAD 40
37
#define EMPTY_CELL "<a/>"
40
#define CORNER_SW "<d/>"
41
#define TEE_WSE "<e/>"
43
#define MESSAGE_END 'f'
44
#define MESSAGE_DOWN 'g'
45
#define MESSAGE_BOTH 'h'
46
#define TOPMESSAGE_END 'i'
47
#define TOPMESSAGE_DOWN 'j'
48
#define TOPMESSAGE_BOTH 'k'
51
using namespace ESort;
53
string Threading::load(Reader* r, const Summary& sum, Key& out)
55
// dump any prior state
61
subject_hash(sum.subject().c_str());
63
auto_ptr<Walker> backwards(r->seek(prefix, sum.id().raw(), Backward));
65
/** Walk backwards until we find step off the subject, or there is
66
* a break of more than 40 days between messages.
68
MessageId root = sum.id();
69
while (backwards->advance() != -1)
71
if (backwards->key.length() < prefix.length() + 8)
72
return "corrupt threading record -- too short";
74
MessageId x(backwards->key.c_str() + prefix.length(), 1);
75
if (x.timestamp() + 60*60*24*DAY_GAP_FOR_NEW_THREAD
82
/** Ok, we have found what will be the root of the tree.
83
* Now, we shall seek and read the messages off.
85
auto_ptr<Walker> forwards(r->seek(prefix, root.raw(), Forward));
87
/* We read the nodes off in timestamp sorted order
89
std::list<Node> timestamp_sorted;
91
/** Walk forwards until we find step off the subject, or there is
92
* a break of more than 40 days between messages.
94
MessageId prev = root;
95
while (forwards->advance() != -1)
97
if (forwards->key.length() < prefix.length() + 8)
98
return "corrupt forwardthreading record -- too short";
100
MessageId x(forwards->key.c_str() + prefix.length(), 1);
102
if (prev.timestamp() + 60*60*24*DAY_GAP_FOR_NEW_THREAD
106
timestamp_sorted.push_back(Node(x));
107
Node& b = timestamp_sorted.back();
109
b.in_reply_tos.assign(
110
forwards->key.c_str() + prefix.length() + 8,
111
forwards->key.length() - prefix.length() - 8);
113
// record that this hash does in fact exist
114
hashes[b.summary.id().hash()] = -1;
119
/** We now have all the messages in timestamp sorted order.
120
* Let's scan the list for the first message with no predecessor.
122
while (!timestamp_sorted.empty())
124
std::list<Node>::iterator i;
126
for (i = timestamp_sorted.begin(); i != timestamp_sorted.end(); ++i)
128
// scan all the in_reply_tos. if none of them are left
129
// in timestamp_sorted, then this should come next.
130
// (ie: no predecessors and lowest timestamp)
132
i->replyee = -1; // find best predecessor also
134
string::size_type replyto;
135
for (replyto = 0; replyto+4 <= i->in_reply_tos.size(); replyto += 4)
137
map<string, int>::iterator r = hashes.find(
138
i->in_reply_tos.substr(replyto, 4));
140
if (r != hashes.end())
143
{ // still in the timestamp queue
146
else if (r->second > i->replyee)
147
{ // an older predecessor
148
i->replyee = r->second;
153
// Did we find no queued predecessors?
154
if (replyto+4 > i->in_reply_tos.size())
158
// deal with cycles (theorectically impossible, but ...)
159
if (i == timestamp_sorted.end()) i = timestamp_sorted.begin();
161
hashes[i->summary.id().hash()] = nodes.size();
163
timestamp_sorted.erase(i);
166
Node& b = nodes.back();
168
b.replyor_first = -1;
171
b.depth = nodes.size() - 1;
175
nodes[b.replyee].replies++;
177
// check for high-lighted node
178
if (b.summary.id() == sum.id())
182
Node* tree = &nodes[0];
184
/** Resolve back links
186
for (int i = nodes.size()-1; i > 0; i--)
188
int p = tree[i].replyee;
189
if (p == -1) continue;
191
if (tree[p].depth < tree[i].depth)
192
tree[p].depth = tree[i].depth;
194
/* Insertion sort is not that fast...
195
* But compared to the drawing algo, this n^2 is negligable.
197
int* w = &tree[p].replyor_first;
198
while (*w != -1 && tree[*w].depth > tree[i].depth)
199
w = &tree[*w].replyor_next;
201
tree[i].replyor_next = *w;
208
set<Summary> Threading::replies(Key k)
211
for (int l = nodes[k].replyor_first; l != -1; l = nodes[l].replyor_next)
212
out.insert(nodes[l].summary);
216
Summary& Threading::getSummary(Key m)
218
return nodes[m].summary;
221
void my_service_tree_message_link(
223
Threading::Node* tree,
227
int selected = (hl == i);
228
// int drift = 0; // !!! too bad I can't do this...
231
if (tree[i].replyee == -1)
233
switch (tree[i].replies)
235
case 0: x = TOPMESSAGE_END; break;
236
case 1: x = TOPMESSAGE_DOWN; break;
237
default: x = TOPMESSAGE_BOTH; break;
242
switch (tree[i].replies)
244
case 0: x = MESSAGE_END; break;
245
case 1: x = MESSAGE_DOWN; break;
246
default: x = MESSAGE_BOTH; break;
251
if (selected) o << " selected=\"yes\"";
252
o << " id=\"" << tree[i].summary.id().serialize() << "\"/>";
255
int my_service_draw_tree(
256
Threading::Node* tree,
263
/* Find the column we can use. */
264
for (i = u; i <= tree[n].depth; i++)
265
if (col < tree[i].consumed)
266
col = tree[i].consumed;
268
tree[n].consumed = col;
270
tree[n].column = col;
271
for (c = tree[n].replyor_first; c != -1; c = tree[c].replyor_next)
273
col = my_service_draw_tree(tree, c, n);
274
for (i = n; i < c; i++)
275
tree[i].consumed = col+1;
278
return tree[n].column;
281
string Threading::draw_tree(Reader* db)
283
Threading::Node* tree = &nodes[0];
284
int tree_size = nodes.size();
286
for (int i = 0; i < tree_size; ++i)
287
if (tree[i].replyee == -1)
288
my_service_draw_tree(tree, i, i);
293
void my_service_draw_tree_row(
295
Threading::Node* tree,
303
printf("\nOffset: %d", tree[i].column);
310
for (; col < tree[*w].column; col++)
317
w = &tree[*w].draw_next;
320
for (; col < tree[i].column; col++)
323
my_service_tree_message_link(o, tree, i, -1);
326
/* Cut ourselves out of the list and graft on our
327
* children. While we're at it, draw the links.
329
for (p = tree[i].replyor_first; p != -1; p = tree[p].replyor_next)
332
w = &tree[p].draw_next;
334
if (col > tree[p].column) continue;
336
for (; col < tree[p].column; col++)
339
if (tree[p].replyor_next == -1)
343
*w = tree[i].draw_next;
345
/* Continue drawing the other children */
346
for (p = *w; p != -1; p = tree[p].draw_next)
348
for (; col < tree[p].column; col++)
355
void Threading::draw_tree_row(ostream& o, int* h, Key row)
357
my_service_draw_tree_row(o, &nodes[0], h, row);
360
int my_service_draw_snippet(
362
Threading::Node* tree,
371
bool dangle_reply = false;
373
col = tree[p].column = tree[p].consumed;
377
out = tree[p].summary.load(db, cfg);
378
if (out != "") return -1;
380
for (c = tree[p].replyor_first; c != -1; c = tree[c].replyor_next)
382
tree[c].consumed = col;
383
col = my_service_draw_snippet(db, tree, c, row+1, out, num, cfg);
384
if (col == -1) return -1;
387
if (p+1 < num && tree[p+1].replyee == -1)
388
{ // draw it as though it were a child
392
tree[c].consumed = col;
393
col = my_service_draw_snippet(db, tree, c, row+1, out, num, cfg);
394
if (col == -1) return -1;
398
if ((tree[p].replyor_first == -1 && !dangle_reply) || row >= 3) col++;
403
int my_service_pick_p(Threading::Node* tree, int root, int num)
407
// If we have nothing which is drawn below us move up an extra step
408
if (tree[p].replyor_first == -1 &&
409
(p+1 >= num || tree[p+1].replyee != -1))
410
{ // we have no children and we have no dangling replyee
411
if (tree[p].replyee != -1)
414
p = p - 1; // use the dangling replyee trick
417
// always move up at least one row if we can
418
if (tree[p].replyee != -1)
421
p = p - 1; // use dangling replyee trick
426
string Threading::draw_snippet(ESort::Reader* db, Key root, const Config& cfg)
428
Threading::Node* tree = &nodes[0];
430
my_service_draw_snippet(db, tree,
431
my_service_pick_p(tree, root, nodes.size()),
432
0, out, nodes.size(), cfg);
436
void my_service_draw_snippet_row(
438
Threading::Node* tree,
448
/* First, draw the current row */
449
for (p = *draw_head; p != -1; p = tree[p].draw_next)
451
for (; col < tree[p].column; col++)
455
my_service_tree_message_link(o, tree, p, hl);
458
/* Now, inject our children in place.
459
* Also, draw the stuff down to them.
461
for (c = tree[p].replyor_first; c != -1; c = tree[c].replyor_next)
464
draw_head = &tree[c].draw_next;
466
if (c == tree[p].replyor_first)
469
for (; col < tree[c].column; col++)
472
if (tree[c].replyor_next == -1)
478
// Check if the next message after p has no in-reply-to
479
if (p+1 < num && tree[p+1].replyee == -1)
480
{ // draw it as though it were a child
482
draw_head = &tree[p+1].draw_next;
486
/* Terminate the list */
490
void Threading::draw_snippet_row(ostream& o, int* h, Key row, Key root)
492
Threading::Node* tree = &nodes[0];
493
if (*h == -2) *h = my_service_pick_p(tree, root, nodes.size());
494
my_service_draw_snippet_row(o, tree, h, row, root, nodes.size());
497
string Threading::findprev(Key m, ESort::Reader* r, const Config& cfg, Summary& s)
506
s = nodes[m].summary;
511
if (!nodes[i].summary.loaded() &&
512
(ok = nodes[i].summary.load(r, cfg)) != "")
515
if (!nodes[i].summary.deleted())
517
s = nodes[i].summary;
523
string Threading::findnext(Key m, ESort::Reader* r, const Config& cfg, Summary& s)
532
if (i == nodes.size())
534
s = nodes[m].summary;
538
if (!nodes[i].summary.loaded() &&
539
(ok = nodes[i].summary.load(r, cfg)) != "")
542
if (!nodes[i].summary.deleted())
544
s = nodes[i].summary;