thread.c

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