← Back to branch summary

~ubuntu-branches/ubuntu/quantal/lurker/quantal

« back to all changes in this revision

Viewing changes to render/Threading.cpp

  • Committer: Bazaar Package Importer
  • Author(s): Jonas Meurer
  • Date: 2004-09-26 16:27:51 UTC
  • Revision ID: james.westby@ubuntu.com-20040926162751-z1ohcjltv7ojtg6z
Tags: upstream-1.2
Import upstream version 1.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
render/Threading.cpp
 
1
/*  $Id: Threading.cpp,v 1.13 2004/08/24 21:52:39 terpstra Exp $
 
2
 *  
 
3
 *  Threading.h - Helper which can load a thread tree
 
4
 *  
 
5
 *  Copyright (C) 2002 - Wesley W. Terpstra
 
6
 *  
 
7
 *  License: GPL
 
8
 *  
 
9
 *  Authors: 'Wesley W. Terpstra' <wesley@terpstra.ca>
 
10
 *  
 
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.
 
14
 *    
 
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.
 
19
 *    
 
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
 
23
 */
 
24
 
 
25
#define _XOPEN_SOURCE 500
 
26
#define _FILE_OFFSET_BITS 64
 
27
 
 
28
#include "Threading.h"
 
29
#include <Keys.h>
 
30
#include <memory>
 
31
#include <cerrno>
 
32
#include <iostream>
 
33
#include <list>
 
34
 
 
35
#define DAY_GAP_FOR_NEW_THREAD  40
 
36
 
 
37
#define EMPTY_CELL      "<a/>"
 
38
#define BAR_NS          "<b/>"
 
39
#define BAR_EW          "<c/>"
 
40
#define CORNER_SW       "<d/>"
 
41
#define TEE_WSE         "<e/>"
 
42
 
 
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'
 
49
 
 
50
using namespace std;
 
51
using namespace ESort;
 
52
 
 
53
string Threading::load(Reader* r, const Summary& sum, Key& out)
 
54
{
 
55
        // dump any prior state
 
56
        hashes.clear();
 
57
        nodes.clear();
 
58
        
 
59
        string prefix = 
 
60
                LU_THREADING + 
 
61
                subject_hash(sum.subject().c_str());
 
62
        
 
63
        auto_ptr<Walker> backwards(r->seek(prefix, sum.id().raw(), Backward));
 
64
        
 
65
        /** Walk backwards until we find step off the subject, or there is
 
66
         *  a break of more than 40 days between messages.
 
67
         */
 
68
        MessageId root = sum.id();
 
69
        while (backwards->advance() != -1)
 
70
        {
 
71
                if (backwards->key.length() < prefix.length() + 8)
 
72
                        return "corrupt threading record -- too short";
 
73
                
 
74
                MessageId x(backwards->key.c_str() + prefix.length(), 1);
 
75
                if (x.timestamp() + 60*60*24*DAY_GAP_FOR_NEW_THREAD 
 
76
                        < root.timestamp())
 
77
                        break;
 
78
                
 
79
                root = x;
 
80
        }
 
81
        
 
82
        /** Ok, we have found what will be the root of the tree.
 
83
         *  Now, we shall seek and read the messages off. 
 
84
         */
 
85
        auto_ptr<Walker> forwards(r->seek(prefix, root.raw(), Forward));
 
86
        
 
87
        /* We read the nodes off in timestamp sorted order
 
88
         */
 
89
        std::list<Node> timestamp_sorted;
 
90
        
 
91
        /** Walk forwards until we find step off the subject, or there is
 
92
         *  a break of more than 40 days between messages.
 
93
         */
 
94
        MessageId prev = root;
 
95
        while (forwards->advance() != -1)
 
96
        {
 
97
                if (forwards->key.length() < prefix.length() + 8)
 
98
                        return "corrupt forwardthreading record -- too short";
 
99
                
 
100
                MessageId x(forwards->key.c_str() + prefix.length(), 1);
 
101
                
 
102
                if (prev.timestamp() + 60*60*24*DAY_GAP_FOR_NEW_THREAD 
 
103
                        < x.timestamp())
 
104
                        break;
 
105
                
 
106
                timestamp_sorted.push_back(Node(x));
 
107
                Node& b = timestamp_sorted.back();
 
108
                
 
109
                b.in_reply_tos.assign(
 
110
                        forwards->key.c_str() + prefix.length() + 8,
 
111
                        forwards->key.length() - prefix.length() - 8);
 
112
                
 
113
                // record that this hash does in fact exist
 
114
                hashes[b.summary.id().hash()] = -1;
 
115
                
 
116
                prev = x;
 
117
        }
 
118
        
 
119
        /** We now have all the messages in timestamp sorted order.
 
120
         *  Let's scan the list for the first message with no predecessor.
 
121
         */
 
122
        while (!timestamp_sorted.empty())
 
123
        {
 
124
                std::list<Node>::iterator i;
 
125
                
 
126
                for (i = timestamp_sorted.begin(); i != timestamp_sorted.end(); ++i)
 
127
                {
 
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)
 
131
                        
 
132
                        i->replyee = -1; // find best predecessor also
 
133
                        
 
134
                        string::size_type replyto;
 
135
                        for (replyto = 0; replyto+4 <= i->in_reply_tos.size(); replyto += 4)
 
136
                        {
 
137
                                map<string, int>::iterator r = hashes.find(
 
138
                                        i->in_reply_tos.substr(replyto, 4));
 
139
                                
 
140
                                if (r != hashes.end())
 
141
                                {
 
142
                                        if (r->second == -1)
 
143
                                        {       // still in the timestamp queue
 
144
                                                break;
 
145
                                        }
 
146
                                        else if (r->second > i->replyee)
 
147
                                        {       // an older predecessor
 
148
                                                i->replyee = r->second;
 
149
                                        }
 
150
                                }
 
151
                        }
 
152
                        
 
153
                        // Did we find no queued predecessors?
 
154
                        if (replyto+4 > i->in_reply_tos.size())
 
155
                                break;
 
156
                }
 
157
                
 
158
                // deal with cycles (theorectically impossible, but ...)
 
159
                if (i == timestamp_sorted.end()) i = timestamp_sorted.begin();
 
160
                
 
161
                hashes[i->summary.id().hash()] = nodes.size();
 
162
                nodes.push_back(*i);
 
163
                timestamp_sorted.erase(i);
 
164
                
 
165
                // prep the node
 
166
                Node& b = nodes.back();
 
167
                b.replies       = 0;
 
168
                b.replyor_first = -1;
 
169
                b.replyor_next  = -1;
 
170
                b.draw_next     = -1;
 
171
                b.depth         = nodes.size() - 1;
 
172
                b.consumed      = 0;
 
173
                
 
174
                if (b.replyee != -1)
 
175
                        nodes[b.replyee].replies++;
 
176
                
 
177
                // check for high-lighted node
 
178
                if (b.summary.id() == sum.id())
 
179
                        out = b.depth;
 
180
        }
 
