1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
3 * Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
5 * Authors: Michael Zucchi <notzed@ximian.com>
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of version 2 of the GNU Lesser General Public
9 * License as published by the Free Software Foundation.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * General Public License for more details.
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this program; if not, write to the
18 * Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
22 /* TODO: This could probably be made a camel object, but it isn't really required */
34 #include <sys/types.h>
36 #include "camel-folder-thread.h"
48 container_add_child (CamelFolderThreadNode *node,
49 CamelFolderThreadNode *child)
51 d (printf ("\nAdding child %p to parent %p \n", child, node));
52 child->next = node->child;
58 container_parent_child (CamelFolderThreadNode *parent,
59 CamelFolderThreadNode *child)
61 CamelFolderThreadNode *c, *node;
63 /* are we already the right parent? */
64 if (child->parent == parent)
67 /* would this create a loop? */
68 node = parent->parent;
75 /* are we unparented? */
76 if (child->parent == NULL) {
77 container_add_child (parent, child);
81 /* else remove child from its existing parent, and reparent */
83 c = (CamelFolderThreadNode *) &node->child;
84 d (printf ("scanning children:\n"));
86 d (printf (" %p\n", c));
87 if (c->next == child) {
88 d (printf ("found node %p\n", child));
89 c->next = c->next->next;
91 container_add_child (parent, child);
97 printf ("DAMN, we shouldn't be here!\n");
101 prune_empty (CamelFolderThread *thread,
102 CamelFolderThreadNode **cp)
104 CamelFolderThreadNode *child, *next, *c, *lastc;
106 /* yes, this is intentional */
107 lastc = (CamelFolderThreadNode *) cp;
108 while (lastc->next) {
110 prune_empty (thread, &c->child);
113 "checking message %p %p (%08x%08x)\n", c,
115 c->message ? c->message->message_id.id.part.hi : 0,
116 c->message ? c->message->message_id.id.part.lo : 0));
117 if (c->message == NULL) {
118 if (c->child == NULL) {
119 d (printf ("removing empty node\n"));
120 lastc->next = c->next;
121 m (memset (c, 0xfe, sizeof (*c)));
122 camel_memchunk_free (thread->node_chunks, c);
125 if (c->parent || c->child->next == NULL) {
126 d (printf ("promoting child\n"));
127 lastc->next = c->next; /* remove us */
132 child->parent = c->parent;
133 child->next = lastc->next;
146 hashloop (gpointer key,
150 CamelFolderThreadNode *c = value;
151 CamelFolderThreadNode *tail = data;
153 if (c->parent == NULL) {
154 c->next = tail->next;
160 get_root_subject (CamelFolderThreadNode *c)
163 CamelFolderThreadNode *scan;
168 s = (gchar *) camel_message_info_subject (c->message);
170 /* one of the children will always have a message */
174 s = (gchar *) camel_message_info_subject (scan->message);
186 if ((s[0] == 'r' || s[0]=='R')
187 && (s[1] == 'e' || s[1]=='E')) {
189 while (isdigit (*p) || (ispunct (*p) && (*p != ':')))
205 /* this can be pretty slow, but not used often */
206 /* clast cannot be null */
208 remove_node (CamelFolderThreadNode **list,
209 CamelFolderThreadNode *node,
210 CamelFolderThreadNode **clast)
212 CamelFolderThreadNode *c;
214 /* this is intentional, even if it looks funny */
215 /* if we have a parent, then we should remove it from the parent list,
216 * otherwise we remove it from the root list */
218 c = (CamelFolderThreadNode *) &node->parent->child;
220 c = (CamelFolderThreadNode *) list;
223 if (c->next == node) {
224 if (*clast == c->next)
226 c->next = c->next->next;
232 printf ("ERROR: removing node %p failed\n", (gpointer) node);
236 group_root_set (CamelFolderThread *thread,
237 CamelFolderThreadNode **cp)
239 GHashTable *subject_table = g_hash_table_new (g_str_hash, g_str_equal);
240 CamelFolderThreadNode *c, *clast, *scan, *container;
242 /* gather subject lines */
243 d (printf ("gathering subject lines\n"));
244 clast = (CamelFolderThreadNode *) cp;
247 c->root_subject = get_root_subject (c);
248 if (c->root_subject) {
249 container = g_hash_table_lookup (subject_table, c->root_subject);
250 if (container == NULL
251 || (container->message == NULL && c->message)
252 || (container->re == TRUE && !c->re)) {
253 g_hash_table_insert (subject_table, c->root_subject, c);
259 /* merge common subjects? */
260 clast = (CamelFolderThreadNode *) cp;
261 while (clast->next) {
263 d (printf ("checking %p %s\n", c, c->root_subject));
265 && (container = g_hash_table_lookup (subject_table, c->root_subject))
266 && (container != c)) {
267 d (printf (" matching %p %s\n", container, container->root_subject));
268 if (c->message == NULL && container->message == NULL) {
269 d (printf ("merge containers children\n"));
270 /* steal the children from c onto container, and unlink c */
271 scan = (CamelFolderThreadNode *) &container->child;
274 scan->next = c->child;
275 clast->next = c->next;
276 m (memset (c, 0xee, sizeof (*c)));
277 camel_memchunk_free (thread->node_chunks, c);
279 } if (c->message == NULL && container->message != NULL) {
280 d (printf ("container is non-empty parent\n"));
281 remove_node (cp, container, &clast);
282 container_add_child (c, container);
283 } else if (c->message != NULL && container->message == NULL) {
284 d (printf ("container is empty child\n"));
285 clast->next = c->next;
286 container_add_child (container, c);
288 } else if (c->re && !container->re) {
289 d (printf ("container is re\n"));
290 clast->next = c->next;
291 container_add_child (container, c);
293 } else if (!c->re && container->re) {
294 d (printf ("container is not re\n"));
295 remove_node (cp, container, &clast);
296 container_add_child (c, container);
298 d (printf ("subjects are common %p and %p\n", c, container));
300 /* build a phantom node */
301 remove_node (cp, container, &clast);
302 remove_node (cp, c, &clast);
304 scan = camel_memchunk_alloc0 (thread->node_chunks);
306 scan->root_subject = c->root_subject;
307 scan->re = c->re && container->re;
308 scan->next = c->next;
310 container_add_child (scan, c);
311 container_add_child (scan, container);
313 g_hash_table_insert (subject_table, scan->root_subject, scan);
319 g_hash_table_destroy (subject_table);
327 dump_tree_rec (struct _tree_info *info,
328 CamelFolderThreadNode *c,
334 p = alloca (depth * 2 + 1);
335 memset (p, ' ', depth * 2);
339 if (g_hash_table_lookup (info->visited, c)) {
340 printf ("WARNING: NODE REVISITED: %p\n", (gpointer) c);
342 g_hash_table_insert (info->visited, c, c);
346 "%s %p Subject: %s <%08x%08x>\n",
348 camel_message_info_subject (c->message),
349 camel_message_info_message_id (c->message)->id.part.hi,
350 camel_message_info_message_id (c->message)->id.part.lo);
353 printf ("%s %p <empty>\n", p, (gpointer) c);
356 count += dump_tree_rec (info, c->child, depth + 1);
363 camel_folder_threaded_messages_dump (CamelFolderThreadNode *c)
366 struct _tree_info info;
368 info.visited = g_hash_table_new (g_direct_hash, g_direct_equal);
369 count = dump_tree_rec (&info, c, 0);
370 g_hash_table_destroy (info.visited);
375 sort_node (gconstpointer a,
378 const CamelFolderThreadNode *a1 = ((CamelFolderThreadNode **) a)[0];
379 const CamelFolderThreadNode *b1 = ((CamelFolderThreadNode **) b)[0];
381 /* if we have no message, it must be a dummy node, which
382 * also means it must have a child, just use that as the
383 * sort data (close enough?) */
384 if (a1->message == NULL)
386 if (b1->message == NULL)
388 if (a1->order == b1->order)
390 if (a1->order < b1->order)
397 sort_thread (CamelFolderThreadNode **cp)
399 CamelFolderThreadNode *c, *head, **carray;
404 /* sort the children while we're at it */
406 sort_thread (&c->child);
412 carray = alloca (size * sizeof (CamelFolderThreadNode *));
420 qsort (carray, size, sizeof (CamelFolderThreadNode *), sort_node);
435 id_hash (gpointer key)
437 CamelSummaryMessageID *id = (CamelSummaryMessageID *) key;
439 return id->id.part.lo;
443 id_equal (gpointer a,
446 return ((CamelSummaryMessageID *) a)->id.id == ((CamelSummaryMessageID *) b)->id.id;
449 /* perform actual threading */
451 thread_summary (CamelFolderThread *thread,
454 GHashTable *id_table, *no_id_table;
456 CamelFolderThreadNode *c, *child, *head;
458 struct timeval start, end;
461 gettimeofday (&start, NULL);
464 id_table = g_hash_table_new ((GHashFunc) id_hash, (GCompareFunc) id_equal);
465 no_id_table = g_hash_table_new (NULL, NULL);
466 for (i = 0; i < summary->len; i++) {
467 CamelMessageInfo *mi = summary->pdata[i];
468 const CamelSummaryMessageID *mid = camel_message_info_message_id (mi);
469 const CamelSummaryReferences *references = camel_message_info_references (mi);
471 if (mid != NULL && mid->id.id) {
472 c = g_hash_table_lookup (id_table, mid);
473 /* check for duplicate messages */
475 /* if duplicate, just make out it is a no-id message, but try and insert it
476 * into the right spot in the tree */
477 d (printf ("doing: (duplicate message id)\n"));
478 c = camel_memchunk_alloc0 (thread->node_chunks);
479 g_hash_table_insert (no_id_table, (gpointer) mi, c);
481 d (printf ("doing : %08x%08x (%s)\n", mid->id.part.hi, mid->id.part.lo, camel_message_info_subject (mi)));
482 c = camel_memchunk_alloc0 (thread->node_chunks);
483 g_hash_table_insert (id_table, (gpointer) mid, c);
486 d (printf ("doing : (no message id)\n"));
487 c = camel_memchunk_alloc0 (thread->node_chunks);
488 g_hash_table_insert (no_id_table, (gpointer) mi, c);
497 d (printf ("%s (%s) references:\n", G_STRLOC, G_STRFUNC); )
498 for (j = 0; j < references->size; j++) {
499 gboolean found = FALSE;
501 /* should never be empty, but just incase */
502 if (references->references[j].id.id == 0)
505 c = g_hash_table_lookup (id_table, &references->references[j]);
507 d (printf ("%s (%s) not found\n", G_STRLOC, G_STRFUNC));
508 c = camel_memchunk_alloc0 (thread->node_chunks);
509 g_hash_table_insert (id_table, (gpointer) &references->references[j], c);
513 container_parent_child (c, child);
514 /* Stop on the first parent found, no need to reparent
515 * it once it's placed in. Also, references are from
516 * parent to root, thus this should do the right thing. */
526 /* build a list of root messages (no parent) */
528 g_hash_table_foreach (id_table, hashloop, &head);
529 g_hash_table_foreach (no_id_table, hashloop, &head);
531 g_hash_table_destroy (id_table);
532 g_hash_table_destroy (no_id_table);
534 /* remove empty parent nodes */
535 prune_empty (thread, &head);
537 /* find any siblings which missed out - but only if we are allowing threading by subject */
539 group_root_set (thread, &head);
542 printf ("finished\n");
543 i = camel_folder_threaded_messages_dump (head);
544 printf ("%d count, %d items in tree\n", summary->len, i);
549 /* remove any phantom nodes, this could possibly be put in group_root_set()? */
550 c = (CamelFolderThreadNode *) &head;
551 while (c && c->next) {
552 CamelFolderThreadNode *scan, *newtop;
555 if (child->message == NULL) {
556 newtop = child->child;
557 newtop->parent = NULL;
558 /* unlink pseudo node */
561 /* link its siblings onto the end of its children, fix all parent pointers */
562 scan = (CamelFolderThreadNode *) &newtop->child;
566 scan->next = newtop->next;
569 scan->parent = newtop;
572 /* and link the now 'real' node into the list */
573 newtop->next = child->next;
575 m (memset (child, 0xde, sizeof (*child)));
576 camel_memchunk_free (thread->node_chunks, child);
582 /* this is only debug assertion stuff */
583 c = (CamelFolderThreadNode *) &head;
586 if (c->message == NULL)
587 g_warning ("threading missed removing a pseudo node: %s\n", c->root_subject);
588 if (c->parent != NULL)
589 g_warning ("base node has a non-null parent: %s\n", c->root_subject);
595 gettimeofday (&end, NULL);
596 diff = end.tv_sec * 1000 + end.tv_usec / 1000;
597 diff -= start.tv_sec * 1000 + start.tv_usec / 1000;
599 "Message threading %d messages took %ld.%03ld seconds\n",
600 summary->len, diff / 1000, diff % 1000);
605 * camel_folder_thread_messages_new:
607 * @uids: The subset of uid's to thread. If NULL. then thread all
609 * @thread_subject: thread based on subject also
611 * Thread a (subset) of the messages in a folder. And sort the result
614 * If @thread_subject is %TRUE, messages with
615 * related subjects will also be threaded. The default behaviour is to
616 * only thread based on message-id.
618 * This function is probably to be removed soon.
620 * Returns: A CamelFolderThread contianing a tree of CamelFolderThreadNode's
621 * which represent the threaded structure of the messages.
624 camel_folder_thread_messages_new (CamelFolder *folder,
626 gboolean thread_subject)
628 CamelFolderThread *thread;
630 GPtrArray *fsummary = NULL;
633 thread = g_malloc (sizeof (*thread));
634 thread->refcount = 1;
635 thread->subject = thread_subject;
637 thread->node_chunks = camel_memchunk_new (32, sizeof (CamelFolderThreadNode));
638 thread->folder = g_object_ref (folder);
640 camel_folder_summary_prepare_fetch_all (folder->summary, NULL);
641 thread->summary = summary = g_ptr_array_new ();
643 /* prefer given order from the summary order */
645 fsummary = camel_folder_summary_get_array (folder->summary);
649 for (i = 0; i < uids->len; i++) {
650 CamelMessageInfo *info;
651 gchar *uid = uids->pdata[i];
653 info = camel_folder_get_message_info (folder, uid);
655 g_ptr_array_add (summary, info);
656 /* FIXME: Check if the info is leaking */
660 camel_folder_summary_free_array (fsummary);
662 thread_summary (thread, summary);
667 /* add any still there, in the existing order */
669 add_present_rec (CamelFolderThread *thread,
672 CamelFolderThreadNode *node)
675 const gchar *uid = camel_message_info_uid (node->message);
677 if (g_hash_table_lookup (have, (gchar *) uid)) {
678 g_hash_table_remove (have, (gchar *) camel_message_info_uid (node->message));
679 g_ptr_array_add (summary, (gpointer) node->message);
681 camel_folder_free_message_info (thread->folder, (CamelMessageInfo *) node->message);
685 add_present_rec (thread, have, summary, node->child);
691 camel_folder_thread_messages_apply (CamelFolderThread *thread,
697 CamelMessageInfo *info;
699 all = g_ptr_array_new ();
700 table = g_hash_table_new (g_str_hash, g_str_equal);
701 for (i = 0; i < uids->len; i++)
702 g_hash_table_insert (table, uids->pdata[i], uids->pdata[i]);
704 add_present_rec (thread, table, all, thread->tree);
706 /* add any new ones, in supplied order */
707 for (i = 0; i < uids->len; i++)
708 if (g_hash_table_lookup (table, uids->pdata[i]) && (info = camel_folder_get_message_info (thread->folder, uids->pdata[i])))
709 g_ptr_array_add (all, info);
711 g_hash_table_destroy (table);
714 camel_memchunk_destroy (thread->node_chunks);
715 thread->node_chunks = camel_memchunk_new (32, sizeof (CamelFolderThreadNode));
716 thread_summary (thread, all);
718 g_ptr_array_free (thread->summary, TRUE);
719 thread->summary = all;
723 camel_folder_thread_messages_ref (CamelFolderThread *thread)
729 * camel_folder_thread_messages_unref:
732 * Free all memory associated with the thread descriptor @thread.
735 camel_folder_thread_messages_unref (CamelFolderThread *thread)
737 if (thread->refcount > 1) {
742 if (thread->folder) {
745 for (i = 0; i < thread->summary->len; i++)
746 camel_folder_free_message_info (thread->folder, thread->summary->pdata[i]);
747 g_ptr_array_free (thread->summary, TRUE);
748 g_object_unref (thread->folder);
750 camel_memchunk_destroy (thread->node_chunks);
756 * camel_folder_thread_messages_new_summary:
757 * @summary: Array of CamelMessageInfo's to thread.
759 * Thread a list of MessageInfo's. The summary must remain valid for the
760 * life of the CamelFolderThread created by this function, and it is upto the
761 * caller to ensure this.
763 * Returns: A CamelFolderThread contianing a tree of CamelFolderThreadNode's
764 * which represent the threaded structure of the messages.
767 camel_folder_thread_messages_new_summary (GPtrArray *summary)
769 CamelFolderThread *thread;
772 struct timeval start, end;
775 gettimeofday (&start, NULL);
778 thread = g_malloc (sizeof (*thread));
779 thread->refcount = 1;
781 thread->node_chunks = camel_memchunk_new (32, sizeof (CamelFolderThreadNode));
782 thread->folder = NULL;
783 thread->summary = NULL;
785 thread_summary (thread, summary);
790 /* scan the list in depth-first fashion */
792 build_summary_rec (GHashTable *have,
794 CamelFolderThreadNode *node)
798 g_hash_table_insert (have, (gchar *) camel_message_info_uid (node->message), node->message);
799 g_ptr_array_add (summary, node);
801 build_summary_rec (have, summary, node->child);
807 camel_folder_thread_messages_add (CamelFolderThread *thread,
814 /* Instead of working out all the complex in's and out's of
815 * trying to do an incremental summary generation, just redo the whole
816 * thing with the summary in the current order - so it comes out
817 * in the same order */
819 all = g_ptr_array_new ();
820 table = g_hash_table_new (g_str_hash, g_str_equal);
821 build_summary_rec (table, all, thread->tree);
822 for (i = 0; i < summary->len; i++) {
823 CamelMessageInfo *info = summary->pdata[i];
825 /* check its not already there, we dont want duplicates */
826 if (g_hash_table_lookup (table, camel_message_info_uid (info)) == NULL)
827 g_ptr_array_add (all, info);
829 g_hash_table_destroy (table);
831 /* reset the tree, and rebuild fully */
833 camel_memchunk_empty (thread->node_chunks);
834 thread_summary (thread, all);
838 remove_uid_node_rec (CamelFolderThread *thread,
840 CamelFolderThreadNode **list,
841 CamelFolderThreadNode *parent)
843 CamelFolderThreadNode *prev = NULL;
844 CamelFolderThreadNode *node, *next, *child, *rest;
846 node = (CamelFolderThreadNode *) list;
851 remove_uid_node_rec (thread, table, &next->child, next);
853 /* do we have a node to remove? */
854 if (next->message && g_hash_table_lookup (table, (gchar *) camel_message_info_uid (node->message))) {
873 camel_memchunk_free (thread->node_chunks, next);
877 child->parent = parent;
889 node->next = next->next;
890 camel_memchunk_free (thread->node_chunks, next);
901 camel_folder_thread_messages_remove (CamelFolderThread *thread,
907 table = g_hash_table_new (g_str_hash, g_str_equal);
908 for (i = 0; i < uids->len; i++)
909 g_hash_table_insert (table, uids->pdata[i], uids->pdata[i]);
911 remove_uid_node_rec (thread, table, &thread->tree, NULL);
912 g_hash_table_destroy (table);