thread.c

   1 /*@ S-nail - a mail user agent derived from Berkeley Mail.
   2  *@ Message threading.
   3  *
   4  * Copyright (c) 2000-2004 Gunnar Ritter, Freiburg i. Br., Germany.
   5  * Copyright (c) 2012 - 2014 Steffen "Daode" Nurpmeso <sdaoden@users.sf.net>.
   6  */
   7 /*
   8  * Copyright (c) 2004
   9  *      Gunnar Ritter.  All rights reserved.
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  * 1. Redistributions of source code must retain the above copyright
  15  *    notice, this list of conditions and the following disclaimer.
  16  * 2. Redistributions in binary form must reproduce the above copyright
  17  *    notice, this list of conditions and the following disclaimer in the
  18  *    documentation and/or other materials provided with the distribution.
  19  * 3. All advertising materials mentioning features or use of this software
  20  *    must display the following acknowledgement:
  21  *      This product includes software developed by Gunnar Ritter
  22  *      and his contributors.
  23  * 4. Neither the name of Gunnar Ritter nor the names of his contributors
  24  *    may be used to endorse or promote products derived from this software
  25  *    without specific prior written permission.
  26  *
  27  * THIS SOFTWARE IS PROVIDED BY GUNNAR RITTER AND CONTRIBUTORS ``AS IS'' AND
  28  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  29  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  30  * ARE DISCLAIMED.  IN NO EVENT SHALL GUNNAR RITTER OR CONTRIBUTORS BE LIABLE
  31  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  32  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  33  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  34  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  35  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  36  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  37  * SUCH DAMAGE.
  38  */
  39
  40 #ifndef HAVE_AMALGAMATION
  41 # include "nail.h"
  42 #endif
  43
  44 /*
  45  * Open addressing is used for Message-IDs because the maximum number of
  46  * messages in the table is known in advance (== msgCount).
  47  */
  48 struct  mitem {
  49         struct message  *mi_data;
  50         char    *mi_id;
  51 };
  52
  53 struct msort {
  54         union {
  55 #ifdef HAVE_SPAM
  56                 ui_it   ms_ui;
  57 #endif
  58                 long    ms_long;
  59                 char *  ms_char;
  60         } ms_u;
  61         int     ms_n;
  62 };
  63
  64 static unsigned mhash(const char *cp, int mprime);
  65 static struct mitem *mlook(char *id, struct mitem *mt, struct message *mdata,
  66                 int mprime);
  67 static void adopt(struct message *parent, struct message *child, int dist);
  68 static struct message *interlink(struct message *m, long cnt, int nmail);
  69 static void finalize(struct message *mp);
  70 #ifdef HAVE_SPAM
  71 static int muilt(void const *a, void const *b);
  72 #endif
  73 static int mlonglt(const void *a, const void *b);
  74 static int mcharlt(const void *a, const void *b);
  75 static void lookup(struct message *m, struct mitem *mi, int mprime);
  76 static void makethreads(struct message *m, long cnt, int nmail);
  77 static char const *skipre(char const *cp);
  78 static int colpt(int *msgvec, int cl);
  79 static void colps(struct message *b, int cl);
  80 static void colpm(struct message *m, int cl, int *cc, int *uc);
  81
  82 /*
  83  * Return the hash value for a message id modulo mprime, or mprime
  84  * if the passed string does not look like a message-id.
  85  */
  86 static unsigned
  87 mhash(const char *cp, int mprime)
  88 {
  89
  90         unsigned        h = 0, g, at = 0;
  91
  92         cp--;
  93         while (*++cp) {
  94                 /*
  95                  * Pay attention not to hash characters which are
  96                  * irrelevant for Message-ID semantics.
  97                  */
  98                 if (*cp == '(') {
  99                         cp = skip_comment(&cp[1]) - 1;
 100                         continue;
 101                 }
 102                 if (*cp == '"' || *cp == '\\')
 103                         continue;
 104                 if (*cp == '@')
 105                         at++;
 106                 h = ((h << 4) & 0xffffffff) + lowerconv(*cp & 0377);
 107                 if ((g = h & 0xf0000000) != 0) {
 108                         h = h ^ (g >> 24);
 109                         h = h ^ g;
 110                 }
 111         }
 112         return at ? h % (unsigned int)mprime : (unsigned int)mprime;
 113 }
 114
 115 #define NOT_AN_ID       ((struct mitem *)-1)
 116
 117 /*
 118  * Look up a message id. Returns NOT_AN_ID if the passed string does
 119  * not look like a message-id.
 120  */
 121 static struct mitem *
 122 mlook(char *id, struct mitem *mt, struct message *mdata, int mprime)
 123 {
 124         struct mitem    *mp;
 125         unsigned        h, c, n = 0;
 126
 127         if (id == NULL && (id = hfield1("message-id", mdata)) == NULL)
 128                 return NULL;
 129         if (mdata && mdata->m_idhash)
 130                 h = ~mdata->m_idhash;
 131         else {
 132                 h = mhash(id, mprime);
 133                 if (h == (unsigned int)mprime)
 134                         return NOT_AN_ID;
 135         }
 136         mp = &mt[c = h];
 137         while (mp->mi_id != NULL) {
 138                 if (msgidcmp(mp->mi_id, id) == 0)
 139                         break;
 140                 c += n&1 ? -((n+1)/2) * ((n+1)/2) : ((n+1)/2) * ((n+1)/2);
 141                 n++;
 142                 while (c >= (unsigned int)mprime)
 143                         c -= mprime;
 144                 mp = &mt[c];
 145         }
 146         if (mdata != NULL && mp->mi_id == NULL) {
 147                 mp->mi_id = sstrdup(id);
 148                 mp->mi_data = mdata;
 149                 mdata->m_idhash = ~h;
 150         }
 151         return mp->mi_id ? mp : NULL;
 152 }
 153
 154 /*
 155  * Child is to be adopted by parent. A thread tree is structured
 156  * as follows:
 157  *
 158  *  ------       m_child       ------        m_child
 159  *  |    |-------------------->|    |------------------------> . . .
 160  *  |    |<--------------------|    |<-----------------------  . . .
 161  *  ------      m_parent       ------       m_parent
 162  *     ^^                       |  ^
 163  *     | \____        m_younger |  |
 164  *     |      \                 |  |
 165  *     |       ----             |  |
 166  *     |           \            |  | m_elder
 167  *     |   m_parent ----        |  |
 168  *     |                \       |  |
 169  *     |                 ----   |  |
 170  *     |                     \  +  |
 171  *     |                       ------        m_child
 172  *     |                       |    |------------------------> . . .
 173  *     |                       |    |<-----------------------  . . .
 174  *     |                       ------       m_parent
 175  *     |                        |  ^
 176  *      \-----        m_younger |  |
 177  *            \                 |  |
 178  *             ----             |  |
 179  *                 \            |  | m_elder
 180  *         m_parent ----        |  |
 181  *                      \       |  |
 182  *                       ----   |  |
 183  *                           \  +  |
 184  *                             ------        m_child
 185  *                             |    |------------------------> . . .
 186  *                             |    |<-----------------------  . . .
 187  *                             ------       m_parent
 188  *                              |  ^
 189  *                              . . .
 190  *
 191  * The base message of a thread does not have a m_parent link. Elements
 192  * connected by m_younger/m_elder links are replies to the same message,
 193  * which is connected to them by m_parent links. The first reply to a
 194  * message gets the m_child link.
 195  */
 196 static void
 197 adopt(struct message *parent, struct message *child, int dist)
 198 {
 199         struct message  *mp, *mq;
 200
 201         for (mp = parent; mp; mp = mp->m_parent)
 202                 if (mp == child)
 203                         return;
 204         child->m_level = dist;  /* temporarily store distance */
 205         child->m_parent = parent;
 206         if (parent->m_child != NULL) {
 207                 mq = NULL;
 208                 for (mp = parent->m_child; mp; mp = mp->m_younger) {
 209                         if (mp->m_date >= child->m_date) {
 210                                 if (mp->m_elder)
 211                                         mp->m_elder->m_younger = child;
 212                                 child->m_elder = mp->m_elder;
 213                                 mp->m_elder = child;
 214                                 child->m_younger = mp;
 215                                 if (mp == parent->m_child)
 216                                         parent->m_child = child;
 217                                 return;
 218                         }
 219                         mq = mp;
 220                 }
 221                 mq->m_younger = child;
 222                 child->m_elder = mq;
 223         } else
 224                 parent->m_child = child;
 225 }
 226
 227 /*
 228  * Connect all messages on the lowest thread level with m_younger/m_elder
 229  * links.
 230  */
 231 static struct message *
 232 interlink(struct message *m, long cnt, int nmail)
 233 {
 234         int     i;
 235         long    n;
 236         struct msort    *ms;
 237         struct message  *root;
 238         int     autocollapse = !nmail && !(inhook&2) &&
 239                         ok_blook(autocollapse);
 240
 241         ms = smalloc(sizeof *ms * cnt);
 242         for (n = 0, i = 0; i < cnt; i++) {
 243                 if (m[i].m_parent == NULL) {
 244                         if (autocollapse)
 245                                 colps(&m[i], 1);
 246                         ms[n].ms_u.ms_long = m[i].m_date;
 247                         ms[n].ms_n = i;
 248                         n++;
 249                 }
 250         }
 251         if (n > 0) {
 252                 qsort(ms, n, sizeof *ms, mlonglt);
 253                 root = &m[ms[0].ms_n];
 254                 for (i = 1; i < n; i++) {
 255                         m[ms[i-1].ms_n].m_younger = &m[ms[i].ms_n];
 256                         m[ms[i].ms_n].m_elder = &m[ms[i-1].ms_n];
 257                 }
 258         } else
 259                 root = &m[0];
 260         free(ms);
 261         return root;
 262 }
 263
 264 static void
 265 finalize(struct message *mp)
 266 {
 267         long    n;
 268
 269         for (n = 0; mp; mp = next_in_thread(mp)) {
 270                 mp->m_threadpos = ++n;
 271                 mp->m_level = mp->m_parent ?
 272                         mp->m_level + mp->m_parent->m_level : 0;
 273         }
 274 }
 275
 276 #ifdef HAVE_SPAM
 277 static int
 278 muilt(void const *a, void const *b)
 279 {
 280         struct msort const *xa = a, *xb = b;
 281         int i;
 282
 283         i = (int)(xa->ms_u.ms_ui - xb->ms_u.ms_ui);
 284         if (i == 0)
 285                 i = xa->ms_n - xb->ms_n;
 286         return i;
 287 }
 288 #endif
 289
 290 static int
 291 mlonglt(const void *a, const void *b)
 292 {
 293         struct msort const *xa = a, *xb = b;
 294         int i;
 295
 296         i = (int)(xa->ms_u.ms_long - xb->ms_u.ms_long);
 297         if (i == 0)
 298                 i = xa->ms_n - xb->ms_n;
 299         return i;
 300 }
 301
 302 static int
 303 mcharlt(const void *a, const void *b)
 304 {
 305         struct msort const *xa = a, *xb = b;
 306         int i;
 307
 308         i = strcoll(xa->ms_u.ms_char, xb->ms_u.ms_char);
 309         if (i == 0)
 310                 i = xa->ms_n - xb->ms_n;
 311         return i;
 312 }
 313
 314 static void
 315 lookup(struct message *m, struct mitem *mi, int mprime)
 316 {
 317         struct name     *np;
 318         struct mitem    *ip;
 319         char    *cp;
 320         long    dist;
 321
 322         if (m->m_flag & MHIDDEN)
 323                 return;
 324         dist = 1;
 325         if ((cp = hfield1("in-reply-to", m)) != NULL) {
 326                 if ((np = extract(cp, GREF)) != NULL)
 327                         do {
 328                                 if ((ip = mlook(np->n_name, mi, NULL, mprime))
 329                                                 != NULL && ip != NOT_AN_ID) {
 330                                         adopt(ip->mi_data, m, 1);
 331                                         return;
 332                                 }
 333                         } while ((np = np->n_flink) != NULL);
 334         }
 335         if ((cp = hfield1("references", m)) != NULL) {
 336                 if ((np = extract(cp, GREF)) != NULL) {
 337                         while (np->n_flink != NULL)
 338                                 np = np->n_flink;
 339                         do {
 340                                 if ((ip = mlook(np->n_name, mi, NULL, mprime))
 341                                                 != NULL) {
 342                                         if (ip == NOT_AN_ID)
 343                                                 continue; /* skip dist++ */
 344                                         adopt(ip->mi_data, m, dist);
 345                                         return;
 346                                 }
 347                                 dist++;
 348                         } while ((np = np->n_blink) != NULL);
 349                 }
 350         }
 351 }
 352
 353 static void
 354 makethreads(struct message *m, long cnt, int nmail)
 355 {
 356         struct mitem    *mt;
 357         char    *cp;
 358         long    i, mprime;
 359
 360         if (cnt == 0)
 361                 return;
 362         mprime = nextprime(cnt);
 363         mt = scalloc(mprime, sizeof *mt);
 364
 365         srelax_hold();
 366         for (i = 0; i < cnt; i++) {
 367                 if ((m[i].m_flag&MHIDDEN) == 0) {
 368                         mlook(NULL, mt, &m[i], mprime);
 369                         if (m[i].m_date == 0) {
 370                                 if ((cp = hfield1("date", &m[i])) != NULL)
 371                                         m[i].m_date = rfctime(cp);
 372                         }
 373                 }
 374                 m[i].m_child = m[i].m_younger = m[i].m_elder =
 375                         m[i].m_parent = NULL;
 376                 m[i].m_level = 0;
 377                 if (!nmail && !(inhook&2))
 378                         m[i].m_collapsed = 0;
 379                 srelax();
 380         }
 381         /*
 382          * Most folders contain the eldest messages first. Traversing
 383          * them in descending order makes it more likely that younger
 384          * brothers are found first, so elder ones can be prepended to
 385          * the brother list, which is faster. The worst case is still
 386          * in O(n^2) and occurs when all but one messages in a folder
 387          * are replies to the one message, and are sorted such that
 388          * youngest messages occur first.
 389          */
 390         for (i = cnt-1; i >= 0; i--) {
 391                 lookup(&m[i], mt, mprime);
 392                 srelax();
 393         }
 394         srelax_rele();
 395
 396         threadroot = interlink(m, cnt, nmail);
 397         finalize(threadroot);
 398
 399         for (i = 0; i < mprime; ++i)
 400                 if (mt[i].mi_id != NULL)
 401                         free(mt[i].mi_id);
 402         free(mt);
 403         mb.mb_threaded = 1;
 404 }
 405
 406 FL int
 407 thread(void *vp)
 408 {
 409         if (mb.mb_threaded != 1 || vp == NULL || vp == (void *)-1) {
 410 #ifdef HAVE_IMAP
 411                 if (mb.mb_type == MB_IMAP)
 412                         imap_getheaders(1, msgCount);
 413 #endif
 414                 makethreads(message, msgCount, vp == (void *)-1);
 415                 if (mb.mb_sorted != NULL)
 416                         free(mb.mb_sorted);
 417                 mb.mb_sorted = sstrdup("thread");
 418         }
 419         if (vp && vp != (void *)-1 && !inhook && ok_blook(header))
 420                 return headers(vp);
 421         return 0;
 422 }
 423
 424 FL int
 425 unthread(void *vp)
 426 {
 427         struct message  *m;
 428
 429         mb.mb_threaded = 0;
 430         free(mb.mb_sorted);
 431         mb.mb_sorted = NULL;
 432         for (m = &message[0]; m < &message[msgCount]; m++)
 433                 m->m_collapsed = 0;
 434         if (vp && !inhook && ok_blook(header))
 435                 return headers(vp);
 436         return 0;
 437 }
 438
 439 FL struct message *
 440 next_in_thread(struct message *mp)
 441 {
 442         if (mp->m_child)
 443                 return mp->m_child;
 444         if (mp->m_younger)
 445                 return mp->m_younger;
 446         while (mp->m_parent) {
 447                 if (mp->m_parent->m_younger)
 448                         return mp->m_parent->m_younger;
 449                 mp = mp->m_parent;
 450         }
 451         return NULL;
 452 }
 453
 454 FL struct message *
 455 prev_in_thread(struct message *mp)
 456 {
 457         if (mp->m_elder) {
 458                 mp = mp->m_elder;
 459                 while (mp->m_child) {
 460                         mp = mp->m_child;
 461                         while (mp->m_younger)
 462                                 mp = mp->m_younger;
 463                 }
 464                 return mp;
 465         }
 466         return mp->m_parent;
 467 }
 468
 469 FL struct message *
 470 this_in_thread(struct message *mp, long n)
 471 {
 472         struct message  *mq;
 473
 474         if (n == -1) {  /* find end of thread */
 475                 while (mp) {
 476                         if (mp->m_younger) {
 477                                 mp = mp->m_younger;
 478                                 continue;
 479                         }
 480                         mq = next_in_thread(mp);
 481                         if (mq == NULL || mq->m_threadpos < mp->m_threadpos)
 482                                 return mp;
 483                         mp = mq;
 484                 }
 485                 return NULL;
 486         }
 487         while (mp && mp->m_threadpos < n) {
 488                 if (mp->m_younger && mp->m_younger->m_threadpos <= n) {
 489                         mp = mp->m_younger;
 490                         continue;
 491                 }
 492                 mp = next_in_thread(mp);
 493         }
 494         return mp && mp->m_threadpos == n ? mp : NULL;
 495 }
 496
 497 /*
 498  * Sorted mode is internally just a variant of threaded mode with all
 499  * m_parent and m_child links being NULL.
 500  */
 501 FL int
 502 sort(void *vp)
 503 {
 504         enum method {
 505                 SORT_SUBJECT,
 506                 SORT_DATE,
 507                 SORT_STATUS,
 508                 SORT_SIZE,
 509                 SORT_FROM,
 510                 SORT_TO,
 511 #ifdef HAVE_SPAM
 512                 SORT_SPAM,
 513 #endif
 514                 SORT_THREAD
 515         } method;
 516         struct {
 517                 const char      *me_name;
 518                 enum method     me_method;
 519                 int     (*me_func)(const void *, const void *);
 520         } methnames[] = {
 521                 { "date",       SORT_DATE,      mlonglt },
 522                 { "from",       SORT_FROM,      mcharlt },
 523                 { "to",         SORT_TO,        mcharlt },
 524                 { "subject",    SORT_SUBJECT,   mcharlt },
 525                 { "size",       SORT_SIZE,      mlonglt },
 526 #ifdef HAVE_SPAM
 527                 { "spam",       SORT_SPAM,      muilt },
 528 #endif
 529                 { "status",     SORT_STATUS,    mlonglt },
 530                 { "thread",     SORT_THREAD,    NULL },
 531                 { NULL,         -1,             NULL }
 532         };
 533         char    **args = (char **)vp, *cp, *_args[2];
 534         int     (*func)(const void *, const void *);
 535         struct msort    *ms;
 536         struct str      in, out;
 537         int     i, n, msgvec[2];
 538         bool_t showname = ok_blook(showname);
 539         struct message  *mp;
 540
 541         msgvec[0] = dot - &message[0] + 1;
 542         msgvec[1] = 0;
 543         if (vp == NULL || vp == (void *)-1) {
 544                 _args[0] = savestr(mb.mb_sorted);
 545                 _args[1] = NULL;
 546                 args = _args;
 547         } else if (args[0] == NULL) {
 548                 printf("Current sorting criterion is: %s\n",
 549                                 mb.mb_sorted ? mb.mb_sorted : "unsorted");
 550                 return 0;
 551         }
 552         for (i = 0; methnames[i].me_name; i++)
 553                 if (*args[0] && is_prefix(args[0], methnames[i].me_name))
 554                         break;
 555         if (methnames[i].me_name == NULL) {
 556                 fprintf(stderr, "Unknown sorting method \"%s\"\n", args[0]);
 557                 return 1;
 558         }
 559         method = methnames[i].me_method;
 560         func = methnames[i].me_func;
 561         free(mb.mb_sorted);
 562         mb.mb_sorted = sstrdup(args[0]);
 563         if (method == SORT_THREAD)
 564                 return thread(vp && vp != (void *)-1 ? msgvec : vp);
 565         ms = ac_alloc(sizeof *ms * msgCount);
 566         switch (method) {
 567         case SORT_SUBJECT:
 568         case SORT_DATE:
 569         case SORT_FROM:
 570         case SORT_TO:
 571 #ifdef HAVE_IMAP
 572                 if (mb.mb_type == MB_IMAP)
 573                         imap_getheaders(1, msgCount);
 574 #endif
 575                 break;
 576         default:
 577                 break;
 578         }
 579
 580         srelax_hold();
 581         for (n = 0, i = 0; i < msgCount; i++) {
 582                 mp = &message[i];
 583                 if ((mp->m_flag&MHIDDEN) == 0) {
 584                         switch (method) {
 585                         case SORT_DATE:
 586                                 if (mp->m_date == 0 &&
 587                                                 (cp = hfield1("date", mp)) != 0)
 588                                         mp->m_date = rfctime(cp);
 589                                 ms[n].ms_u.ms_long = mp->m_date;
 590                                 break;
 591                         case SORT_STATUS:
 592                                 if (mp->m_flag & MDELETED)
 593                                         ms[n].ms_u.ms_long = 1;
 594                                 else if ((mp->m_flag&(MNEW|MREAD)) == MNEW)
 595                                         ms[n].ms_u.ms_long = 90;
 596                                 else if (mp->m_flag & MFLAGGED)
 597                                         ms[n].ms_u.ms_long = 85;
 598                                 else if ((mp->m_flag&(MNEW|MBOX)) == MBOX)
 599                                         ms[n].ms_u.ms_long = 70;
 600                                 else if (mp->m_flag & MNEW)
 601                                         ms[n].ms_u.ms_long = 80;
 602                                 else if (mp->m_flag & MREAD)
 603                                         ms[n].ms_u.ms_long = 40;
 604                                 else
 605                                         ms[n].ms_u.ms_long = 60;
 606                                 break;
 607                         case SORT_SIZE:
 608                                 ms[n].ms_u.ms_long = mp->m_xsize;
 609                                 break;
 610 #ifdef HAVE_SPAM
 611                         case SORT_SPAM:
 612                                 ms[n].ms_u.ms_ui = mp->m_spamscore;
 613                                 break;
 614 #endif
 615                         case SORT_FROM:
 616                         case SORT_TO:
 617                                 if ((cp = hfield1(method == SORT_FROM ?
 618                                                 "from" : "to", mp)) != NULL) {
 619                                         ms[n].ms_u.ms_char = sstrdup(showname ?
 620                                                 realname(cp) : skin(cp));
 621                                         makelow(ms[n].ms_u.ms_char);
 622                                 } else
 623                                         ms[n].ms_u.ms_char = sstrdup("");
 624                                 break;
 625                         default:
 626                         case SORT_SUBJECT:
 627                                 if ((cp = hfield1("subject", mp)) != NULL) {
 628                                         in.s = cp;
 629                                         in.l = strlen(in.s);
 630                                         mime_fromhdr(&in, &out, TD_ICONV);
 631                                         ms[n].ms_u.ms_char = sstrdup(
 632                                                         skipre(out.s));
 633                                         free(out.s);
 634                                         makelow(ms[n].ms_u.ms_char);
 635                                 } else
 636                                         ms[n].ms_u.ms_char = sstrdup("");
 637                                 break;
 638                         }
 639                         ms[n++].ms_n = i;
 640                 }
 641                 mp->m_child = mp->m_younger = mp->m_elder = mp->m_parent = NULL;
 642                 mp->m_level = 0;
 643                 mp->m_collapsed = 0;
 644                 srelax();
 645         }
 646         srelax_rele();
 647
 648         if (n > 0) {
 649                 qsort(ms, n, sizeof *ms, func);
 650                 threadroot = &message[ms[0].ms_n];
 651                 for (i = 1; i < n; i++) {
 652                         message[ms[i-1].ms_n].m_younger = &message[ms[i].ms_n];
 653                         message[ms[i].ms_n].m_elder = &message[ms[i-1].ms_n];
 654                 }
 655         } else
 656                 threadroot = &message[0];
 657         finalize(threadroot);
 658         mb.mb_threaded = 2;
 659
 660         switch (method) {
 661         case SORT_FROM:
 662         case SORT_TO:
 663         case SORT_SUBJECT:
 664                 for (i = 0; i < n; ++i)
 665                         free(ms[i].ms_u.ms_char);
 666                 /* FALLTHRU */
 667         default:
 668                 break;
 669         }
 670         ac_free(ms);
 671         return ((vp && vp != (void *)-1 && !inhook && ok_blook(header))
 672                 ? headers(msgvec) : 0);
 673 }
 674
 675 static char const *
 676 skipre(char const *cp)
 677 {
 678         if (lowerconv(cp[0]) == 'r' && lowerconv(cp[1]) == 'e' &&
 679                         cp[2] == ':' && spacechar(cp[3])) {
 680                 cp = &cp[4];
 681                 while (spacechar(*cp))
 682                         cp++;
 683         }
 684         return cp;
 685 }
 686
 687 FL int
 688 ccollapse(void *v)
 689 {
 690         return colpt(v, 1);
 691 }
 692
 693 FL int
 694 cuncollapse(void *v)
 695 {
 696         return colpt(v, 0);
 697 }
 698
 699 static int
 700 colpt(int *msgvec, int cl)
 701 {
 702         int     *ip;
 703
 704         if (mb.mb_threaded != 1) {
 705                 puts("Not in threaded mode.");
 706                 return 1;
 707         }
 708         for (ip = msgvec; *ip != 0; ip++)
 709                 colps(&message[*ip-1], cl);
 710         return 0;
 711 }
 712
 713 static void
 714 colps(struct message *b, int cl)
 715 {
 716         struct message  *m;
 717         int     cc = 0, uc = 0;
 718
 719         if (cl && (b->m_collapsed > 0 || (b->m_flag & (MNEW|MREAD)) == MNEW))
 720                 return;
 721         if (b->m_child) {
 722                 m = b->m_child;
 723                 colpm(m, cl, &cc, &uc);
 724                 for (m = m->m_younger; m; m = m->m_younger)
 725                         colpm(m, cl, &cc, &uc);
 726         }
 727         if (cl) {
 728                 b->m_collapsed = -cc;
 729                 for (m = b->m_parent; m; m = m->m_parent)
 730                         if (m->m_collapsed <= -uc ) {
 731                                 m->m_collapsed += uc;
 732                                 break;
 733                         }
 734         } else {
 735                 if (b->m_collapsed > 0) {
 736                         b->m_collapsed = 0;
 737                         uc++;
 738                 }
 739                 for (m = b; m; m = m->m_parent)
 740                         if (m->m_collapsed <= -uc) {
 741                                 m->m_collapsed += uc;
 742                                 break;
 743                         }
 744         }
 745 }
 746
 747 static void
 748 colpm(struct message *m, int cl, int *cc, int *uc)
 749 {
 750         if (cl) {
 751                 if (m->m_collapsed > 0)
 752                         (*uc)++;
 753                 if ((m->m_flag & (MNEW|MREAD)) != MNEW || m->m_collapsed < 0)
 754                         m->m_collapsed = 1;
 755                 if (m->m_collapsed > 0)
 756                         (*cc)++;
 757         } else {
 758                 if (m->m_collapsed > 0) {
 759                         m->m_collapsed = 0;
 760                         (*uc)++;
 761                 }
 762         }
 763         if (m->m_child) {
 764                 m = m->m_child;
 765                 colpm(m, cl, cc, uc);
 766                 for (m = m->m_younger; m; m = m->m_younger)
 767                         colpm(m, cl, cc, uc);
 768         }
 769 }
 770
 771 FL void
 772 uncollapse1(struct message *m, int always)
 773 {
 774         if (mb.mb_threaded == 1 && (always || m->m_collapsed > 0))
 775                 colps(m, 0);
 776 }