181
        
 
182
        Node* tree = &nodes[0];
 
183
        
 
184
        /** Resolve back links
 
185
         */
 
186
        for (int i = nodes.size()-1; i > 0; i--)
 
187
        {
 
188
                int p = tree[i].replyee;
 
189
                if (p == -1) continue;
 
190
                                
 
191
                if (tree[p].depth < tree[i].depth)
 
192
                        tree[p].depth = tree[i].depth;
 
193
                
 
194
                /* Insertion sort is not that fast...
 
195
                 * But compared to the drawing algo, this n^2 is negligable.
 
196
                 */
 
197
                int* w = &tree[p].replyor_first;
 
198
                while (*w != -1 && tree[*w].depth > tree[i].depth)
 
199
                        w = &tree[*w].replyor_next;
 
200
                
 
201
                tree[i].replyor_next = *w;
 
202
                *w                   = i;
 
203
        }
 
204
        
 
205
        return "";
 
206
}
 
207
 
 
208
set<Summary> Threading::replies(Key k)
 
209
{
 
210
        set<Summary> out;
 
211
        for (int l = nodes[k].replyor_first; l != -1; l = nodes[l].replyor_next)
 
212
                out.insert(nodes[l].summary);
 
213
        return out;
 
214
}
 
215
 
 
216
Summary& Threading::getSummary(Key m)
 
217
{
 
218
        return nodes[m].summary;
 
219
}
 
220
 
 
221
void my_service_tree_message_link(
 
222
        ostream&                o,
 
223
        Threading::Node*        tree,
 
224
        int                     i,
 
225
        int                     hl)
 
226
{
 
227
        int  selected   = (hl == i);
 
228
//      int  drift      = 0; // !!! too bad I can't do this...
 
229
        char x;
 
230
        
 
231
        if (tree[i].replyee == -1)
 
232
        {
 
233
                switch (tree[i].replies)
 
234
                {
 
235
                case 0:  x = TOPMESSAGE_END;  break;
 
236
                case 1:  x = TOPMESSAGE_DOWN; break;
 
237
                default: x = TOPMESSAGE_BOTH; break;
 
238
                }
 
239
        }
 
240
        else
 
241
        {
 
242
                switch (tree[i].replies)
 
243
                {
 
244
                case 0:  x = MESSAGE_END;  break;
 
245
                case 1:  x = MESSAGE_DOWN; break;
 
246
                default: x = MESSAGE_BOTH; break;
 
247
                }
 
248
        }
 
249
        
 
250
        o << "<" << x;
 
251
        if (selected) o << " selected=\"yes\"";
 
252
        o << " id=\"" << tree[i].summary.id().serialize() << "\"/>";
 
253
}
 
