rfc822/imaprefs.c

   1 /*
   2 ** Copyright 2000-2003 Double Precision, Inc.
   3 ** See COPYING for distribution information.
   4 */
   5
   6 /*
   7 ** $Id: imaprefs.c,v 1.12 2009/11/22 19:39:52 mrsam Exp $
   8 */
   9
  10 #include        "config.h"
  11
  12 #include        <stdio.h>
  13 #include        <stdlib.h>
  14 #include        <string.h>
  15 #include        <time.h>
  16
  17 #include        "rfc822.h"
  18 #include        "imaprefs.h"
  19
  20 static void swapmsgdata(struct imap_refmsg *a, struct imap_refmsg *b)
  21 {
  22         char *cp;
  23         char c;
  24         time_t t;
  25         unsigned long ul;
  26
  27 #define swap(a,b,tmp) (tmp)=(a); (a)=(b); (b)=(tmp);
  28
  29         swap(a->msgid, b->msgid, cp);
  30         swap(a->isdummy, b->isdummy, c);
  31         swap(a->flag2, b->flag2, c);
  32
  33         swap(a->timestamp, b->timestamp, t);
  34         swap(a->seqnum, b->seqnum, ul);
  35
  36 #undef  swap
  37 }
  38
  39 struct imap_refmsgtable *rfc822_threadalloc()
  40 {
  41 struct imap_refmsgtable *p;
  42
  43         p=(struct imap_refmsgtable *)malloc(sizeof(struct imap_refmsgtable));
  44         if (p)
  45                 memset(p, 0, sizeof(*p));
  46         return (p);
  47 }
  48
  49 void rfc822_threadfree(struct imap_refmsgtable *p)
  50 {
  51 int i;
  52 struct imap_refmsghash *h;
  53 struct imap_subjlookup *s;
  54 struct imap_refmsg *m;
  55
  56         for (i=0; i<sizeof(p->hashtable)/sizeof(p->hashtable[0]); i++)
  57                 while ((h=p->hashtable[i]) != 0)
  58                 {
  59                         p->hashtable[i]=h->nexthash;
  60                         free(h);
  61                 }
  62
  63         for (i=0; i<sizeof(p->subjtable)/sizeof(p->subjtable[0]); i++)
  64                 while ((s=p->subjtable[i]) != 0)
  65                 {
  66                         p->subjtable[i]=s->nextsubj;
  67                         free(s->subj);
  68                         free(s);
  69                 }
  70
  71         while ((m=p->firstmsg) != 0)
  72         {
  73                 p->firstmsg=m->next;
  74                 if (m->subj)
  75                         free(m->subj);
  76                 free(m);
  77         }
  78         free(p);
  79 }
  80
  81 static int hashmsgid(const char *msgid)
  82 {
  83 unsigned long hashno=0;
  84
  85         while (*msgid)
  86         {
  87         unsigned long n= (hashno << 1);
  88
  89 #define HMIDS   (((struct imap_refmsgtable *)0)->hashtable)
  90 #define HHMIDSS ( sizeof(HMIDS) / sizeof( HMIDS[0] ))
  91
  92                 if (hashno & HHMIDSS )
  93                         n ^= 1;
  94
  95                 hashno= n ^ (unsigned char)*msgid++;
  96         }
  97
  98         return (hashno % HHMIDSS);
  99 }
 100
 101 struct imap_refmsg *rfc822_threadallocmsg(struct imap_refmsgtable *mt,
 102                                           const char *msgid)
 103 {
 104 int n=hashmsgid(msgid);
 105 struct imap_refmsg *msgp= (struct imap_refmsg *)
 106         malloc(sizeof(struct imap_refmsg)+1+strlen(msgid));
 107 struct imap_refmsghash *h, **hp;
 108
 109         if (!msgp)      return (0);
 110         memset(msgp, 0, sizeof(*msgp));
 111         strcpy ((msgp->msgid=(char *)(msgp+1)), msgid);
 112
 113         h=(struct imap_refmsghash *)malloc(sizeof(struct imap_refmsghash));
 114         if (!h)
 115         {
 116                 free(msgp);
 117                 return (0);
 118         }
 119
 120         for (hp= &mt->hashtable[n]; *hp; hp= & (*hp)->nexthash)
 121         {
 122                 if (strcmp( (*hp)->msg->msgid, msgp->msgid) > 0)
 123                         break;
 124         }
 125
 126         h->nexthash= *hp;
 127         *hp=h;
 128         h->msg=msgp;
 129
 130         msgp->last=mt->lastmsg;
 131
 132         if (mt->lastmsg)
 133                 mt->lastmsg->next=msgp;
 134         else
 135                 mt->firstmsg=msgp;
 136
 137         mt->lastmsg=msgp;
 138         return (msgp);
 139 }
 140
 141 struct imap_refmsg *rfc822_threadsearchmsg(struct imap_refmsgtable *mt,
 142                                            const char *msgid)
 143 {
 144 int n=hashmsgid(msgid);
 145 struct imap_refmsghash *h;
 146
 147         for (h= mt->hashtable[n]; h; h= h->nexthash)
 148         {
 149         int     rc=strcmp(h->msg->msgid, msgid);
 150
 151                 if (rc == 0)    return (h->msg);
 152                 if (rc > 0)
 153                         break;
 154         }
 155         return (0);
 156 }
 157
 158 static int findsubj(struct imap_refmsgtable *mt, const char *s, int *isrefwd,
 159                     int create, struct imap_subjlookup **ptr)
 160 {
 161         char *ss=rfc822_coresubj(s, isrefwd);
 162         int n;
 163         struct imap_subjlookup **h;
 164         struct imap_subjlookup *newsubj;
 165
 166         if (!ss)        return (-1);
 167         n=hashmsgid(ss);
 168
 169         for (h= &mt->subjtable[n]; *h; h= &(*h)->nextsubj)
 170         {
 171         int     rc=strcmp((*h)->subj, ss);
 172
 173                 if (rc == 0)
 174                 {
 175                         free(ss);
 176                         *ptr= *h;
 177                         return (0);
 178                 }
 179                 if (rc > 0)
 180                         break;
 181         }
 182         if (!create)
 183         {
 184                 free(ss);
 185                 *ptr=0;
 186                 return (0);
 187         }
 188
 189         newsubj=malloc(sizeof(struct imap_subjlookup));
 190         if (!newsubj)
 191         {
 192                 free(ss);
 193                 return (-1);
 194         }
 195         memset(newsubj, 0, sizeof(*newsubj));
 196         newsubj->subj=ss;
 197         newsubj->nextsubj= *h;
 198         newsubj->msgisrefwd= *isrefwd;
 199         *h=newsubj;
 200         *ptr=newsubj;
 201         return (0);
 202 }
 203
 204 static void linkparent(struct imap_refmsg *msg, struct imap_refmsg *lastmsg)
 205 {
 206         msg->parent=lastmsg;
 207         msg->prevsib=lastmsg->lastchild;
 208         if (msg->prevsib)
 209                 msg->prevsib->nextsib=msg;
 210         else
 211                 lastmsg->firstchild=msg;
 212
 213         lastmsg->lastchild=msg;
 214         msg->nextsib=0;
 215 }
 216
 217
 218 static void breakparent(struct imap_refmsg *m)
 219 {
 220         if (!m->parent) return;
 221
 222         if (m->prevsib) m->prevsib->nextsib=m->nextsib;
 223         else            m->parent->firstchild=m->nextsib;
 224
 225         if (m->nextsib) m->nextsib->prevsib=m->prevsib;
 226         else            m->parent->lastchild=m->prevsib;
 227         m->parent=0;
 228 }
 229
 230 static struct imap_refmsg *dorefcreate(struct imap_refmsgtable *mt,
 231                                        const char *newmsgid,
 232                                        struct rfc822a *a)
 233      /* a - references header */
 234 {
 235 struct imap_refmsg *lastmsg=0, *m;
 236 struct imap_refmsg *msg;
 237 int n;
 238
 239 /*
 240             (A) Using the Message-IDs in the message's references, link
 241             the corresponding messages together as parent/child.  Make
 242             the first reference the parent of the second (and the second
 243             a child of the first), the second the parent of the third
 244             (and the third a child of the second), etc.  The following
 245             rules govern the creation of these links:
 246
 247                If no reference message can be found with a given
 248                Message-ID, create a dummy message with this ID.  Use
 249                this dummy message for all subsequent references to this
 250                ID.
 251 */
 252
 253         for (n=0; n<a->naddrs; n++)
 254         {
 255                 char *msgid=a->addrs[n].tokens ? rfc822_getaddr(a, n):NULL;
 256
 257                 msg=msgid ? rfc822_threadsearchmsg(mt, msgid):0;
 258                 if (!msg)
 259                 {
 260                         msg=rfc822_threadallocmsg(mt, msgid ? msgid:"");
 261                         if (!msg)
 262                         {
 263                                 if (msgid)
 264                                         free(msgid);
 265
 266                                 return (0);
 267                         }
 268                         msg->isdummy=1;
 269                 }
 270
 271                 if (msgid)
 272                         free(msgid);
 273
 274 /*
 275                If a reference message already has a parent, don't change
 276                the existing link.
 277 */
 278
 279                 if (lastmsg == 0 || msg->parent)
 280                 {
 281                         lastmsg=msg;
 282                         continue;
 283                 }
 284
 285 /*
 286                Do not create a parent/child link if creating that link
 287                would introduce a loop.  For example, before making
 288                message A the parent of B, make sure that A is not a
 289                descendent of B.
 290
 291 */
 292
 293                 for (m=lastmsg; m; m=m->parent)
 294                         if (strcmp(m->msgid, msg->msgid) == 0)
 295                                 break;
 296                 if (m)
 297                 {
 298                         lastmsg=msg;
 299                         continue;
 300                 }
 301
 302                 linkparent(msg, lastmsg);
 303
 304                 lastmsg=msg;
 305         }
 306
 307 /*
 308             (B) Create a parent/child link between the last reference
 309             (or NIL if there are no references) and the current message.
 310             If the current message has a parent already, break the
 311             current parent/child link before creating the new one.  Note
 312             that if this message has no references, that it will now
 313             have no parent.
 314
 315                NOTE: The parent/child links MUST be kept consistent with
 316                one another at ALL times.
 317
 318 */
 319
 320         msg=*newmsgid ? rfc822_threadsearchmsg(mt, newmsgid):0;
 321
 322         /*
 323                If a message does not contain a Message-ID header line,
 324                or the Message-ID header line does not contain a valid
 325                Message ID, then assign a unique Message ID to this
 326                message.
 327
 328                Implementation note: empty msgid, plus dupe check below,
 329                implements that.
 330         */
 331
 332         if (msg && msg->isdummy)
 333         {
 334                 msg->isdummy=0;
 335                 if (msg->parent)
 336                         breakparent(msg);
 337         }
 338         else
 339         {
 340 #if 1
 341                 /*
 342                 ** If two or more messages have the same Message ID, assign
 343                 ** a unique Message ID to each of the duplicates.
 344                 **
 345                 ** Implementation note: just unlink the existing message from
 346                 ** it's parents/children.
 347                 */
 348                 if (msg)
 349                 {
 350                         while (msg->firstchild)
 351                                 breakparent(msg->firstchild);
 352                         breakparent(msg);
 353                         newmsgid="";
 354
 355                         /* Create new entry with an empty msgid, if any more
 356                         ** msgids come, they'll hit the dupe check again.
 357                         */
 358
 359                 }
 360 #endif
 361                 msg=rfc822_threadallocmsg(mt, newmsgid);
 362                 if (!msg)       return (0);
 363         }
 364
 365         if (lastmsg)
 366         {
 367                 for (m=lastmsg; m; m=m->parent)
 368                         if (strcmp(m->msgid, msg->msgid) == 0)
 369                                 break;
 370                 if (!m)
 371                         linkparent(msg, lastmsg);
 372         }
 373         return (msg);
 374 }
 375
 376 static struct imap_refmsg *threadmsg_common(struct imap_refmsg *m,
 377                                             const char *subjheader,
 378                                             const char *dateheader,
 379                                             time_t dateheader_tm,
 380                                             unsigned long seqnum);
 381
 382 static struct imap_refmsg *rfc822_threadmsgaref(struct imap_refmsgtable *mt,
 383                                                const char *msgidhdr,
 384                                                struct rfc822a *refhdr,
 385                                                const char *subjheader,
 386                                                const char *dateheader,
 387                                                time_t dateheader_tm,
 388                                                unsigned long seqnum);
 389
 390 struct imap_refmsg *rfc822_threadmsg(struct imap_refmsgtable *mt,
 391                                      const char *msgidhdr,
 392                                      const char *refhdr,
 393                                      const char *subjheader,
 394                                      const char *dateheader,
 395                                      time_t dateheader_tm,
 396                                      unsigned long seqnum)
 397 {
 398         struct rfc822t *t;
 399         struct rfc822a *a;
 400         struct imap_refmsg *m;
 401
 402         t=rfc822t_alloc_new(refhdr ? refhdr:"", NULL, NULL);
 403         if (!t)
 404         {
 405                 return (0);
 406         }
 407
 408         a=rfc822a_alloc(t);
 409         if (!a)
 410         {
 411                 rfc822t_free(t);
 412                 return (0);
 413         }
 414
 415         m=rfc822_threadmsgaref(mt, msgidhdr, a, subjheader, dateheader,
 416                                dateheader_tm, seqnum);
 417
 418         rfc822a_free(a);
 419         rfc822t_free(t);
 420         return m;
 421 }
 422
 423
 424 struct imap_refmsg *rfc822_threadmsgrefs(struct imap_refmsgtable *mt,
 425                                          const char *msgid_s,
 426                                          const char * const * msgidList,
 427                                          const char *subjheader,
 428                                          const char *dateheader,
 429                                          time_t dateheader_tm,
 430                                          unsigned long seqnum)
 431 {
 432         struct imap_refmsg *m;
 433         struct rfc822token *tArray;
 434         struct rfc822addr *aArray;
 435
 436         struct rfc822a a;
 437         size_t n, i;
 438
 439         for (n=0; msgidList[n]; n++)
 440                 ;
 441
 442         if ((tArray=malloc((n+1) * sizeof(*tArray))) == NULL)
 443                 return NULL;
 444
 445         if ((aArray=malloc((n+1) * sizeof(*aArray))) == NULL)
 446         {
 447                 free(tArray);
 448                 return NULL;
 449         }
 450
 451         for (i=0; i<n; i++)
 452         {
 453                 tArray[i].next=NULL;
 454                 tArray[i].token=0;
 455                 tArray[i].ptr=msgidList[i];
 456                 tArray[i].len=strlen(msgidList[i]);
 457
 458                 aArray[i].name=NULL;
 459                 aArray[i].tokens=&tArray[i];
 460         }
 461
 462         a.naddrs=n;
 463         a.addrs=aArray;
 464
 465         m=rfc822_threadmsgaref(mt, msgid_s, &a, subjheader, dateheader,
 466                                dateheader_tm, seqnum);
 467
 468         free(tArray);
 469         free(aArray);
 470         return m;
 471 }
 472
 473 static struct imap_refmsg *rfc822_threadmsgaref(struct imap_refmsgtable *mt,
 474                                                 const char *msgidhdr,
 475                                                 struct rfc822a *refhdr,
 476                                                 const char *subjheader,
 477                                                 const char *dateheader,
 478                                                 time_t dateheader_tm,
 479                                                 unsigned long seqnum)
 480 {
 481         struct rfc822t *t;
 482         struct rfc822a *a;
 483         struct imap_refmsg *m;
 484
 485         char *msgid_s;
 486
 487         t=rfc822t_alloc_new(msgidhdr ? msgidhdr:"", NULL, NULL);
 488         if (!t)
 489                 return (0);
 490         a=rfc822a_alloc(t);
 491         if (!a)
 492         {
 493                 rfc822t_free(t);
 494                 return (0);
 495         }
 496
 497         msgid_s=a->naddrs > 0 ? rfc822_getaddr(a, 0):strdup("");
 498
 499         rfc822a_free(a);
 500         rfc822t_free(t);
 501
 502         if (!msgid_s)
 503                 return (0);
 504
 505         m=dorefcreate(mt, msgid_s, refhdr);
 506
 507         free(msgid_s);
 508
 509         if (!m)
 510                 return (0);
 511
 512
 513         return threadmsg_common(m, subjheader, dateheader,
 514                                 dateheader_tm, seqnum);
 515 }
 516
 517 static struct imap_refmsg *threadmsg_common(struct imap_refmsg *m,
 518                                             const char *subjheader,
 519                                             const char *dateheader,
 520                                             time_t dateheader_tm,
 521                                             unsigned long seqnum)
 522 {
 523         if (subjheader && (m->subj=strdup(subjheader)) == 0)
 524                 return (0);     /* Cleanup in rfc822_threadfree() */
 525
 526         if (dateheader)
 527                 dateheader_tm=rfc822_parsedt(dateheader);
 528
 529         m->timestamp=dateheader_tm;
 530
 531         m->seqnum=seqnum;
 532
 533         return (m);
 534 }
 535
 536 /*
 537          (2) Gather together all of the messages that have no parents
 538          and make them all children (siblings of one another) of a dummy
 539          parent (the "root").  These messages constitute first messages
 540          of the threads created thus far.
 541
 542 */
 543
 544 struct imap_refmsg *rfc822_threadgetroot(struct imap_refmsgtable *mt)
 545 {
 546         struct imap_refmsg *root, *m;
 547
 548         if (mt->rootptr)
 549                 return (mt->rootptr);
 550
 551         root=rfc822_threadallocmsg(mt, "(root)");
 552
 553         if (!root)      return (0);
 554
 555         root->parent=root;      /* Temporary */
 556         root->isdummy=1;
 557
 558         for (m=mt->firstmsg; m; m=m->next)
 559                 if (!m->parent)
 560                 {
 561                         if (m->isdummy && m->firstchild == 0)
 562                                 continue; /* Can happen in reference creation */
 563
 564                         linkparent(m, root);
 565                 }
 566         root->parent=NULL;
 567         return (mt->rootptr=root);
 568 }
 569
 570 /*
 571 **
 572 **       (3) Prune dummy messages from the thread tree.  Traverse each
 573 **        thread under the root, and for each message:
 574 */
 575
 576 void rfc822_threadprune(struct imap_refmsgtable *mt)
 577 {
 578         struct imap_refmsg *msg;
 579
 580         for (msg=mt->firstmsg; msg; msg=msg->next)
 581         {
 582                 struct imap_refmsg *saveparent, *m;
 583
 584                 if (!msg->parent)
 585                         continue;       /* The root, need it later. */
 586
 587                 if (!msg->isdummy)
 588                         continue;
 589
 590                 /*
 591                 **
 592                 ** If it is a dummy message with NO children, delete it.
 593                 */
 594
 595                 if (msg->firstchild == 0)
 596                 {
 597                         breakparent(msg);
 598                         /*
 599                         ** Don't free the node, it'll be done on msgtable
 600                         ** purge.
 601                         */
 602                         continue;
 603                 }
 604
 605                 /*
 606                 ** If it is a dummy message with children, delete it, but
 607                 ** promote its children to the current level.  In other words,
 608                 ** splice them in with the dummy's siblings.
 609                 **
 610                 ** Do not promote the children if doing so would make them
 611                 ** children of the root, unless there is only one child.
 612                 */
 613
 614                 if (msg->firstchild->nextsib &&
 615                     msg->parent->parent)
 616                         continue;
 617
 618                 saveparent=msg->parent;
 619                 breakparent(msg);
 620
 621                 while ((m=msg->firstchild) != 0)
 622                 {
 623                         breakparent(m);
 624                         linkparent(m, saveparent);
 625                 }
 626         }
 627 }
 628
 629 static int cmp_msgs(const void *, const void *);
 630
 631 int rfc822_threadsortsubj(struct imap_refmsg *root)
 632 {
 633         struct imap_refmsg *toproot;
 634
 635 /*
 636 ** (4) Sort the messages under the root (top-level siblings only)
 637 ** by sent date.  In the case of an exact match on sent date or if
 638 ** either of the Date: headers used in a comparison can not be
 639 ** parsed, use the order in which the messages appear in the
 640 ** mailbox (that is, by sequence number) to determine the order.
 641 ** In the case of a dummy message, sort its children by sent date
 642 ** and then use the first child for the top-level sort.
 643 */
 644         size_t cnt, i;
 645         struct imap_refmsg **sortarray;
 646
 647         for (cnt=0, toproot=root->firstchild; toproot;
 648              toproot=toproot->nextsib)
 649         {
 650                 if (toproot->isdummy)
 651                         rfc822_threadsortsubj(toproot);
 652                 ++cnt;
 653         }
 654
 655         if ((sortarray=malloc(sizeof(struct imap_refmsg *)*(cnt+1))) == 0)
 656                 return (-1);
 657
 658         for (cnt=0; (toproot=root->firstchild) != NULL; ++cnt)
 659         {
 660                 sortarray[cnt]=toproot;
 661                 breakparent(toproot);
 662         }
 663
 664         qsort(sortarray, cnt, sizeof(*sortarray), cmp_msgs);
 665
 666         for (i=0; i<cnt; i++)
 667                 linkparent(sortarray[i], root);
 668         free(sortarray);
 669         return (0);
 670 }
 671
 672 int rfc822_threadgathersubj(struct imap_refmsgtable *mt,
 673                             struct imap_refmsg *root)
 674 {
 675         struct imap_refmsg *toproot, *p;
 676
 677 /*
 678 ** (5) Gather together messages under the root that have the same
 679 ** extracted subject text.
 680 **
 681 ** (A) Create a table for associating extracted subjects with
 682 ** messages.
 683 **
 684 ** (B) Populate the subject table with one message per
 685 ** extracted subject.  For each message under the root:
 686 */
 687
 688         for (toproot=root->firstchild; toproot; toproot=toproot->nextsib)
 689         {
 690                 const char *subj;
 691                 struct imap_subjlookup *subjtop;
 692                 int isrefwd;
 693
 694                 /*
 695                 ** (i) Find the subject of this thread by extracting the
 696                 ** base subject from the current message, or its first child
 697                 ** if the current message is a dummy.
 698                 */
 699
 700                 p=toproot;
 701                 if (p->isdummy)
 702                         p=p->firstchild;
 703
 704                 subj=p->subj ? p->subj:"";
 705
 706
 707                 /*
 708                 ** (ii) If the extracted subject is empty, skip this
 709                 ** message.
 710                 */
 711
 712                 if (*subj == 0)
 713                         continue;
 714
 715                 /*
 716                 ** (iii) Lookup the message associated with this extracted
 717                 ** subject in the table.
 718                 */
 719
 720                 if (findsubj(mt, subj, &isrefwd, 1, &subjtop))
 721                         return (-1);
 722
 723                 /*
 724                 **
 725                 ** (iv) If there is no message in the table with this
 726                 ** subject, add the current message and the extracted
 727                 ** subject to the subject table.
 728                 */
 729
 730                 if (subjtop->msg == 0)
 731                 {
 732                         subjtop->msg=toproot;
 733                         subjtop->msgisrefwd=isrefwd;
 734                         continue;
 735                 }
 736
 737                 /*
 738                 ** Otherwise, replace the message in the table with the
 739                 ** current message if the message in the table is not a
 740                 ** dummy AND either of the following criteria are true:
 741                 */
 742
 743                 if (!subjtop->msg->isdummy)
 744                 {
 745                         /*
 746                         ** The current message is a dummy
 747                         **
 748                         */
 749
 750                         if (toproot->isdummy)
 751                         {
 752                                 subjtop->msg=toproot;
 753                                 subjtop->msgisrefwd=isrefwd;
 754                                 continue;
 755                         }
 756
 757                         /*
 758                         ** The message in the table is a reply or forward (its
 759                         ** original subject contains a subj-refwd part and/or a
 760                         ** "(fwd)" subj-trailer) and the current message is
 761                         not.
 762                         */
 763
 764                         if (subjtop->msgisrefwd && !isrefwd)
 765                         {
 766                                 subjtop->msg=toproot;
 767                                 subjtop->msgisrefwd=isrefwd;
 768                         }
 769                 }
 770         }
 771         return (0);
 772 }
 773
 774 /*
 775 ** (C) Merge threads with the same subject.  For each message
 776 ** under the root:
 777 */
 778
 779 int rfc822_threadmergesubj(struct imap_refmsgtable *mt,
 780                            struct imap_refmsg *root)
 781 {
 782         struct imap_refmsg *toproot, *p, *q, *nextroot;
 783         char *str;
 784
 785         for (toproot=root->firstchild; toproot; toproot=nextroot)
 786         {
 787                 const char *subj;
 788                 struct imap_subjlookup *subjtop;
 789                 int isrefwd;
 790
 791                 nextroot=toproot->nextsib;
 792
 793                 /*
 794                 ** (i) Find the subject of this thread as in step 4.B.i
 795                 ** above.
 796                 */
 797
 798                 p=toproot;
 799                 if (p->isdummy)
 800                         p=p->firstchild;
 801
 802                 subj=p->subj ? p->subj:"";
 803
 804                 /*
 805                 ** (ii) If the extracted subject is empty, skip this
 806                 ** message.
 807                 */
 808
 809                 if (*subj == 0)
 810                         continue;
 811
 812                 /*
 813                 ** (iii) Lookup the message associated with this extracted
 814                 ** subject in the table.
 815                 */
 816
 817                 if (findsubj(mt, subj, &isrefwd, 0, &subjtop) || subjtop == 0)
 818                         return (-1);
 819
 820                 /*
 821                 ** (iv) If the message in the table is the current message,
 822                 ** skip it.
 823                 */
 824
 825                 /* NOTE - ptr comparison IS NOT LEGAL */
 826
 827                 subjtop->msg->flag2=1;
 828                 if (toproot->flag2)
 829                 {
 830                         toproot->flag2=0;
 831                         continue;
 832                 }
 833                 subjtop->msg->flag2=0;
 834
 835                 /*
 836                 ** Otherwise, merge the current message with the one in the
 837                 ** table using the following rules:
 838                 **
 839                 ** If both messages are dummies, append the current
 840                 ** message's children to the children of the message in
 841                 ** the table (the children of both messages become
 842                 ** siblings), and then delete the current message.
 843                 */
 844
 845                 if (subjtop->msg->isdummy && toproot->isdummy)
 846                 {
 847                         while ((p=toproot->firstchild) != 0)
 848                         {
 849                                 breakparent(p);
 850                                 linkparent(p, subjtop->msg);
 851                         }
 852                         breakparent(toproot);
 853                         continue;
 854                 }
 855
 856                 /*
 857                 ** If the message in the table is a dummy and the current
 858                 ** message is not, make the current message a child of
 859                 ** the message in the table (a sibling of it's children).
 860                 */
 861
 862                 if (subjtop->msg->isdummy)
 863                 {
 864                         breakparent(toproot);
 865                         linkparent(toproot, subjtop->msg);
 866                         continue;
 867                 }
 868
 869                 /*
 870                 ** If the current message is a reply or forward and the
 871                 ** message in the table is not, make the current message
 872                 ** a child of the message in the table (a sibling of it's
 873                 ** children).
 874                 */
 875
 876                 if (isrefwd)
 877                 {
 878                         p=subjtop->msg;
 879                         if (p->isdummy)
 880                                 p=p->firstchild;
 881
 882                         subj=p->subj ? p->subj:"";
 883
 884                         str=rfc822_coresubj(subj, &isrefwd);
 885
 886                         if (!str)
 887                                 return (-1);
 888                         free(str);      /* Don't really care */
 889
 890                         if (!isrefwd)
 891                         {
 892                                 breakparent(toproot);
 893                                 linkparent(toproot, subjtop->msg);
 894                                 continue;
 895                         }
 896                 }
 897
 898                 /*
 899                 ** Otherwise, create a new dummy container and make both
 900                 ** messages children of the dummy, and replace the
 901                 ** message in the table with the dummy message.
 902                 */
 903
 904                 /* What we do is create a new message, then move the
 905                 ** contents of subjtop->msg (including its children)
 906                 ** to the new message, then make the new message a child
 907                 ** of subjtop->msg, and mark subjtop->msg as a dummy msg.
 908                 */
 909
 910                 q=rfc822_threadallocmsg(mt, "(dummy)");
 911                 if (!q)
 912                         return (-1);
 913
 914                 q->isdummy=1;
 915
 916                 swapmsgdata(q, subjtop->msg);
 917
 918                 while ((p=subjtop->msg->firstchild) != 0)
 919                 {
 920                         breakparent(p);
 921                         linkparent(p, q);
 922                 }
 923                 linkparent(q, subjtop->msg);
 924
 925                 breakparent(toproot);
 926                 linkparent(toproot, subjtop->msg);
 927         }
 928         return (0);
 929 }
 930
 931 /*
 932 ** (6) Traverse the messages under the root and sort each set of
 933 ** siblings by sent date.  Traverse the messages in such a way
 934 ** that the "youngest" set of siblings are sorted first, and the
 935 ** "oldest" set of siblings are sorted last (grandchildren are
 936 ** sorted before children, etc).  In the case of an exact match on
 937 ** sent date or if either of the Date: headers used in a
 938 ** comparison can not be parsed, use the order in which the
 939 ** messages appear in the mailbox (that is, by sequence number) to
 940 ** determine the order.  In the case of a dummy message (which can
 941 ** only occur with top-level siblings), use its first child for
 942 ** sorting.
 943 */
 944
 945 static int cmp_msgs(const void *a, const void *b)
 946 {
 947         struct imap_refmsg *ma=*(struct imap_refmsg **)a;
 948         struct imap_refmsg *mb=*(struct imap_refmsg **)b;
 949         time_t ta, tb;
 950         unsigned long na, nb;
 951
 952         while (ma && ma->isdummy)
 953                 ma=ma->firstchild;
 954
 955         while (mb && mb->isdummy)
 956                 mb=mb->firstchild;
 957
 958         ta=tb=0;
 959         na=nb=0;
 960         if (ma)
 961         {
 962                 ta=ma->timestamp;
 963                 na=ma->seqnum;
 964         }
 965         if (mb)
 966         {
 967                 tb=mb->timestamp;
 968                 nb=mb->seqnum;
 969         }
 970
 971         return (ta && tb && ta != tb ? ta < tb ? -1: 1:
 972                 na < nb ? -1: na > nb ? 1:0);
 973 }
 974
 975 struct imap_threadsortinfo {
 976         struct imap_refmsgtable *mt;
 977         struct imap_refmsg **sort_table;
 978         size_t sort_table_cnt;
 979 } ;
 980
 981 static int dothreadsort(struct imap_threadsortinfo *,
 982                         struct imap_refmsg *);
 983
 984 int rfc822_threadsortbydate(struct imap_refmsgtable *mt)
 985 {
 986         struct imap_threadsortinfo itsi;
 987         int rc;
 988
 989         itsi.mt=mt;
 990         itsi.sort_table=0;
 991         itsi.sort_table_cnt=0;
 992
 993         rc=dothreadsort(&itsi, mt->rootptr);
 994
 995         if (itsi.sort_table)
 996                 free(itsi.sort_table);
 997         return (rc);
 998 }
 999
