Logo Search packages:      
Sourcecode: heirloom-mailx version File versions  Download package

thread.c

/*
 * Heirloom mailx - a mail user agent derived from Berkeley Mail.
 *
 * Copyright (c) 2000-2004 Gunnar Ritter, Freiburg i. Br., Germany.
 */
/*
 * Copyright (c) 2004
 *    Gunnar Ritter.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *    This product includes software developed by Gunnar Ritter
 *    and his contributors.
 * 4. Neither the name of Gunnar Ritter nor the names of his contributors
 *    may be used to endorse or promote products derived from this software
 *    without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY GUNNAR RITTER AND CONTRIBUTORS ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL GUNNAR RITTER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 */

#ifndef lint
#ifdef      DOSCCS
static char sccsid[] = "@(#)thread.c      1.57 (gritter) 3/4/06";
#endif
#endif /* not lint */

#include "config.h"

#include "rcv.h"
#include "extern.h"
#include <time.h>

/*
 * Mail -- a mail program
 *
 * Message threading.
 */

/*
 * Open addressing is used for Message-IDs because the maximum number of
 * messages in the table is known in advance (== msgCount).
 */
struct      mitem {
      struct message    *mi_data;
      char  *mi_id;
};

struct msort {
      union {
            long  ms_long;
            char  *ms_char;
            float ms_float;
      } ms_u;
      int   ms_n;
};

static unsigned mhash(const char *cp, int mprime);
static struct mitem *mlook(char *id, struct mitem *mt, struct message *mdata,
            int mprime);
static void adopt(struct message *parent, struct message *child, int dist);
static struct message *interlink(struct message *m, long count, int newmail);
static void finalize(struct message *mp);
static int mlonglt(const void *a, const void *b);
static int mfloatlt(const void *a, const void *b);
static int mcharlt(const void *a, const void *b);
static void lookup(struct message *m, struct mitem *mi, int mprime);
static void makethreads(struct message *m, long count, int newmail);
static char *skipre(const char *cp);
static int colpt(int *msgvec, int cl);
static void colps(struct message *b, int cl);
static void colpm(struct message *m, int cl, int *cc, int *uc);

/*
 * Return the hash value for a message id modulo mprime, or mprime
 * if the passed string does not look like a message-id.
 */
static unsigned 
mhash(const char *cp, int mprime)
{

      unsigned    h = 0, g, at = 0;

      cp--;
      while (*++cp) {
            /*
             * Pay attention not to hash characters which are
             * irrelevant for Message-ID semantics.
             */
            if (*cp == '(') {
                  cp = skip_comment(&cp[1]) - 1;
                  continue;
            }
            if (*cp == '"' || *cp == '\\')
                  continue;
            if (*cp == '@')
                  at++;
            h = ((h << 4) & 0xffffffff) + lowerconv(*cp & 0377);
            if ((g = h & 0xf0000000) != 0) {
                  h = h ^ (g >> 24);
                  h = h ^ g;
            }
      }
      return at ? h % mprime : mprime;
}

#define     NOT_AN_ID   ((struct mitem *)-1)

/*
 * Look up a message id. Returns NOT_AN_ID if the passed string does
 * not look like a message-id.
 */
static struct mitem *
mlook(char *id, struct mitem *mt, struct message *mdata, int mprime)
{
      struct mitem      *mp;
      unsigned    h, c, n = 0;

      if (id == NULL && (id = hfield("message-id", mdata)) == NULL)
            return NULL;
      if (mdata && mdata->m_idhash)
            h = ~mdata->m_idhash;
      else {
            h = mhash(id, mprime);
            if (h == mprime)
                  return NOT_AN_ID;
      }
      mp = &mt[c = h];
      while (mp->mi_id != NULL) {
            if (msgidcmp(mp->mi_id, id) == 0)
                  break;
            c += n&1 ? -((n+1)/2) * ((n+1)/2) : ((n+1)/2) * ((n+1)/2);
            n++;
            while (c >= mprime)
                  c -= mprime;
            mp = &mt[c];
      }
      if (mdata != NULL && mp->mi_id == NULL) {
            mp->mi_id = id;
            mp->mi_data = mdata;
            mdata->m_idhash = ~h;
      }
      return mp->mi_id ? mp : NULL;
}