254
 
 
255
int my_service_draw_tree(
 
256
        Threading::Node* tree,
 
257
        int n, int u)
 
258
{
 
259
        int i;
 
260
        int c;
 
261
        int col = 0;
 
262
        
 
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;
 
267
        
 
268
        tree[n].consumed = col;
 
269
        
 
270
        tree[n].column = col;
 
271
        for (c = tree[n].replyor_first; c != -1; c = tree[c].replyor_next)
 
272
        {
 
273
                col = my_service_draw_tree(tree, c, n); 
 
274
                for (i = n; i < c; i++)
 
275
                        tree[i].consumed = col+1;
 
276
        }
 
277
        
 
278
        return tree[n].column;
 
279
}
 
280
 
 
281
string Threading::draw_tree(Reader* db)
 
282
{
 
283
        Threading::Node* tree = &nodes[0];
 
284
        int tree_size = nodes.size();
 
285
        
 
286
        for (int i = 0; i < tree_size; ++i)
 
287
                if (tree[i].replyee == -1)
 
288
                        my_service_draw_tree(tree, i, i);
 
289
        
 
290
        return "";
 
291
}
 
292
 
 
293
void my_service_draw_tree_row(
 
294
        ostream&                o,
 
295
        Threading::Node*        tree,
 
296
        int* head, 
 
297
        int i)
 
298
{
 
299
        int     col, p;
 
300
        int*    w;
 
301
 
 
302
#ifdef DEBUG
 
303
        printf("\nOffset: %d", tree[i].column);
 
304
#endif
 
305
        
 
306
        col = 0;
 
307
        w = head;
 
308
        while (*w != -1)
 
309
        {
 
310
                for (; col < tree[*w].column; col++)
 
311
                        o << EMPTY_CELL;
 
312
                
 
313
                if (*w == i) break;
 
314
                
 
315
                o << BAR_NS;
 
316
                col++;
 
317
                w = &tree[*w].draw_next;
 
318
        }
 
319
        
 
320
        for (; col < tree[i].column; col++)
 
321
                o << EMPTY_CELL;
 
322
        
 
323
        my_service_tree_message_link(o, tree, i, -1);
 
324
        col++;
 
325
        
 
326
        /* Cut ourselves out of the list and graft on our
 
327
         * children. While we're at it, draw the links.
 
328
         */
 
329
        for (p = tree[i].replyor_first; p != -1; p = tree[p].replyor_next)
 
330
        {
 
331
                *w = p;
 
332
                w = &tree[p].draw_next;
 
333
                
 
334
                if (col > tree[p].column) continue;
 
335
                
 
336
                for (; col < tree[p].column; col++)
 
337
                        o << BAR_EW;
 
338
                col++;
 
339
                if (tree[p].replyor_next == -1)
 
340
                        o << CORNER_SW;
 
341
                else    o << TEE_WSE;
 
342
        }
 
343
        *w = tree[i].draw_next;
 
344
        
 
345
        /* Continue drawing the other children */
 
346
        for (p = *w; p != -1; p = tree[p].draw_next)
 
347
        {
 
348
                for (; col < tree[p].column; col++)
 
349
                        o << EMPTY_CELL;
 
350
                col++;
 
351
                o << BAR_NS;
 
352
        }
 
353
}
 
354
 
 
355
void Threading::draw_tree_row(ostream& o, int* h, Key row)
 
356
{
 
357
        my_service_draw_tree_row(o, &nodes[0], h, row);
 
358
}
 
359
 
 
360
int my_service_draw_snippet(
 
361
        ESort::Reader*  db,
 
362
        Threading::Node* tree,
 
363
        int p, 
 
364
        int row,
 
365
        string& out,
 
366
        int num,
 
367
        const Config& cfg)
 
368
{
 
369
        int col;
 
370
        int c;
 
371
        bool dangle_reply = false;
 
372
        
 
373
        col = tree[p].column = tree[p].consumed;
 
374
        
 
375
        if (row < 3)
 
376
        {
 
377
                out = tree[p].summary.load(db, cfg);
 
378
                if (out != "") return -1;
 
379
                
 
380
                for (c = tree[p].replyor_first; c != -1; c = tree[c].replyor_next)
 
381
                {
 
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;
 
385
                }
 
386
                
 
387
                if (p+1 < num && tree[p+1].replyee == -1)
 
388
                { // draw it as though it were a child
 
389
                        dangle_reply = true;
 
390
                        c = p+1;
 
391
                        
 
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;
 
395
                }
 
396
        }
 
397
        
 
398
        if ((tree[p].replyor_first == -1 && !dangle_reply) || row >= 3) col++;
 
399
        
 
400
        return col;
 
401
}
 
