thread.c

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