/*
 * Child is to be adopted by parent. A thread tree is structured
 * as follows:
 *
 *  ------       m_child       ------        m_child
 *  |    |-------------------->|    |------------------------> . . .
 *  |    |<--------------------|    |<-----------------------  . . .
 *  ------      m_parent       ------       m_parent
 *     ^^                       |  ^
 *     | \____        m_younger |  |
 *     |      \                 |  |
 *     |       ----             |  |
 *     |           \            |  | m_elder
 *     |   m_parent ----        |  |
 *     |                \       |  |
 *     |                 ----   |  |
 *     |                     \  +  |
 *     |                       ------        m_child
 *     |                       |    |------------------------> . . .
 *     |                       |    |<-----------------------  . . .
 *     |                       ------       m_parent
 *     |                        |  ^
 *      \-----        m_younger |  |
 *            \                 |  |
 *             ----             |  |
 *                 \            |  | m_elder
 *         m_parent ----        |  |
 *                      \       |  |
 *                       ----   |  |
 *                           \  +  |
 *                             ------        m_child
 *                             |    |------------------------> . . .
 *                             |    |<-----------------------  . . .
 *                             ------       m_parent
 *                              |  ^
 *                              . . .
 *
 * The base message of a thread does not have a m_parent link. Elements
 * connected by m_younger/m_elder links are replies to the same message,
 * which is connected to them by m_parent links. The first reply to a
 * message gets the m_child link.
 */
static void 
adopt(struct message *parent, struct message *child, int dist)
{
      struct message    *mp, *mq;

      for (mp = parent; mp; mp = mp->m_parent)
            if (mp == child)
                  return;
      child->m_level = dist;  /* temporarily store distance */
      child->m_parent = parent;
      if (parent->m_child != NULL) {
            mq = NULL;
            for (mp = parent->m_child; mp; mp = mp->m_younger) {
                  if (mp->m_date >= child->m_date) {
                        if (mp->m_elder)
                              mp->m_elder->m_younger = child;
                        child->m_elder = mp->m_elder;
                        mp->m_elder = child;
                        child->m_younger = mp;
                        if (mp == parent->m_child)
                              parent->m_child = child;
                        return;
                  }
                  mq = mp;
            }
            mq->m_younger = child;
            child->m_elder = mq;
      } else
            parent->m_child = child;
}

/*
 * Connect all messages on the lowest thread level with m_younger/m_elder
 * links.
 */
static struct message *
interlink(struct message *m, long count, int newmail)
{
      int   i;
      long  n;
      struct msort      *ms;
      struct message    *root;
      int   autocollapse = !newmail && !(inhook&2) &&
                  value("autocollapse") != NULL;

      ms = smalloc(sizeof *ms * count);
      for (n = 0, i = 0; i < count; i++) {
            if (m[i].m_parent == NULL) {
                  if (autocollapse)
                        colps(&m[i], 1);
                  ms[n].ms_u.ms_long = m[i].m_date;
                  ms[n].ms_n = i;
                  n++;
            }
      }
      if (n > 0) {
            qsort(ms, n, sizeof *ms, mlonglt);
            root = &m[ms[0].ms_n];
            for (i = 1; i < n; i++) {
                  m[ms[i-1].ms_n].m_younger = &m[ms[i].ms_n];
                  m[ms[i].ms_n].m_elder = &m[ms[i-1].ms_n];
            }
      } else
            root = &m[0];
      free(ms);
      return root;
}

static void 
finalize(struct message *mp)
{
      long  n;

      for (n = 0; mp; mp = next_in_thread(mp)) {
            mp->m_threadpos = ++n;
            mp->m_level = mp->m_parent ?
                  mp->m_level + mp->m_parent->m_level : 0;
      }
}

static int 
mlonglt(const void *a, const void *b)
{
      int   i;

      i = ((struct msort *)a)->ms_u.ms_long -
            ((struct msort *)b)->ms_u.ms_long;
      if (i == 0)
            i = ((struct msort *)a)->ms_n - ((struct msort *)b)->ms_n;
      return i;
}

static int 
mfloatlt(const void *a, const void *b)
{
      float i;

      i = ((struct msort *)a)->ms_u.ms_float -
            ((struct msort *)b)->ms_u.ms_float;
      if (i == 0)
            i = ((struct msort *)a)->ms_n - ((struct msort *)b)->ms_n;
      return i > 0 ? 1 : i < 0 ? -1 : 0;
}

static int 
mcharlt(const void *a, const void *b)
{
      int   i;

      i = strcoll(((struct msort *)a)->ms_u.ms_char,
                  ((struct msort *)b)->ms_u.ms_char);
      if (i == 0)
            i = ((struct msort *)a)->ms_n - ((struct msort *)b)->ms_n;
      return i;
}


