/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
/*
* Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
*
* This library is free software: you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as published by
* the Free Software Foundation.
*
* This library is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
* or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
* for more details.
*
* You should have received a copy of the GNU Lesser General Public License
* along with this library. If not, see .
*
* Authors: Michael Zucchi
*/
/* TODO: This could probably be made a camel object, but it isn't really required */
#ifdef HAVE_CONFIG_H
#include
#endif
#include
#include
#include
#include
#include
#include
#include
#include "camel-folder-thread.h"
#define d(x)
#define m(x)
/*#define TIMEIT*/
#ifdef TIMEIT
#include
#endif
static void
container_add_child (CamelFolderThreadNode *node,
CamelFolderThreadNode *child)
{
d (printf ("\nAdding child %p to parent %p \n", child, node));
child->next = node->child;
node->child = child;
child->parent = node;
}
static void
container_parent_child (CamelFolderThreadNode *parent,
CamelFolderThreadNode *child)
{
CamelFolderThreadNode *c, *node;
/* are we already the right parent? */
if (child->parent == parent)
return;
/* would this create a loop? */
node = parent->parent;
while (node) {
if (node == child)
return;
node = node->parent;
}
/* are we unparented? */
if (child->parent == NULL) {
container_add_child (parent, child);
return;
}
/* else remove child from its existing parent, and reparent */
node = child->parent;
c = (CamelFolderThreadNode *) &node->child;
d (printf ("scanning children:\n"));
while (c->next) {
d (printf (" %p\n", c));
if (c->next == child) {
d (printf ("found node %p\n", child));
c->next = c->next->next;
child->parent = NULL;
container_add_child (parent, child);
return;
}
c = c->next;
}
printf ("DAMN, we shouldn't be here!\n");
}
static void
prune_empty (CamelFolderThread *thread,
CamelFolderThreadNode **cp)
{
CamelFolderThreadNode *child, *next, *c, *lastc;
/* yes, this is intentional */
lastc = (CamelFolderThreadNode *) cp;
while (lastc->next) {
c = lastc->next;
prune_empty (thread, &c->child);
d (printf (
"checking message %p %p (%08x%08x)\n", c,
c->message,
c->message ? c->message->message_id.id.part.hi : 0,
c->message ? c->message->message_id.id.part.lo : 0));
if (c->message == NULL) {
if (c->child == NULL) {
d (printf ("removing empty node\n"));
lastc->next = c->next;
m (memset (c, 0xfe, sizeof (*c)));
camel_memchunk_free (thread->node_chunks, c);
continue;
}
if (c->parent || c->child->next == NULL) {
d (printf ("promoting child\n"));
lastc->next = c->next; /* remove us */
child = c->child;
while (child) {
next = child->next;
child->parent = c->parent;
child->next = lastc->next;
lastc->next = child;
child = next;
}
continue;
}
}
lastc = c;
}
}
static void
hashloop (gpointer key,
gpointer value,
gpointer data)
{
CamelFolderThreadNode *c = value;
CamelFolderThreadNode *tail = data;
if (c->parent == NULL) {
c->next = tail->next;
tail->next = c;
}
}
static gchar *
skip_list_ids (gchar *s)
{
gchar *p;
while (isspace (*s))
s++;
while (*s == '[') {
p = s + 1;
while (*p && *p != ']' && !isspace (*p))
p++;
if (*p != ']')
break;
s = p + 1;
while (isspace (*s))
s++;
if (*s == '-' && isspace (s[1]))
s += 2;
while (isspace (*s))
s++;
}
return s;
}
static gchar *
get_root_subject (CamelFolderThreadNode *c)
{
gchar *s, *p;
CamelFolderThreadNode *scan;
s = NULL;
c->re = FALSE;
if (c->message)
s = (gchar *) camel_message_info_subject (c->message);
else {
/* one of the children will always have a message */
scan = c->child;
while (scan) {
if (scan->message) {
s = (gchar *) camel_message_info_subject (scan->message);
break;
}
scan = scan->next;
}
}
if (s != NULL) {
s = skip_list_ids (s);
while (*s) {
while (isspace (*s))
s++;
if (s[0] == 0)
break;
if ((s[0] == 'r' || s[0]=='R')
&& (s[1] == 'e' || s[1]=='E')) {
p = s + 2;
while (isdigit (*p) || (ispunct (*p) && (*p != ':')))
p++;
if (*p == ':') {
c->re = TRUE;
s = skip_list_ids (p + 1);
} else
break;
} else
break;
}
if (*s)
return s;
}
return NULL;
}
/* this can be pretty slow, but not used often */
/* clast cannot be null */
static void
remove_node (CamelFolderThreadNode **list,
CamelFolderThreadNode *node,
CamelFolderThreadNode **clast)
{
CamelFolderThreadNode *c;
/* this is intentional, even if it looks funny */
/* if we have a parent, then we should remove it from the parent list,
* otherwise we remove it from the root list */
if (node->parent) {
c = (CamelFolderThreadNode *) &node->parent->child;
} else {
c = (CamelFolderThreadNode *) list;
}
while (c->next) {
if (c->next == node) {
if (*clast == c->next)
*clast = c;
c->next = c->next->next;
return;
}
c = c->next;
}
printf ("ERROR: removing node %p failed\n", (gpointer) node);
}
static void
group_root_set (CamelFolderThread *thread,
CamelFolderThreadNode **cp)
{
GHashTable *subject_table = g_hash_table_new (g_str_hash, g_str_equal);
CamelFolderThreadNode *c, *clast, *scan, *container;
/* gather subject lines */
d (printf ("gathering subject lines\n"));
clast = (CamelFolderThreadNode *) cp;
c = clast->next;
while (c) {
c->root_subject = get_root_subject (c);
if (c->root_subject) {
container = g_hash_table_lookup (subject_table, c->root_subject);
if (container == NULL
|| (container->message == NULL && c->message)
|| (container->re == TRUE && !c->re)) {
g_hash_table_insert (subject_table, c->root_subject, c);
}
}
c = c->next;
}
/* merge common subjects? */
clast = (CamelFolderThreadNode *) cp;
while (clast->next) {
c = clast->next;
d (printf ("checking %p %s\n", c, c->root_subject));
if (c->root_subject
&& (container = g_hash_table_lookup (subject_table, c->root_subject))
&& (container != c)) {
d (printf (" matching %p %s\n", container, container->root_subject));
if (c->message == NULL && container->message == NULL) {
d (printf ("merge containers children\n"));
/* steal the children from c onto container, and unlink c */
scan = (CamelFolderThreadNode *) &container->child;
while (scan->next)
scan = scan->next;
scan->next = c->child;
clast->next = c->next;
m (memset (c, 0xee, sizeof (*c)));
camel_memchunk_free (thread->node_chunks, c);
continue;
} if (c->message == NULL && container->message != NULL) {
d (printf ("container is non-empty parent\n"));
remove_node (cp, container, &clast);
container_add_child (c, container);
} else if (c->message != NULL && container->message == NULL) {
d (printf ("container is empty child\n"));
clast->next = c->next;
container_add_child (container, c);
continue;
} else if (c->re && !container->re) {
d (printf ("container is re\n"));
clast->next = c->next;
container_add_child (container, c);
continue;
} else if (!c->re && container->re) {
d (printf ("container is not re\n"));
remove_node (cp, container, &clast);
container_add_child (c, container);
} else {
d (printf ("subjects are common %p and %p\n", c, container));
/* build a phantom node */
remove_node (cp, container, &clast);
remove_node (cp, c, &clast);
scan = camel_memchunk_alloc0 (thread->node_chunks);
scan->root_subject = c->root_subject;
scan->re = c->re && container->re;
scan->next = c->next;
clast->next = scan;
container_add_child (scan, c);
container_add_child (scan, container);
clast = scan;
g_hash_table_insert (subject_table, scan->root_subject, scan);
continue;
}
}
clast = c;
}
g_hash_table_destroy (subject_table);
}
struct _tree_info {
GHashTable *visited;
};
static gint
dump_tree_rec (struct _tree_info *info,
CamelFolderThreadNode *c,
gint depth)
{
gchar *p;
gint count = 0;
p = alloca (depth * 2 + 1);
memset (p, ' ', depth * 2);
p[depth * 2] = 0;
while (c) {
if (g_hash_table_lookup (info->visited, c)) {
printf ("WARNING: NODE REVISITED: %p\n", (gpointer) c);
} else {
g_hash_table_insert (info->visited, c, c);
}
if (c->message) {
printf (
"%s %p Subject: %s <%08x%08x>\n",
p, (gpointer) c,
camel_message_info_subject (c->message),
camel_message_info_message_id (c->message)->id.part.hi,
camel_message_info_message_id (c->message)->id.part.lo);
count += 1;
} else {
printf ("%s %p \n", p, (gpointer) c);
}
if (c->child)
count += dump_tree_rec (info, c->child, depth + 1);
c = c->next;
}
return count;
}
gint
camel_folder_threaded_messages_dump (CamelFolderThreadNode *c)
{
gint count;
struct _tree_info info;
info.visited = g_hash_table_new (g_direct_hash, g_direct_equal);
count = dump_tree_rec (&info, c, 0);
g_hash_table_destroy (info.visited);
return count;
}
static gint
sort_node (gconstpointer a,
gconstpointer b)
{
const CamelFolderThreadNode *a1 = ((CamelFolderThreadNode **) a)[0];
const CamelFolderThreadNode *b1 = ((CamelFolderThreadNode **) b)[0];
/* if we have no message, it must be a dummy node, which
* also means it must have a child, just use that as the
* sort data (close enough?) */
if (a1->message == NULL)
a1 = a1->child;
if (b1->message == NULL)
b1 = b1->child;
if (a1->order == b1->order)
return 0;
if (a1->order < b1->order)
return -1;
else
return 1;
}
static void
sort_thread (CamelFolderThreadNode **cp)
{
CamelFolderThreadNode *c, *head, **carray;
gint size = 0;
c = *cp;
while (c) {
/* sort the children while we're at it */
if (c->child)
sort_thread (&c->child);
size++;
c = c->next;
}
if (size < 2)
return;
carray = alloca (size * sizeof (CamelFolderThreadNode *));
c = *cp;
size = 0;
while (c) {
carray[size] = c;
c = c->next;
size++;
}
qsort (carray, size, sizeof (CamelFolderThreadNode *), sort_node);
size--;
head = carray[size];
head->next = NULL;
size--;
do {
c = carray[size];
c->next = head;
head = c;
size--;
} while (size >= 0);
*cp = head;
}
static guint
id_hash (gpointer key)
{
CamelSummaryMessageID *id = (CamelSummaryMessageID *) key;
return id->id.part.lo;
}
static gint
id_equal (gpointer a,
gpointer b)
{
return ((CamelSummaryMessageID *) a)->id.id == ((CamelSummaryMessageID *) b)->id.id;
}
/* perform actual threading */
static void
thread_summary (CamelFolderThread *thread,
GPtrArray *summary)
{
GHashTable *id_table, *no_id_table;
gint i;
CamelFolderThreadNode *c, *child, *head;
#ifdef TIMEIT
struct timeval start, end;
gulong diff;
gettimeofday (&start, NULL);
#endif
id_table = g_hash_table_new ((GHashFunc) id_hash, (GCompareFunc) id_equal);
no_id_table = g_hash_table_new (NULL, NULL);
for (i = 0; i < summary->len; i++) {
CamelMessageInfo *mi = summary->pdata[i];
const CamelSummaryMessageID *mid = camel_message_info_message_id (mi);
const CamelSummaryReferences *references = camel_message_info_references (mi);
if (mid != NULL && mid->id.id) {
c = g_hash_table_lookup (id_table, mid);
/* check for duplicate messages */
if (c && c->order) {
/* if duplicate, just make out it is a no-id message, but try and insert it
* into the right spot in the tree */
d (printf ("doing: (duplicate message id)\n"));
c = camel_memchunk_alloc0 (thread->node_chunks);
g_hash_table_insert (no_id_table, (gpointer) mi, c);
} else if (!c) {
d (printf ("doing : %08x%08x (%s)\n", mid->id.part.hi, mid->id.part.lo, camel_message_info_subject (mi)));
c = camel_memchunk_alloc0 (thread->node_chunks);
g_hash_table_insert (id_table, (gpointer) mid, c);
}
} else {
d (printf ("doing : (no message id)\n"));
c = camel_memchunk_alloc0 (thread->node_chunks);
g_hash_table_insert (no_id_table, (gpointer) mi, c);
}
c->message = mi;
c->order = i + 1;
child = c;
if (references) {
gint j;
d (printf ("%s (%s) references:\n", G_STRLOC, G_STRFUNC); )
for (j = 0; j < references->size; j++) {
gboolean found = FALSE;
/* should never be empty, but just incase */
if (references->references[j].id.id == 0)
continue;
c = g_hash_table_lookup (id_table, &references->references[j]);
if (c == NULL) {
d (printf ("%s (%s) not found\n", G_STRLOC, G_STRFUNC));
c = camel_memchunk_alloc0 (thread->node_chunks);
g_hash_table_insert (id_table, (gpointer) &references->references[j], c);
} else
found = TRUE;
if (c != child) {
container_parent_child (c, child);
/* Stop on the first parent found, no need to reparent
* it once it's placed in. Also, references are from
* parent to root, thus this should do the right thing. */
if (found)
break;
}
child = c;
}
}
}
d (printf ("\n\n"));
/* build a list of root messages (no parent) */
head = NULL;
g_hash_table_foreach (id_table, hashloop, &head);
g_hash_table_foreach (no_id_table, hashloop, &head);
g_hash_table_destroy (id_table);
g_hash_table_destroy (no_id_table);
/* remove empty parent nodes */
prune_empty (thread, &head);
/* find any siblings which missed out - but only if we are allowing threading by subject */
if (thread->subject)
group_root_set (thread, &head);
#if 0
printf ("finished\n");
i = camel_folder_threaded_messages_dump (head);
printf ("%d count, %d items in tree\n", summary->len, i);
#endif
sort_thread (&head);
/* remove any phantom nodes, this could possibly be put in group_root_set()? */
c = (CamelFolderThreadNode *) &head;
while (c && c->next) {
CamelFolderThreadNode *scan, *newtop;
child = c->next;
if (child->message == NULL) {
newtop = child->child;
newtop->parent = NULL;
/* unlink pseudo node */
c->next = newtop;
/* link its siblings onto the end of its children, fix all parent pointers */
scan = (CamelFolderThreadNode *) &newtop->child;
while (scan->next) {
scan = scan->next;
}
scan->next = newtop->next;
while (scan->next) {
scan = scan->next;
scan->parent = newtop;
}
/* and link the now 'real' node into the list */
newtop->next = child->next;
c = newtop;
m (memset (child, 0xde, sizeof (*child)));
camel_memchunk_free (thread->node_chunks, child);
} else {
c = child;
}
}
/* this is only debug assertion stuff */
c = (CamelFolderThreadNode *) &head;
while (c->next) {
c = c->next;
if (c->message == NULL)
g_warning ("threading missed removing a pseudo node: %s\n", c->root_subject);
if (c->parent != NULL)
g_warning ("base node has a non-null parent: %s\n", c->root_subject);
}
thread->tree = head;
#ifdef TIMEIT
gettimeofday (&end, NULL);
diff = end.tv_sec * 1000 + end.tv_usec / 1000;
diff -= start.tv_sec * 1000 + start.tv_usec / 1000;
printf (
"Message threading %d messages took %ld.%03ld seconds\n",
summary->len, diff / 1000, diff % 1000);
#endif
}
/**
* camel_folder_thread_messages_new:
* @folder:
* @uids: The subset of uid's to thread. If NULL. then thread all
* uid's in @folder.
* @thread_subject: thread based on subject also
*
* Thread a (subset) of the messages in a folder. And sort the result
* in summary order.
*
* If @thread_subject is %TRUE, messages with
* related subjects will also be threaded. The default behaviour is to
* only thread based on message-id.
*
* This function is probably to be removed soon.
*
* Returns: A CamelFolderThread contianing a tree of CamelFolderThreadNode's
* which represent the threaded structure of the messages.
**/
CamelFolderThread *
camel_folder_thread_messages_new (CamelFolder *folder,
GPtrArray *uids,
gboolean thread_subject)
{
CamelFolderThread *thread;
GPtrArray *summary;
GPtrArray *fsummary = NULL;
gint i;
thread = g_malloc (sizeof (*thread));
thread->refcount = 1;
thread->subject = thread_subject;
thread->tree = NULL;
thread->node_chunks = camel_memchunk_new (32, sizeof (CamelFolderThreadNode));
thread->folder = g_object_ref (folder);
camel_folder_summary_prepare_fetch_all (folder->summary, NULL);
thread->summary = summary = g_ptr_array_new ();
/* prefer given order from the summary order */
if (!uids) {
fsummary = camel_folder_summary_get_array (folder->summary);
uids = fsummary;
}
for (i = 0; i < uids->len; i++) {
CamelMessageInfo *info;
gchar *uid = uids->pdata[i];
info = camel_folder_get_message_info (folder, uid);
if (info)
g_ptr_array_add (summary, info);
/* FIXME: Check if the info is leaking */
}
if (fsummary)
camel_folder_summary_free_array (fsummary);
thread_summary (thread, summary);
return thread;
}
/* add any still there, in the existing order */
static void
add_present_rec (CamelFolderThread *thread,
GHashTable *have,
GPtrArray *summary,
CamelFolderThreadNode *node)
{
while (node) {
CamelMessageInfo *info;
const gchar *uid;
/* XXX Casting away const. */
info = (CamelMessageInfo *) node->message;
uid = camel_message_info_uid (info);
if (g_hash_table_lookup (have, uid)) {
g_hash_table_remove (have, uid);
g_ptr_array_add (summary, info);
} else {
camel_message_info_unref (info);
}
if (node->child)
add_present_rec (thread, have, summary, node->child);
node = node->next;
}
}
void
camel_folder_thread_messages_apply (CamelFolderThread *thread,
GPtrArray *uids)
{
gint i;
GPtrArray *all;
GHashTable *table;
CamelMessageInfo *info;
all = g_ptr_array_new ();
table = g_hash_table_new (g_str_hash, g_str_equal);
for (i = 0; i < uids->len; i++)
g_hash_table_insert (table, uids->pdata[i], uids->pdata[i]);
add_present_rec (thread, table, all, thread->tree);
/* add any new ones, in supplied order */
for (i = 0; i < uids->len; i++)
if (g_hash_table_lookup (table, uids->pdata[i]) && (info = camel_folder_get_message_info (thread->folder, uids->pdata[i])))
g_ptr_array_add (all, info);
g_hash_table_destroy (table);
thread->tree = NULL;
camel_memchunk_destroy (thread->node_chunks);
thread->node_chunks = camel_memchunk_new (32, sizeof (CamelFolderThreadNode));
thread_summary (thread, all);
g_ptr_array_free (thread->summary, TRUE);
thread->summary = all;
}
void
camel_folder_thread_messages_ref (CamelFolderThread *thread)
{
thread->refcount++;
}
/**
* camel_folder_thread_messages_unref:
* @thread:
*
* Free all memory associated with the thread descriptor @thread.
**/
void
camel_folder_thread_messages_unref (CamelFolderThread *thread)
{
if (thread->refcount > 1) {
thread->refcount--;
return;
}
if (thread->folder) {
gint i;
for (i = 0; i < thread->summary->len; i++)
camel_message_info_unref (thread->summary->pdata[i]);
g_ptr_array_free (thread->summary, TRUE);
g_object_unref (thread->folder);
}
camel_memchunk_destroy (thread->node_chunks);
g_free (thread);
}
#if 0
/**
* camel_folder_thread_messages_new_summary:
* @summary: Array of CamelMessageInfo's to thread.
*
* Thread a list of MessageInfo's. The summary must remain valid for the
* life of the CamelFolderThread created by this function, and it is upto the
* caller to ensure this.
*
* Returns: A CamelFolderThread contianing a tree of CamelFolderThreadNode's
* which represent the threaded structure of the messages.
**/
CamelFolderThread *
camel_folder_thread_messages_new_summary (GPtrArray *summary)
{
CamelFolderThread *thread;
#ifdef TIMEIT
struct timeval start, end;
gulong diff;
gettimeofday (&start, NULL);
#endif
thread = g_malloc (sizeof (*thread));
thread->refcount = 1;
thread->tree = NULL;
thread->node_chunks = camel_memchunk_new (32, sizeof (CamelFolderThreadNode));
thread->folder = NULL;
thread->summary = NULL;
thread_summary (thread, summary);
return thread;
}
/* scan the list in depth-first fashion */
static void
build_summary_rec (GHashTable *have,
GPtrArray *summary,
CamelFolderThreadNode *node)
{
while (node) {
if (node->message)
g_hash_table_insert (have, (gchar *) camel_message_info_uid (node->message), node->message);
g_ptr_array_add (summary, node);
if (node->child)
build_summary_rec (have, summary, node->child);
node = node->next;
}
}
void
camel_folder_thread_messages_add (CamelFolderThread *thread,
GPtrArray *summary)
{
GPtrArray *all;
gint i;
GHashTable *table;
/* Instead of working out all the complex in's and out's of
* trying to do an incremental summary generation, just redo the whole
* thing with the summary in the current order - so it comes out
* in the same order */
all = g_ptr_array_new ();
table = g_hash_table_new (g_str_hash, g_str_equal);
build_summary_rec (table, all, thread->tree);
for (i = 0; i < summary->len; i++) {
CamelMessageInfo *info = summary->pdata[i];
/* check its not already there, we dont want duplicates */
if (g_hash_table_lookup (table, camel_message_info_uid (info)) == NULL)
g_ptr_array_add (all, info);
}
g_hash_table_destroy (table);
/* reset the tree, and rebuild fully */
thread->tree = NULL;
camel_memchunk_empty (thread->node_chunks);
thread_summary (thread, all);
}
static void
remove_uid_node_rec (CamelFolderThread *thread,
GHashTable *table,
CamelFolderThreadNode **list,
CamelFolderThreadNode *parent)
{
CamelFolderThreadNode *prev = NULL;
CamelFolderThreadNode *node, *next, *child, *rest;
node = (CamelFolderThreadNode *) list;
next = node->next;
while (next) {
if (next->child)
remove_uid_node_rec (thread, table, &next->child, next);
/* do we have a node to remove? */
if (next->message && g_hash_table_lookup (table, (gchar *) camel_message_info_uid (node->message))) {
child = next->child;
if (child) {
/*
* node
* next
* child
* lchild
* rest
*
* becomes:
* node
* child
* lchild
* rest
*/
rest = next->next;
node->next = child;
camel_memchunk_free (thread->node_chunks, next);
next = child;
do {
lchild = child;
child->parent = parent;
child = child->next;
} while (child);
lchild->next = rest;
} else {
/*
* node
* next
* rest
* becomes:
* node
* rest */
node->next = next->next;
camel_memchunk_free (thread->node_chunks, next);
next = node->next;
}
} else {
node = next;
next = node->next;
}
}
}
void
camel_folder_thread_messages_remove (CamelFolderThread *thread,
GPtrArray *uids)
{
GHashTable *table;
gint i;
table = g_hash_table_new (g_str_hash, g_str_equal);
for (i = 0; i < uids->len; i++)
g_hash_table_insert (table, uids->pdata[i], uids->pdata[i]);
remove_uid_node_rec (thread, table, &thread->tree, NULL);
g_hash_table_destroy (table);
}
#endif