Back to index

courier  0.68.2
imaprefs.c
Go to the documentation of this file.
00001 /*
00002 ** Copyright 2000-2003 Double Precision, Inc.
00003 ** See COPYING for distribution information.
00004 */
00005 
00006 /*
00007 */
00008 
00009 #include      "config.h"
00010 
00011 #include      <stdio.h>
00012 #include      <stdlib.h>
00013 #include      <string.h>
00014 #include      <time.h>
00015 
00016 #include      "rfc822.h"
00017 #include      "imaprefs.h"
00018 
00019 static void swapmsgdata(struct imap_refmsg *a, struct imap_refmsg *b)
00020 {
00021        char *cp;
00022        char c;
00023        time_t t;
00024        unsigned long ul;
00025 
00026 #define swap(a,b,tmp) (tmp)=(a); (a)=(b); (b)=(tmp);
00027 
00028        swap(a->msgid, b->msgid, cp);
00029        swap(a->isdummy, b->isdummy, c);
00030        swap(a->flag2, b->flag2, c);
00031 
00032        swap(a->timestamp, b->timestamp, t);
00033        swap(a->seqnum, b->seqnum, ul);
00034 
00035 #undef swap
00036 }
00037 
00038 struct imap_refmsgtable *rfc822_threadalloc()
00039 {
00040 struct imap_refmsgtable *p;
00041 
00042        p=(struct imap_refmsgtable *)malloc(sizeof(struct imap_refmsgtable));
00043        if (p)
00044               memset(p, 0, sizeof(*p));
00045        return (p);
00046 }
00047 
00048 void rfc822_threadfree(struct imap_refmsgtable *p)
00049 {
00050 int i;
00051 struct imap_refmsghash *h;
00052 struct imap_subjlookup *s;
00053 struct imap_refmsg *m;
00054 
00055        for (i=0; i<sizeof(p->hashtable)/sizeof(p->hashtable[0]); i++)
00056               while ((h=p->hashtable[i]) != 0)
00057               {
00058                      p->hashtable[i]=h->nexthash;
00059                      free(h);
00060               }
00061 
00062        for (i=0; i<sizeof(p->subjtable)/sizeof(p->subjtable[0]); i++)
00063               while ((s=p->subjtable[i]) != 0)
00064               {
00065                      p->subjtable[i]=s->nextsubj;
00066                      free(s->subj);
00067                      free(s);
00068               }
00069 
00070        while ((m=p->firstmsg) != 0)
00071        {
00072               p->firstmsg=m->next;
00073               if (m->subj)
00074                      free(m->subj);
00075               free(m);
00076        }
00077        free(p);
00078 }
00079 
00080 static int hashmsgid(const char *msgid)
00081 {
00082 unsigned long hashno=0;
00083 
00084        while (*msgid)
00085        {
00086        unsigned long n= (hashno << 1);
00087 
00088 #define       HMIDS  (((struct imap_refmsgtable *)0)->hashtable)
00089 #define       HHMIDSS       ( sizeof(HMIDS) / sizeof( HMIDS[0] ))
00090 
00091               if (hashno & HHMIDSS )
00092                      n ^= 1;
00093 
00094               hashno= n ^ (unsigned char)*msgid++;
00095        }
00096 
00097        return (hashno % HHMIDSS);
00098 }
00099 
00100 struct imap_refmsg *rfc822_threadallocmsg(struct imap_refmsgtable *mt,
00101                                      const char *msgid)
00102 {
00103 int n=hashmsgid(msgid);
00104 struct imap_refmsg *msgp= (struct imap_refmsg *)
00105        malloc(sizeof(struct imap_refmsg)+1+strlen(msgid));
00106 struct imap_refmsghash *h, **hp;
00107 
00108        if (!msgp)    return (0);
00109        memset(msgp, 0, sizeof(*msgp));
00110        strcpy ((msgp->msgid=(char *)(msgp+1)), msgid);
00111 
00112        h=(struct imap_refmsghash *)malloc(sizeof(struct imap_refmsghash));
00113        if (!h)
00114        {
00115               free(msgp);
00116               return (0);
00117        }
00118 
00119        for (hp= &mt->hashtable[n]; *hp; hp= & (*hp)->nexthash)
00120        {
00121               if (strcmp( (*hp)->msg->msgid, msgp->msgid) > 0)
00122                      break;
00123        }
00124 
00125        h->nexthash= *hp;
00126        *hp=h;
00127        h->msg=msgp;
00128 
00129        msgp->last=mt->lastmsg;
00130 
00131        if (mt->lastmsg)
00132               mt->lastmsg->next=msgp;
00133        else
00134               mt->firstmsg=msgp;
00135 
00136        mt->lastmsg=msgp;
00137        return (msgp);
00138 }
00139 
00140 struct imap_refmsg *rfc822_threadsearchmsg(struct imap_refmsgtable *mt,
00141                                       const char *msgid)
00142 {
00143 int n=hashmsgid(msgid);
00144 struct imap_refmsghash *h;
00145 
00146        for (h= mt->hashtable[n]; h; h= h->nexthash)
00147        {
00148        int    rc=strcmp(h->msg->msgid, msgid);
00149 
00150               if (rc == 0)  return (h->msg);
00151               if (rc > 0)
00152                      break;
00153        }
00154        return (0);
00155 }
00156 
00157 static int findsubj(struct imap_refmsgtable *mt, const char *s, int *isrefwd,
00158                   int create, struct imap_subjlookup **ptr)
00159 {
00160        char *ss=rfc822_coresubj(s, isrefwd);
00161        int n;
00162        struct imap_subjlookup **h;
00163        struct imap_subjlookup *newsubj;
00164 
00165        if (!ss)      return (-1);
00166        n=hashmsgid(ss);
00167 
00168        for (h= &mt->subjtable[n]; *h; h= &(*h)->nextsubj)
00169        {
00170        int    rc=strcmp((*h)->subj, ss);
00171 
00172               if (rc == 0)
00173               {
00174                      free(ss);
00175                      *ptr= *h;
00176                      return (0);
00177               }
00178               if (rc > 0)
00179                      break;
00180        }
00181        if (!create)
00182        {
00183               free(ss);
00184               *ptr=0;
00185               return (0);
00186        }
00187 
00188        newsubj=malloc(sizeof(struct imap_subjlookup));
00189        if (!newsubj)
00190        {
00191               free(ss);
00192               return (-1);
00193        }
00194        memset(newsubj, 0, sizeof(*newsubj));
00195        newsubj->subj=ss;
00196        newsubj->nextsubj= *h;
00197        newsubj->msgisrefwd= *isrefwd;
00198        *h=newsubj;
00199        *ptr=newsubj;
00200        return (0);
00201 }
00202 
00203 static void linkparent(struct imap_refmsg *msg, struct imap_refmsg *lastmsg)
00204 {
00205        msg->parent=lastmsg;
00206        msg->prevsib=lastmsg->lastchild;
00207        if (msg->prevsib)
00208               msg->prevsib->nextsib=msg;
00209        else
00210               lastmsg->firstchild=msg;
00211 
00212        lastmsg->lastchild=msg;
00213        msg->nextsib=0;
00214 }
00215 
00216 
00217 static void breakparent(struct imap_refmsg *m)
00218 {
00219        if (!m->parent)      return;
00220 
00221        if (m->prevsib)      m->prevsib->nextsib=m->nextsib;
00222        else          m->parent->firstchild=m->nextsib;
00223 
00224        if (m->nextsib)      m->nextsib->prevsib=m->prevsib;
00225        else          m->parent->lastchild=m->prevsib;
00226        m->parent=0;
00227 }
00228 
00229 static struct imap_refmsg *dorefcreate(struct imap_refmsgtable *mt,
00230                                    const char *newmsgid,
00231                                    struct rfc822a *a)
00232      /* a - references header */
00233 {
00234 struct imap_refmsg *lastmsg=0, *m;
00235 struct imap_refmsg *msg;
00236 int n;
00237 
00238 /*
00239             (A) Using the Message-IDs in the message's references, link
00240             the corresponding messages together as parent/child.  Make
00241             the first reference the parent of the second (and the second
00242             a child of the first), the second the parent of the third
00243             (and the third a child of the second), etc.  The following
00244             rules govern the creation of these links:
00245 
00246                If no reference message can be found with a given
00247                Message-ID, create a dummy message with this ID.  Use
00248                this dummy message for all subsequent references to this
00249                ID.
00250 */
00251 
00252        for (n=0; n<a->naddrs; n++)
00253        {
00254               char *msgid=a->addrs[n].tokens ? rfc822_getaddr(a, n):NULL;
00255 
00256               msg=msgid ? rfc822_threadsearchmsg(mt, msgid):0;
00257               if (!msg)
00258               {
00259                      msg=rfc822_threadallocmsg(mt, msgid ? msgid:"");
00260                      if (!msg)
00261                      {
00262                             if (msgid)
00263                                    free(msgid);
00264 
00265                             return (0);
00266                      }
00267                      msg->isdummy=1;
00268               }
00269 
00270               if (msgid)
00271                      free(msgid);
00272 
00273 /*
00274                If a reference message already has a parent, don't change
00275                the existing link.
00276 */
00277 
00278               if (lastmsg == 0 || msg->parent)
00279               {
00280                      lastmsg=msg;
00281                      continue;
00282               }
00283 
00284 /*
00285                Do not create a parent/child link if creating that link
00286                would introduce a loop.  For example, before making
00287                message A the parent of B, make sure that A is not a
00288                descendent of B.
00289 
00290 */
00291 
00292               for (m=lastmsg; m; m=m->parent)
00293                      if (strcmp(m->msgid, msg->msgid) == 0)
00294                             break;
00295               if (m)
00296               {
00297                      lastmsg=msg;
00298                      continue;
00299               }
00300 
00301               linkparent(msg, lastmsg);
00302 
00303               lastmsg=msg;
00304        }
00305 
00306 /*
00307             (B) Create a parent/child link between the last reference
00308             (or NIL if there are no references) and the current message.
00309             If the current message has a parent already, break the
00310             current parent/child link before creating the new one.  Note
00311             that if this message has no references, that it will now
00312             have no parent.
00313 
00314                NOTE: The parent/child links MUST be kept consistent with
00315                one another at ALL times.
00316 
00317 */
00318 
00319        msg=*newmsgid ? rfc822_threadsearchmsg(mt, newmsgid):0;
00320 
00321        /*
00322               If a message does not contain a Message-ID header line,
00323               or the Message-ID header line does not contain a valid
00324               Message ID, then assign a unique Message ID to this
00325               message.
00326 
00327               Implementation note: empty msgid, plus dupe check below,
00328               implements that.
00329        */
00330 
00331        if (msg && msg->isdummy)
00332        {
00333               msg->isdummy=0;
00334               if (msg->parent)
00335                      breakparent(msg);
00336        }
00337        else
00338        {
00339 #if 1
00340               /*
00341               ** If two or more messages have the same Message ID, assign
00342               ** a unique Message ID to each of the duplicates.
00343               **
00344               ** Implementation note: just unlink the existing message from
00345               ** it's parents/children.
00346               */
00347               if (msg)
00348               {
00349                      while (msg->firstchild)
00350                             breakparent(msg->firstchild);
00351                      breakparent(msg);
00352                      newmsgid="";
00353 
00354                      /* Create new entry with an empty msgid, if any more
00355                      ** msgids come, they'll hit the dupe check again.
00356                      */
00357 
00358               }
00359 #endif
00360               msg=rfc822_threadallocmsg(mt, newmsgid);
00361               if (!msg)     return (0);
00362        }
00363 
00364        if (lastmsg)
00365        {
00366               for (m=lastmsg; m; m=m->parent)
00367                      if (strcmp(m->msgid, msg->msgid) == 0)
00368                             break;
00369               if (!m)
00370                      linkparent(msg, lastmsg);
00371        }
00372        return (msg);
00373 }
00374 
00375 static struct imap_refmsg *threadmsg_common(struct imap_refmsg *m,
00376                                        const char *subjheader,
00377                                        const char *dateheader,
00378                                        time_t dateheader_tm,
00379                                        unsigned long seqnum);
00380 
00381 static struct imap_refmsg *rfc822_threadmsgaref(struct imap_refmsgtable *mt,
00382                                           const char *msgidhdr,
00383                                           struct rfc822a *refhdr,
00384                                           const char *subjheader,
00385                                           const char *dateheader,
00386                                           time_t dateheader_tm,
00387                                           unsigned long seqnum);
00388 
00389 struct imap_refmsg *rfc822_threadmsg(struct imap_refmsgtable *mt,
00390                                  const char *msgidhdr,
00391                                  const char *refhdr,
00392                                  const char *subjheader,
00393                                  const char *dateheader,
00394                                  time_t dateheader_tm,
00395                                  unsigned long seqnum)
00396 {
00397        struct rfc822t *t;
00398        struct rfc822a *a;
00399        struct imap_refmsg *m;
00400 
00401        t=rfc822t_alloc_new(refhdr ? refhdr:"", NULL, NULL);
00402        if (!t)
00403        {
00404               return (0);
00405        }
00406 
00407        a=rfc822a_alloc(t);
00408        if (!a)
00409        {
00410               rfc822t_free(t);
00411               return (0);
00412        }
00413 
00414        m=rfc822_threadmsgaref(mt, msgidhdr, a, subjheader, dateheader,
00415                             dateheader_tm, seqnum);
00416 
00417        rfc822a_free(a);
00418        rfc822t_free(t);
00419        return m;
00420 }
00421 
00422 
00423 struct imap_refmsg *rfc822_threadmsgrefs(struct imap_refmsgtable *mt,
00424                                     const char *msgid_s,
00425                                     const char * const * msgidList,
00426                                     const char *subjheader,
00427                                     const char *dateheader,
00428                                     time_t dateheader_tm,
00429                                     unsigned long seqnum)
00430 {
00431        struct imap_refmsg *m;
00432        struct rfc822token *tArray;
00433        struct rfc822addr *aArray;
00434 
00435        struct rfc822a a;
00436        size_t n, i;
00437 
00438        for (n=0; msgidList[n]; n++)
00439               ;
00440 
00441        if ((tArray=malloc((n+1) * sizeof(*tArray))) == NULL)
00442               return NULL;
00443 
00444        if ((aArray=malloc((n+1) * sizeof(*aArray))) == NULL)
00445        {
00446               free(tArray);
00447               return NULL;
00448        }
00449 
00450        for (i=0; i<n; i++)
00451        {
00452               tArray[i].next=NULL;
00453               tArray[i].token=0;
00454               tArray[i].ptr=msgidList[i];
00455               tArray[i].len=strlen(msgidList[i]);
00456 
00457               aArray[i].name=NULL;
00458               aArray[i].tokens=&tArray[i];
00459        }
00460 
00461        a.naddrs=n;
00462        a.addrs=aArray;
00463 
00464        m=rfc822_threadmsgaref(mt, msgid_s, &a, subjheader, dateheader,
00465                             dateheader_tm, seqnum);
00466 
00467        free(tArray);
00468        free(aArray);
00469        return m;
00470 }
00471 
00472 static struct imap_refmsg *rfc822_threadmsgaref(struct imap_refmsgtable *mt,
00473                                           const char *msgidhdr,
00474                                           struct rfc822a *refhdr,
00475                                           const char *subjheader,
00476                                           const char *dateheader,
00477                                           time_t dateheader_tm,
00478                                           unsigned long seqnum)
00479 {
00480        struct rfc822t *t;
00481        struct rfc822a *a;
00482        struct imap_refmsg *m;
00483 
00484        char *msgid_s;
00485 
00486        t=rfc822t_alloc_new(msgidhdr ? msgidhdr:"", NULL, NULL);
00487        if (!t)
00488               return (0);
00489        a=rfc822a_alloc(t);
00490        if (!a)
00491        {
00492               rfc822t_free(t);
00493               return (0);
00494        }
00495 
00496        msgid_s=a->naddrs > 0 ? rfc822_getaddr(a, 0):strdup("");
00497 
00498        rfc822a_free(a);
00499        rfc822t_free(t);
00500 
00501        if (!msgid_s)
00502               return (0);
00503 
00504        m=dorefcreate(mt, msgid_s, refhdr);
00505 
00506        free(msgid_s);
00507 
00508        if (!m)
00509               return (0);
00510 
00511 
00512        return threadmsg_common(m, subjheader, dateheader,
00513                             dateheader_tm, seqnum);
00514 }
00515 
00516 static struct imap_refmsg *threadmsg_common(struct imap_refmsg *m,
00517                                        const char *subjheader,
00518                                        const char *dateheader,
00519                                        time_t dateheader_tm,
00520                                        unsigned long seqnum)
00521 {
00522        if (subjheader && (m->subj=strdup(subjheader)) == 0)
00523               return (0);   /* Cleanup in rfc822_threadfree() */
00524 
00525        if (dateheader)
00526               dateheader_tm=rfc822_parsedt(dateheader);
00527 
00528        m->timestamp=dateheader_tm;
00529 
00530        m->seqnum=seqnum;
00531 
00532        return (m);
00533 }
00534 
00535 /*
00536          (2) Gather together all of the messages that have no parents
00537          and make them all children (siblings of one another) of a dummy
00538          parent (the "root").  These messages constitute first messages
00539          of the threads created thus far.
00540 
00541 */
00542 
00543 struct imap_refmsg *rfc822_threadgetroot(struct imap_refmsgtable *mt)
00544 {
00545        struct imap_refmsg *root, *m;
00546 
00547        if (mt->rootptr)
00548               return (mt->rootptr);
00549 
00550        root=rfc822_threadallocmsg(mt, "(root)");
00551 
00552        if (!root)    return (0);
00553 
00554        root->parent=root;   /* Temporary */
00555        root->isdummy=1;
00556 
00557        for (m=mt->firstmsg; m; m=m->next)
00558               if (!m->parent)
00559               {
00560                      if (m->isdummy && m->firstchild == 0)
00561                             continue; /* Can happen in reference creation */
00562 
00563                      linkparent(m, root);
00564               }
00565        root->parent=NULL;
00566        return (mt->rootptr=root);
00567 }
00568 
00569 /*
00570 ** 
00571 **       (3) Prune dummy messages from the thread tree.  Traverse each
00572 **        thread under the root, and for each message:
00573 */
00574 
00575 void rfc822_threadprune(struct imap_refmsgtable *mt)
00576 {
00577        struct imap_refmsg *msg;
00578 
00579        for (msg=mt->firstmsg; msg; msg=msg->next)
00580        {
00581               struct imap_refmsg *saveparent, *m;
00582 
00583               if (!msg->parent)
00584                      continue;     /* The root, need it later. */
00585 
00586               if (!msg->isdummy)
00587                      continue;
00588 
00589               /*
00590               **
00591               ** If it is a dummy message with NO children, delete it.
00592               */
00593 
00594               if (msg->firstchild == 0)
00595               {
00596                      breakparent(msg);
00597                      /*
00598                      ** Don't free the node, it'll be done on msgtable
00599                      ** purge.
00600                      */
00601                      continue;
00602               }
00603 
00604               /*
00605               ** If it is a dummy message with children, delete it, but
00606               ** promote its children to the current level.  In other words,
00607               ** splice them in with the dummy's siblings.
00608               **
00609               ** Do not promote the children if doing so would make them
00610               ** children of the root, unless there is only one child.
00611               */
00612 
00613               if (msg->firstchild->nextsib &&
00614                   msg->parent->parent)
00615                      continue;
00616 
00617               saveparent=msg->parent;
00618               breakparent(msg);
00619 
00620               while ((m=msg->firstchild) != 0)
00621               {
00622                      breakparent(m);
00623                      linkparent(m, saveparent);
00624               }
00625        }
00626 }
00627 
00628 static int cmp_msgs(const void *, const void *);
00629 
00630 int rfc822_threadsortsubj(struct imap_refmsg *root)
00631 {
00632        struct imap_refmsg *toproot;
00633 
00634 /*
00635 ** (4) Sort the messages under the root (top-level siblings only)
00636 ** by sent date.  In the case of an exact match on sent date or if
00637 ** either of the Date: headers used in a comparison can not be
00638 ** parsed, use the order in which the messages appear in the
00639 ** mailbox (that is, by sequence number) to determine the order.
00640 ** In the case of a dummy message, sort its children by sent date
00641 ** and then use the first child for the top-level sort.
00642 */
00643        size_t cnt, i;
00644        struct imap_refmsg **sortarray;
00645 
00646        for (cnt=0, toproot=root->firstchild; toproot;
00647             toproot=toproot->nextsib)
00648        {
00649               if (toproot->isdummy)
00650                      rfc822_threadsortsubj(toproot);
00651               ++cnt;
00652        }
00653 
00654        if ((sortarray=malloc(sizeof(struct imap_refmsg *)*(cnt+1))) == 0)
00655               return (-1);
00656 
00657        for (cnt=0; (toproot=root->firstchild) != NULL; ++cnt)
00658        {
00659               sortarray[cnt]=toproot;
00660               breakparent(toproot);
00661        }
00662 
00663        qsort(sortarray, cnt, sizeof(*sortarray), cmp_msgs);
00664 
00665        for (i=0; i<cnt; i++)
00666               linkparent(sortarray[i], root);
00667        free(sortarray);
00668        return (0);
00669 }
00670 
00671 int rfc822_threadgathersubj(struct imap_refmsgtable *mt,
00672                          struct imap_refmsg *root)
00673 {
00674        struct imap_refmsg *toproot, *p;
00675 
00676 /*
00677 ** (5) Gather together messages under the root that have the same
00678 ** extracted subject text.
00679 **
00680 ** (A) Create a table for associating extracted subjects with
00681 ** messages.
00682 **
00683 ** (B) Populate the subject table with one message per
00684 ** extracted subject.  For each message under the root:
00685 */
00686 
00687        for (toproot=root->firstchild; toproot; toproot=toproot->nextsib)
00688        {
00689               const char *subj;
00690               struct imap_subjlookup *subjtop;
00691               int isrefwd;
00692 
00693               /*
00694               ** (i) Find the subject of this thread by extracting the
00695               ** base subject from the current message, or its first child
00696               ** if the current message is a dummy.
00697               */
00698 
00699               p=toproot;
00700               if (p->isdummy)
00701                      p=p->firstchild;
00702 
00703               subj=p->subj ? p->subj:"";
00704 
00705 
00706               /*
00707               ** (ii) If the extracted subject is empty, skip this
00708               ** message.
00709               */
00710 
00711               if (*subj == 0)
00712                      continue;
00713 
00714               /*
00715               ** (iii) Lookup the message associated with this extracted
00716               ** subject in the table.
00717               */
00718 
00719               if (findsubj(mt, subj, &isrefwd, 1, &subjtop))
00720                      return (-1);
00721 
00722               /*
00723               **
00724               ** (iv) If there is no message in the table with this
00725               ** subject, add the current message and the extracted
00726               ** subject to the subject table.
00727               */
00728 
00729               if (subjtop->msg == 0)
00730               {
00731                      subjtop->msg=toproot;
00732                      subjtop->msgisrefwd=isrefwd;
00733                      continue;
00734               }
00735 
00736               /*
00737               ** Otherwise, replace the message in the table with the
00738               ** current message if the message in the table is not a
00739               ** dummy AND either of the following criteria are true:
00740               */
00741 
00742               if (!subjtop->msg->isdummy)
00743               {
00744                      /*
00745                      ** The current message is a dummy
00746                      **
00747                      */
00748 
00749                      if (toproot->isdummy)
00750                      {
00751                             subjtop->msg=toproot;
00752                             subjtop->msgisrefwd=isrefwd;
00753                             continue;
00754                      }
00755 
00756                      /*
00757                      ** The message in the table is a reply or forward (its
00758                      ** original subject contains a subj-refwd part and/or a
00759                      ** "(fwd)" subj-trailer) and the current message is
00760                      not.
00761                      */
00762 
00763                      if (subjtop->msgisrefwd && !isrefwd)
00764                      {
00765                             subjtop->msg=toproot;
00766                             subjtop->msgisrefwd=isrefwd;
00767                      }
00768               }
00769        }
00770        return (0);
00771 }
00772 
00773 /*
00774 ** (C) Merge threads with the same subject.  For each message
00775 ** under the root:
00776 */
00777 
00778 int rfc822_threadmergesubj(struct imap_refmsgtable *mt,
00779                         struct imap_refmsg *root)
00780 {
00781        struct imap_refmsg *toproot, *p, *q, *nextroot;
00782        char *str;
00783 
00784        for (toproot=root->firstchild; toproot; toproot=nextroot)
00785        {
00786               const char *subj;
00787               struct imap_subjlookup *subjtop;
00788               int isrefwd;
00789 
00790               nextroot=toproot->nextsib;
00791 
00792               /*
00793               ** (i) Find the subject of this thread as in step 4.B.i
00794               ** above.
00795               */
00796 
00797               p=toproot;
00798               if (p->isdummy)
00799                      p=p->firstchild;
00800 
00801               subj=p->subj ? p->subj:"";
00802 
00803               /*
00804               ** (ii) If the extracted subject is empty, skip this
00805               ** message.
00806               */
00807 
00808               if (*subj == 0)
00809                      continue;
00810 
00811               /*
00812               ** (iii) Lookup the message associated with this extracted
00813               ** subject in the table.
00814               */
00815 
00816               if (findsubj(mt, subj, &isrefwd, 0, &subjtop) || subjtop == 0)
00817                      return (-1);
00818 
00819               /*
00820               ** (iv) If the message in the table is the current message,
00821               ** skip it.
00822               */
00823 
00824               /* NOTE - ptr comparison IS NOT LEGAL */
00825 
00826               subjtop->msg->flag2=1;
00827               if (toproot->flag2)
00828               {
00829                      toproot->flag2=0;
00830                      continue;
00831               }
00832               subjtop->msg->flag2=0;
00833 
00834               /*
00835               ** Otherwise, merge the current message with the one in the
00836               ** table using the following rules:
00837               **
00838               ** If both messages are dummies, append the current
00839               ** message's children to the children of the message in
00840               ** the table (the children of both messages become
00841               ** siblings), and then delete the current message.
00842               */
00843 
00844               if (subjtop->msg->isdummy && toproot->isdummy)
00845               {
00846                      while ((p=toproot->firstchild) != 0)
00847                      {
00848                             breakparent(p);
00849                             linkparent(p, subjtop->msg);
00850                      }
00851                      breakparent(toproot);
00852                      continue;
00853               }
00854 
00855               /*
00856               ** If the message in the table is a dummy and the current
00857               ** message is not, make the current message a child of
00858               ** the message in the table (a sibling of it's children).
00859               */
00860 
00861               if (subjtop->msg->isdummy)
00862               {
00863                      breakparent(toproot);
00864                      linkparent(toproot, subjtop->msg);
00865                      continue;
00866               }
00867 
00868               /*
00869               ** If the current message is a reply or forward and the
00870               ** message in the table is not, make the current message
00871               ** a child of the message in the table (a sibling of it's
00872               ** children).
00873               */
00874 
00875               if (isrefwd)
00876               {
00877                      p=subjtop->msg;
00878                      if (p->isdummy)
00879                             p=p->firstchild;
00880 
00881                      subj=p->subj ? p->subj:"";
00882 
00883                      str=rfc822_coresubj(subj, &isrefwd);
00884 
00885                      if (!str)
00886                             return (-1);
00887                      free(str);    /* Don't really care */
00888 
00889                      if (!isrefwd)
00890                      {
00891                             breakparent(toproot);
00892                             linkparent(toproot, subjtop->msg);
00893                             continue;
00894                      }
00895               }
00896 
00897               /*
00898               ** Otherwise, create a new dummy container and make both
00899               ** messages children of the dummy, and replace the
00900               ** message in the table with the dummy message.
00901               */
00902 
00903               /* What we do is create a new message, then move the
00904               ** contents of subjtop->msg (including its children)
00905               ** to the new message, then make the new message a child
00906               ** of subjtop->msg, and mark subjtop->msg as a dummy msg.
00907               */
00908 
00909               q=rfc822_threadallocmsg(mt, "(dummy)");
00910               if (!q)
00911                      return (-1);
00912 
00913               q->isdummy=1;
00914 
00915               swapmsgdata(q, subjtop->msg);
00916 
00917               while ((p=subjtop->msg->firstchild) != 0)
00918               {
00919                      breakparent(p);
00920                      linkparent(p, q);
00921               }
00922               linkparent(q, subjtop->msg);
00923 
00924               breakparent(toproot);
00925               linkparent(toproot, subjtop->msg);
00926        }
00927        return (0);
00928 }
00929 
00930 /*
00931 ** (6) Traverse the messages under the root and sort each set of
00932 ** siblings by sent date.  Traverse the messages in such a way
00933 ** that the "youngest" set of siblings are sorted first, and the
00934 ** "oldest" set of siblings are sorted last (grandchildren are
00935 ** sorted before children, etc).  In the case of an exact match on
00936 ** sent date or if either of the Date: headers used in a
00937 ** comparison can not be parsed, use the order in which the
00938 ** messages appear in the mailbox (that is, by sequence number) to
00939 ** determine the order.  In the case of a dummy message (which can
00940 ** only occur with top-level siblings), use its first child for
00941 ** sorting.
00942 */
00943 
00944 static int cmp_msgs(const void *a, const void *b)
00945 {
00946        struct imap_refmsg *ma=*(struct imap_refmsg **)a;
00947        struct imap_refmsg *mb=*(struct imap_refmsg **)b;
00948        time_t ta, tb;
00949        unsigned long na, nb;
00950 
00951        while (ma && ma->isdummy)
00952               ma=ma->firstchild;
00953 
00954        while (mb && mb->isdummy)
00955               mb=mb->firstchild;
00956 
00957        ta=tb=0;
00958        na=nb=0;
00959        if (ma)
00960        {
00961               ta=ma->timestamp;
00962               na=ma->seqnum;
00963        }
00964        if (mb)
00965        {
00966               tb=mb->timestamp;
00967               nb=mb->seqnum;
00968        }
00969 
00970        return (ta && tb && ta != tb ? ta < tb ? -1: 1:
00971               na < nb ? -1: na > nb ? 1:0);
00972 }
00973 
00974 struct imap_threadsortinfo {
00975        struct imap_refmsgtable *mt;
00976        struct imap_refmsg **sort_table;
00977        size_t sort_table_cnt;
00978 } ;
00979 
00980 static int dothreadsort(struct imap_threadsortinfo *,
00981                      struct imap_refmsg *);
00982 
00983 int rfc822_threadsortbydate(struct imap_refmsgtable *mt)
00984 {
00985        struct imap_threadsortinfo itsi;
00986        int rc;
00987 
00988        itsi.mt=mt;
00989        itsi.sort_table=0;
00990        itsi.sort_table_cnt=0;
00991 
00992        rc=dothreadsort(&itsi, mt->rootptr);
00993 
00994        if (itsi.sort_table)
00995               free(itsi.sort_table);
00996        return (rc);
00997 }
00998 
00999 static int dothreadsort(struct imap_threadsortinfo *itsi,
01000                      struct imap_refmsg *p)
01001 {
01002        struct imap_refmsg *q;
01003        size_t i, n;
01004 
01005        for (q=p->firstchild; q; q=q->nextsib)
01006               dothreadsort(itsi, q);
01007 
01008        n=0;
01009        for (q=p->firstchild; q; q=q->nextsib)
01010               ++n;
01011 
01012        if (n > itsi->sort_table_cnt)
01013        {
01014               struct imap_refmsg **new_array=(struct imap_refmsg **)
01015                      (itsi->sort_table ?
01016                       realloc(itsi->sort_table,
01017                              sizeof(struct imap_refmsg *)*n)
01018                       :malloc(sizeof(struct imap_refmsg *)*n));
01019 
01020               if (!new_array)
01021                      return (-1);
01022 
01023               itsi->sort_table=new_array;
01024               itsi->sort_table_cnt=n;
01025        }
01026 
01027        n=0;
01028        while ((q=p->firstchild) != 0)
01029        {
01030               breakparent(q);
01031               itsi->sort_table[n++]=q;
01032        }
01033 
01034        qsort(itsi->sort_table, n, sizeof(struct imap_refmsg *), cmp_msgs);
01035 
01036        for (i=0; i<n; i++)
01037               linkparent(itsi->sort_table[i], p);
01038        return (0);
01039 }
01040 
01041 struct imap_refmsg *rfc822_thread(struct imap_refmsgtable *mt)
01042 {
01043        if (!mt->rootptr)
01044        {
01045               rfc822_threadprune(mt);
01046               if ((mt->rootptr=rfc822_threadgetroot(mt)) == 0)
01047                      return (0);
01048               if (rfc822_threadsortsubj(mt->rootptr) ||
01049                   rfc822_threadgathersubj(mt, mt->rootptr) ||
01050                   rfc822_threadmergesubj(mt, mt->rootptr) ||
01051                   rfc822_threadsortbydate(mt))
01052               {
01053                      mt->rootptr=0;
01054                      return (0);
01055               }
01056        }
01057 
01058        return (mt->rootptr);
01059 }