static void 
lookup(struct message *m, struct mitem *mi, int mprime)
{
      struct name *np;
      struct mitem      *ip;
      char  *cp;
      long  dist;

      if (m->m_flag & MHIDDEN)
            return;
      dist = 1;
      if ((cp = hfield("in-reply-to", m)) != NULL) {
            if ((np = extract(cp, GREF)) != NULL)
                  do {
                        if ((ip = mlook(np->n_name, mi, NULL, mprime))
                                    != NULL && ip != NOT_AN_ID) {
                              adopt(ip->mi_data, m, 1);
                              return;
                        }
                  } while ((np = np->n_flink) != NULL);
      }
      if ((cp = hfield("references", m)) != NULL) {
            if ((np = extract(cp, GREF)) != NULL) {
                  while (np->n_flink != NULL)
                        np = np->n_flink;
                  do {
                        if ((ip = mlook(np->n_name, mi, NULL, mprime))
                                    != NULL) {
                              if (ip == NOT_AN_ID)
                                    continue; /* skip dist++ */
                              adopt(ip->mi_data, m, dist);
                              return;
                        }
                        dist++;
                  } while ((np = np->n_blink) != NULL);
            }
      }
}

static void 
makethreads(struct message *m, long count, int newmail)
{
      struct mitem      *mt;
      char  *cp;
      long  i, mprime;

      if (count == 0)
            return;
      mprime = nextprime(count);
      mt = scalloc(mprime, sizeof *mt);
      for (i = 0; i < count; i++) {
            if ((m[i].m_flag&MHIDDEN) == 0) {
                  mlook(NULL, mt, &m[i], mprime);
                  if (m[i].m_date == 0) {
                        if ((cp = hfield("date", &m[i])) != NULL)
                              m[i].m_date = rfctime(cp);
                  }
            }
            m[i].m_child = m[i].m_younger = m[i].m_elder =
                  m[i].m_parent = NULL;
            m[i].m_level = 0;
            if (!newmail && !(inhook&2))
                  m[i].m_collapsed = 0;
      }
      /*
       * Most folders contain the eldest messages first. Traversing
       * them in descending order makes it more likely that younger
       * brothers are found first, so elder ones can be prepended to
       * the brother list, which is faster. The worst case is still
       * in O(n^2) and occurs when all but one messages in a folder
       * are replies to the one message, and are sorted such that
       * youngest messages occur first.
       */
      for (i = count-1; i >= 0; i--)
            lookup(&m[i], mt, mprime);
      threadroot = interlink(m, count, newmail);
      finalize(threadroot);
      free(mt);
      mb.mb_threaded = 1;
}

int 
thread(void *vp)
{
      if (mb.mb_threaded != 1 || vp == NULL || vp == (void *)-1) {
            if (mb.mb_type == MB_IMAP)
                  imap_getheaders(1, msgCount);
            makethreads(message, msgCount, vp == (void *)-1);
            free(mb.mb_sorted);
            mb.mb_sorted = sstrdup("thread");
      }
      if (vp && vp != (void *)-1 && !inhook && value("header"))
            return headers(vp);
      return 0;
}

int 
unthread(void *vp)
{
      struct message    *m;

      mb.mb_threaded = 0;
      free(mb.mb_sorted);
      mb.mb_sorted = NULL;
      for (m = &message[0]; m < &message[msgCount]; m++)
            m->m_collapsed = 0;
      if (vp && !inhook && value("header"))
            return headers(vp);
      return 0;
}

struct message *
next_in_thread(struct message *mp)
{
      if (mp->m_child)
            return mp->m_child;
      if (mp->m_younger)
            return mp->m_younger;
      while (mp->m_parent) {
            if (mp->m_parent->m_younger)
                  return mp->m_parent->m_younger;
            mp = mp->m_parent;
      }
      return NULL;
}

struct message *
prev_in_thread(struct message *mp)
{
      if (mp->m_elder) {
            mp = mp->m_elder;
            while (mp->m_child) {
                  mp = mp->m_child;
                  while (mp->m_younger)
                        mp = mp->m_younger;
            }
            return mp;
      }
      return mp->m_parent;
}

