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