/*
* 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);
}
syntax highlighted by Code2HTML, v. 0.9.1