struct message *
this_in_thread(struct message *mp, long n)
{
      struct message    *mq;

      if (n == -1) {    /* find end of thread */
            while (mp) {
                  if (mp->m_younger) {
                        mp = mp->m_younger;
                        continue;
                  }
                  mq = next_in_thread(mp);
                  if (mq == NULL || mq->m_threadpos < mp->m_threadpos)
                        return mp;
                  mp = mq;
            }
            return NULL;
      }
      while (mp && mp->m_threadpos < n) {
            if (mp->m_younger && mp->m_younger->m_threadpos <= n) {
                  mp = mp->m_younger;
                  continue;
            }
            mp = next_in_thread(mp);
      }
      return mp && mp->m_threadpos == n ? mp : NULL;
}

/*
 * Sorted mode is internally just a variant of threaded mode with all
 * m_parent and m_child links being NULL.
 */
int 
sort(void *vp)
{
      enum method {
            SORT_SUBJECT,
            SORT_DATE,
            SORT_STATUS,
            SORT_SIZE,
            SORT_FROM,
            SORT_TO,
            SORT_SCORE,
            SORT_THREAD
      } method;
      struct {
            const char  *me_name;
            enum method me_method;
            int   (*me_func)(const void *, const void *);
      } methnames[] = {
            { "date",   SORT_DATE,  mlonglt },
            { "from",   SORT_FROM,  mcharlt },
            { "to",           SORT_TO,    mcharlt },
            { "subject",      SORT_SUBJECT,     mcharlt },
            { "size",   SORT_SIZE,  mlonglt },
            { "status", SORT_STATUS,      mlonglt },
            { "score",  SORT_SCORE, mfloatlt },
            { "thread", SORT_THREAD,      NULL },
            { NULL,           -1,         NULL }
      };
      char  **args = (char **)vp, *cp, *_args[2];
      int   (*func)(const void *, const void *);
      struct msort      *ms;
      struct str  in, out;
      int   i, n, msgvec[2];
      int   showname = value("showname") != NULL;
      struct message    *mp;

      msgvec[0] = dot - &message[0] + 1;
      msgvec[1] = 0;
      if (vp == NULL || vp == (void *)-1) {
            _args[0] = savestr(mb.mb_sorted);
            _args[1] = NULL;
            args = _args;
      } else if (args[0] == NULL) {
            printf("Current sorting criterion is: %s\n",
                        mb.mb_sorted ? mb.mb_sorted : "unsorted");
            return 0;
      }
      for (i = 0; methnames[i].me_name; i++)
            if (*args[0] && is_prefix(args[0], methnames[i].me_name))
                  break;
      if (methnames[i].me_name == NULL) {
            fprintf(stderr, "Unknown sorting method \"%s\"\n", args[0]);
            return 1;
      }
      method = methnames[i].me_method;
      func = methnames[i].me_func;
      free(mb.mb_sorted);
      mb.mb_sorted = sstrdup(args[0]);
      if (method == SORT_THREAD)
            return thread(vp && vp != (void *)-1 ? msgvec : vp);
      ms = ac_alloc(sizeof *ms * msgCount);
      switch (method) {
      case SORT_SUBJECT:
      case SORT_DATE:
      case SORT_FROM:
      case SORT_TO:
            if (mb.mb_type == MB_IMAP)
                  imap_getheaders(1, msgCount);
            break;
      default:
            break;
      }
      for (n = 0, i = 0; i < msgCount; i++) {
            mp = &message[i];
            if ((mp->m_flag&MHIDDEN) == 0) {
                  switch (method) {
                  case SORT_DATE:
                        if (mp->m_date == 0 &&
                                    (cp = hfield("date", mp)) != 0)
                              mp->m_date = rfctime(cp);
                        ms[n].ms_u.ms_long = mp->m_date;
                        break;
                  case SORT_STATUS:
                        if (mp->m_flag & MDELETED)
                              ms[n].ms_u.ms_long = 1;
                        else if ((mp->m_flag&(MNEW|MREAD)) == MNEW)
                              ms[n].ms_u.ms_long = 90;
                        else if (mp->m_flag & MFLAGGED)
                              ms[n].ms_u.ms_long = 85;
                        else if ((mp->m_flag&(MNEW|MBOX)) == MBOX)
                              ms[n].ms_u.ms_long = 70;
                        else if (mp->m_flag & MNEW)
                              ms[n].ms_u.ms_long = 80;
                        else if (mp->m_flag & MREAD)
                              ms[n].ms_u.ms_long = 40;
                        else
                              ms[n].ms_u.ms_long = 60;
                        break;
                  case SORT_SIZE:
                        ms[n].ms_u.ms_long = mp->m_xsize;
                        break;
                  case SORT_SCORE:
                        ms[n].ms_u.ms_float = mp->m_score;
                        break;
                  case SORT_FROM:
                  case SORT_TO:
                        if ((cp = hfield(method == SORT_FROM ?
                                    "from" : "to", mp)) != NULL) {
                              ms[n].ms_u.ms_char = showname ?
                                    realname(cp) : skin(cp);
                              makelow(ms[n].ms_u.ms_char);
                        } else
                              ms[n].ms_u.ms_char = "";
                        break;
                  default:
                  case SORT_SUBJECT:
                        if ((cp = hfield("subject", mp)) != NULL) {
                              in.s = cp;
                              in.l = strlen(in.s);
                              mime_fromhdr(&in, &out, TD_ICONV);
                              ms[n].ms_u.ms_char =
                                    savestr(skipre(out.s));
                              free(out.s);
                              makelow(ms[n].ms_u.ms_char);
                        } else
                              ms[n].ms_u.ms_char = "";
                        break;
                  }
                  ms[n++].ms_n = i;
            }
            mp->m_child = mp->m_younger = mp->m_elder = mp->m_parent = NULL;
            mp->m_level = 0;
            mp->m_collapsed = 0;
      }
      if (n > 0) {
            qsort(ms, n, sizeof *ms, func);
            threadroot = &message[ms[0].ms_n];
            for (i = 1; i < n; i++) {
                  message[ms[i-1].ms_n].m_younger = &message[ms[i].ms_n];
                  message[ms[i].ms_n].m_elder = &message[ms[i-1].ms_n];
            }
      } else
            threadroot = &message[0];
      finalize(threadroot);
      mb.mb_threaded = 2;
      ac_free(ms);
      return vp && vp != (void *)-1 && !inhook &&
            value("header") ? headers(msgvec) : 0;
}