1000 static int dothreadsort(struct imap_threadsortinfo *itsi,
1001                         struct imap_refmsg *p)
1002 {
1003         struct imap_refmsg *q;
1004         size_t i, n;
1005
1006         for (q=p->firstchild; q; q=q->nextsib)
1007                 dothreadsort(itsi, q);
1008
1009         n=0;
1010         for (q=p->firstchild; q; q=q->nextsib)
1011                 ++n;
1012
1013         if (n > itsi->sort_table_cnt)
1014         {
1015                 struct imap_refmsg **new_array=(struct imap_refmsg **)
1016                         (itsi->sort_table ?
1017                          realloc(itsi->sort_table,
1018                                  sizeof(struct imap_refmsg *)*n)
1019                          :malloc(sizeof(struct imap_refmsg *)*n));
1020
1021                 if (!new_array)
1022                         return (-1);
1023
1024                 itsi->sort_table=new_array;
1025                 itsi->sort_table_cnt=n;
1026         }
1027
1028         n=0;
1029         while ((q=p->firstchild) != 0)
1030         {
1031                 breakparent(q);
1032                 itsi->sort_table[n++]=q;
1033         }
1034
1035         qsort(itsi->sort_table, n, sizeof(struct imap_refmsg *), cmp_msgs);
1036
1037         for (i=0; i<n; i++)
1038                 linkparent(itsi->sort_table[i], p);
1039         return (0);
1040 }
1041
1042 struct imap_refmsg *rfc822_thread(struct imap_refmsgtable *mt)
1043 {
1044         if (!mt->rootptr)
1045         {
1046                 rfc822_threadprune(mt);
1047                 if ((mt->rootptr=rfc822_threadgetroot(mt)) == 0)
1048                         return (0);
1049                 if (rfc822_threadsortsubj(mt->rootptr) ||
1050                     rfc822_threadgathersubj(mt, mt->rootptr) ||
1051                     rfc822_threadmergesubj(mt, mt->rootptr) ||
1052                     rfc822_threadsortbydate(mt))
1053                 {
1054                         mt->rootptr=0;
1055                         return (0);
1056                 }
1057         }
1058
1059         return (mt->rootptr);
1060 }