402
 
 
403
int my_service_pick_p(Threading::Node* tree, int root, int num)
 
404
{
 
405
        int p = root;
 
406
        
 
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)
 
412
                        p = tree[p].replyee;
 
413
                else if (p != 0)
 
414
                        p = p - 1; // use the dangling replyee trick
 
415
        }
 
416
        
 
417
        // always move up at least one row if we can
 
418
        if (tree[p].replyee != -1)
 
419
                p = tree[p].replyee;
 
420
        else if (p != 0)
 
421
                p = p - 1; // use dangling replyee trick
 
422
        
 
423
        return p;
 
424
}
 
425
 
 
426
string Threading::draw_snippet(ESort::Reader* db, Key root, const Config& cfg)
 
427
{
 
428
        Threading::Node* tree = &nodes[0];
 
429
        string out;
 
430
        my_service_draw_snippet(db, tree, 
 
431
                my_service_pick_p(tree, root, nodes.size()), 
 
432
                0, out, nodes.size(), cfg);
 
433
        return out;
 
434
}
 
435
 
 
436
void my_service_draw_snippet_row(
 
437
        ostream&                o,
 
438
        Threading::Node*        tree,
 
439
        int* draw_head, 
 
440
        int row,
 
441
        int hl,
 
442
        int num)
 
443
{
 
444
        int     p;
 
445
        int     c;
 
446
        int     col = 0;
 
447
 
 
448
        /* First, draw the current row */
 
449
        for (p = *draw_head; p != -1; p = tree[p].draw_next)
 
450
        {
 
451
                for (; col < tree[p].column; col++)
 
452
                        o << EMPTY_CELL;
 
453
                
 
454
                
 
455
                my_service_tree_message_link(o, tree, p, hl);
 
456
                col++;
 
457
                
 
458
                /* Now, inject our children in place.
 
459
                 * Also, draw the stuff down to them.
 
460
                 */
 
461
                for (c = tree[p].replyor_first; c != -1; c = tree[c].replyor_next)
 
462
                {
 
463
                        *draw_head = c;
 
464
                        draw_head = &tree[c].draw_next;
 
465
                        
 
466
                        if (c == tree[p].replyor_first)
 
467
                                continue;
 
468
                        
 
469
                        for (; col < tree[c].column; col++)
 
470
                                o << BAR_EW;
 
471
                        
 
472
                        if (tree[c].replyor_next == -1)
 
473
                                o << CORNER_SW;
 
474
                        else    o << TEE_WSE;
 
475
                        col++;
 
476
                }
 
477
                
 
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
 
481
                        *draw_head = p+1;
 
482
                        draw_head = &tree[p+1].draw_next;
 
483
                }
 
484
        }
 
485
        
 
486
        /* Terminate the list */
 
487
        *draw_head = -1;
 
488
}
 
489
 
 
490
void Threading::draw_snippet_row(ostream& o, int* h, Key row, Key root)
 
491
{
 
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());
 
495
}
 
496
 
 
497
string Threading::findprev(Key m, ESort::Reader* r, const Config& cfg, Summary& s)
 
498
{
 
499
        string ok;
 
500
        
 
501
        Key i = m;
 
502
        while (1)
 
503
        {
 
504
                if (i == 0)
 
505
                {
 
506
                        s = nodes[m].summary;
 
507
                        return "";
 
508
                }
 
509
                --i;
 
510
                
 
511
                if (!nodes[i].summary.loaded() && 
 
512
                    (ok = nodes[i].summary.load(r, cfg)) != "")
 
513
                        return ok;
 
514
                
 
515
                if (!nodes[i].summary.deleted())
 
516
                {
 
517
                        s = nodes[i].summary;
 
518
                        return "";
 
519
                }
 
520
        }
 
521
}
 
522
 
 
523
string Threading::findnext(Key m, ESort::Reader* r, const Config& cfg, Summary& s)
 
524
{
 
525
        string ok;
 
526
        
 
527
        
 
528
        Key i = m;
 
529
        while (1)
 
530
        {
 
531
                ++i;
 
532
                if (i == nodes.size())
 
533
                {
 
534
                        s = nodes[m].summary;
 
535
                        return "";
 
536
                }
 
537
                
 
538
                if (!nodes[i].summary.loaded() && 
 
539
                    (ok = nodes[i].summary.load(r, cfg)) != "")
 
540
                        return ok;
 
541
                
 
542
                if (!nodes[i].summary.deleted())
 
543
                {
 
544
                        s = nodes[i].summary;
 
545
                        return "";
 
546
                }
 
547
        }
 
548
}