static char *
skipre(const char *cp)
{
      if (lowerconv(cp[0]&0377) == 'r' &&
                  lowerconv(cp[1]&0377) == 'e' &&
                  cp[2] == ':' &&
                  spacechar(cp[3]&0377)) {
            cp = &cp[4];
            while (spacechar(*cp&0377))
                  cp++;
      }
      return (char *)cp;
}

int 
ccollapse(void *v)
{
      return colpt(v, 1);
}

int 
cuncollapse(void *v)
{
      return colpt(v, 0);
}

static int 
colpt(int *msgvec, int cl)
{
      int   *ip;

      if (mb.mb_threaded != 1) {
            puts("Not in threaded mode.");
            return 1;
      }
      for (ip = msgvec; *ip != 0; ip++)
            colps(&message[*ip-1], cl);
      return 0;
}

static void 
colps(struct message *b, int cl)
{
      struct message    *m;
      int   cc = 0, uc = 0;

      if (cl && (b->m_collapsed > 0 || (b->m_flag & (MNEW|MREAD)) == MNEW))
            return;
      if (b->m_child) {
            m = b->m_child;
            colpm(m, cl, &cc, &uc);
            for (m = m->m_younger; m; m = m->m_younger)
                  colpm(m, cl, &cc, &uc);
      }
      if (cl) {
            b->m_collapsed = -cc;
            for (m = b->m_parent; m; m = m->m_parent)
                  if (m->m_collapsed <= -uc ) {
                        m->m_collapsed += uc;
                        break;
                  }
      } else {
            if (b->m_collapsed > 0) {
                  b->m_collapsed = 0;
                  uc++;
            }
            for (m = b; m; m = m->m_parent)
                  if (m->m_collapsed <= -uc) {
                        m->m_collapsed += uc;
                        break;
                  }
      }
}

static void 
colpm(struct message *m, int cl, int *cc, int *uc)
{
      if (cl) {
            if (m->m_collapsed > 0)
                  (*uc)++;
            if ((m->m_flag & (MNEW|MREAD)) != MNEW || m->m_collapsed < 0)
                  m->m_collapsed = 1;
            if (m->m_collapsed > 0)
                  (*cc)++;
      } else {
            if (m->m_collapsed > 0) {
                  m->m_collapsed = 0;
                  (*uc)++;
            }
      }
      if (m->m_child) {
            m = m->m_child;
            colpm(m, cl, cc, uc);
            for (m = m->m_younger; m; m = m->m_younger)
                  colpm(m, cl, cc, uc);
      }
}

void 
uncollapse1(struct message *m, int always)
{
      if (mb.mb_threaded == 1 && (always || m->m_collapsed > 0))
            colps(m, 0);
}

Generated by  Doxygen 1.6.0   Back to index