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