aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorNot Zed <NotZed@HelixCode.com>2000-07-06 13:03:57 +0800
committerMichael Zucci <zucchi@src.gnome.org>2000-07-06 13:03:57 +0800
commitb226c0a68fb89c074b5c5655e9469d692f71c988 (patch)
tree2025df6152c8c7ec0db7a9de0338112fee9022f5
parent04f148f617112009091abd18b16463033dd322d0 (diff)
downloadgsoc2013-evolution-b226c0a68fb89c074b5c5655e9469d692f71c988.tar
gsoc2013-evolution-b226c0a68fb89c074b5c5655e9469d692f71c988.tar.gz
gsoc2013-evolution-b226c0a68fb89c074b5c5655e9469d692f71c988.tar.bz2
gsoc2013-evolution-b226c0a68fb89c074b5c5655e9469d692f71c988.tar.lz
gsoc2013-evolution-b226c0a68fb89c074b5c5655e9469d692f71c988.tar.xz
gsoc2013-evolution-b226c0a68fb89c074b5c5655e9469d692f71c988.tar.zst
gsoc2013-evolution-b226c0a68fb89c074b5c5655e9469d692f71c988.zip
Code for message threading.
2000-07-06 Not Zed <NotZed@HelixCode.com> * message-thread.[ch]: Code for message threading. svn path=/trunk/; revision=3916
-rw-r--r--mail/ChangeLog4
-rw-r--r--mail/Makefile.am2
-rw-r--r--mail/message-thread.c506
-rw-r--r--mail/message-thread.h20
4 files changed, 532 insertions, 0 deletions
diff --git a/mail/ChangeLog b/mail/ChangeLog
index dee175d84d..8169830a2b 100644
--- a/mail/ChangeLog
+++ b/mail/ChangeLog
@@ -1,3 +1,7 @@
+2000-07-06 Not Zed <NotZed@HelixCode.com>
+
+ * message-thread.[ch]: Code for message threading.
+
2000-07-05 Dan Winship <danw@helixcode.com>
* mail-identify.c (mail_identify_mime_part): Oops. My gnome-vfs
diff --git a/mail/Makefile.am b/mail/Makefile.am
index dce2a11a03..e92223bb5b 100644
--- a/mail/Makefile.am
+++ b/mail/Makefile.am
@@ -51,6 +51,8 @@ evolution_mail_SOURCES = \
main.c \
message-list.c \
message-list.h \
+ message-thread.c \
+ message-thread.h \
session.c \
mail.h
diff --git a/mail/message-thread.c b/mail/message-thread.c
new file mode 100644
index 0000000000..153cc75015
--- /dev/null
+++ b/mail/message-thread.c
@@ -0,0 +1,506 @@
+/* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
+/*
+ * Copyright (C) 2000 Helix Code Inc.
+ *
+ * Authors: Michael Zucchi <notzed@helixcode.com>
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * This program 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
+ * USA
+ */
+
+#include "camel/camel.h"
+#include <sys/types.h>
+#include <unistd.h>
+#include <errno.h>
+#include <string.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <glib.h>
+
+#include "message-thread.h"
+
+#define d(x)
+
+int dump_tree(struct _container *c, int depth);
+
+static void
+container_add_child(struct _container *node, struct _container *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_unparent_child(struct _container *child)
+{
+ struct _container *c, *p = NULL, *last, *node;
+
+ /* are we unparented? */
+ if (child->parent == NULL) {
+ return;
+ }
+
+ /* else remove child from its existing parent, and reparent */
+ node = child->parent;
+ c = (struct _container *)&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;
+ return;
+ }
+ c = c->next;
+ }
+
+ printf("DAMN, we shouldn't be here!\n");
+}
+
+static void
+container_parent_child(struct _container *parent, struct _container *child)
+{
+ struct _container *c, *p = NULL, *last, *node;
+
+ /* are we already the right parent? */
+ if (child->parent == parent)
+ return;
+
+ /* 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 = (struct _container *)&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(struct _container **cp)
+{
+ struct _container *child, *next, *nextc, *c, *lastc;
+
+ /* yes, this is intentional */
+ lastc = (struct _container *)cp;
+ while (lastc->next) {
+ c = lastc->next;
+
+ d(printf("checking message %p %p (%s)\n", c,
+ c->message, c->message?c->message->message_id:"<empty>"));
+ if (c->message == NULL) {
+ if (c->child == NULL) {
+ d(printf("removing empty node\n"));
+ lastc->next = c->next;
+ continue;
+ }
+ if (c->parent || c->child->next==0) {
+ 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;
+ }
+ }
+ prune_empty(&c->child);
+ lastc = c;
+ }
+}
+
+static void
+hashloop(void *key, void *value, void *data)
+{
+ struct _container *c = value;
+ char *keystr = key;
+ struct _container *tail = data;
+
+ if (c->parent == NULL) {
+ c->next = tail->next;
+ tail->next = c;
+ }
+}
+
+static char *
+get_root_subject(struct _container *c, int *re)
+{
+ char *s, *p;
+ struct _container *scan;
+
+ s = NULL;
+ *re = FALSE;
+ if (c->message)
+ s = c->message->subject;
+ else {
+ /* one of the children will always have a message */
+ scan = c->child;
+ while (scan) {
+ if (scan->message) {
+ s = scan->message->subject;
+ break;
+ }
+ scan = scan->next;
+ }
+ }
+ if (s != NULL) {
+ while (*s) {
+ char cc;
+ 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 (ispunct(*p) || isdigit(*p) && *p != ':')
+ p++;
+ if (*p==':') {
+ *re = TRUE;
+ s = p+1;
+ } else
+ break;
+ } else
+ break;
+ }
+ if (*s)
+ return s;
+ }
+ return NULL;
+}
+
+/* this is pretty slow, but not used often */
+static void
+remove_node(struct _container **list, struct _container *node)
+{
+ struct _container *c;
+
+ /* this is intentional, even if it looks funny */
+ c = (struct _container *)list;
+ while (c->next) {
+ if (c->next == node) {
+ c->next = c->next->next;
+ break;
+ }
+ c = c->next;
+ }
+}
+
+static void
+group_root_set(struct _container **cp)
+{
+ GHashTable *subject_table = g_hash_table_new(g_str_hash, g_str_equal);
+ struct _container *c, *clast, *scan, *container;
+ char *s;
+ int re;
+
+ /* gather subject lines */
+ d(printf("gathering subject lines\n"));
+ clast = (struct _container *)cp;
+ c = clast->next;
+ while (c) {
+ c->root_subject = get_root_subject(c, &c->re);
+ 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 = (struct _container *)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 = (struct _container *)&container->child;
+ while (scan->next)
+ scan = scan->next;
+ scan->next = c->child;
+ clast->next = c->next;
+ continue;
+ } if (c->message == NULL && container->message != NULL) {
+ d(printf("container is non-empty parent\n"));
+ remove_node(cp, container);
+ 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);
+ container_add_child(c, container);
+ } else {
+ d(printf("subjects are common %p and %p\n", c, container));
+
+ remove_node(cp, container);
+
+ scan = g_malloc0(sizeof(*scan));
+ 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);
+}
+
+int
+dump_tree(struct _container *c, int depth)
+{
+ char *p;
+ struct _container *child;
+ int count=0;
+
+ p = alloca(depth*2+1);
+ memset(p, ' ', depth*2);
+ p[depth*2] = 0;
+
+ while (c) {
+ if (c->message) {
+ printf("%s %p Subject: %s <%s>\n", p, c, c->message->subject, c->message->message_id);
+ count += 1;
+ } else {
+ printf("%s %p <empty>\n", p, c);
+ }
+ if (c->child)
+ count += dump_tree(c->child, depth+1);
+ c = c->next;
+ }
+ return count;
+}
+
+void thread_messages_free(struct _container *head)
+{
+ printf("FIXME: Free message thread structure\n");
+}
+
+struct _container *
+thread_messages(CamelMessageInfo **messages, int count)
+{
+ GHashTable *id_table;
+ int i, msgs;
+ struct _container *c, *p, *child, *head, *scan, *container;
+ struct _header_references *ref;
+
+ id_table = g_hash_table_new(g_str_hash, g_str_equal);
+ for (i=0;i<count;i++) {
+ CamelMessageInfo *mi;
+ mi = messages[i];
+ if (mi->message_id) {
+ d(printf("doing : %s\n", mi->message_id));
+ c = g_hash_table_lookup(id_table, mi->message_id);
+ if (c) {
+ c->message = mi;
+ } else {
+ c = g_malloc0(sizeof(*c));
+ c->message = mi;
+ g_hash_table_insert(id_table, mi->message_id, c);
+ }
+ container = c;
+ ref = mi->references;
+ p = NULL;
+ child = container;
+ head = NULL;
+ d(printf("referencfes: "));
+ while (ref) {
+ d(printf(" %s\n", ref->id));
+ if (ref->id == NULL) {
+ printf("FUCK!?\n");
+ ref = ref->next;
+ continue;
+ }
+ d(printf("looking up reference: %s\n", ref->id));
+ c = g_hash_table_lookup(id_table, ref->id);
+ if (c == NULL) {
+ d(printf("not found\n"));
+ c = g_malloc0(sizeof(*c));
+ g_hash_table_insert(id_table, ref->id, c);
+ }
+ if (c!=child) {
+ container_parent_child(c, child);
+ }
+ child = c;
+ if (head == NULL)
+ head = c;
+ ref = ref->next;
+ }
+ d(printf("\n"));
+ } else {
+ printf("No message id???\n");
+ /* ?? */
+ }
+ }
+
+ 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_destroy(id_table);
+
+ /* remove empty parent nodes */
+ prune_empty(&head);
+
+ /* find any siblings which missed out */
+ group_root_set(&head);
+
+ printf("finished\n");
+ i = dump_tree(head, 0);
+ printf("%d count, %d msgs initially, %d items in tree\n", count, msgs, i);
+
+ return head;
+}
+
+#ifdef STANDALONE
+
+static char *
+auth_callback(char *prompt, gboolean secret,
+ CamelService *service, char *item,
+ CamelException *ex)
+{
+ printf ("auth_callback called: %s\n", prompt);
+ return NULL;
+}
+
+int
+main (int argc, char**argv)
+{
+ CamelSession *session;
+ CamelException *ex;
+ CamelStore *store;
+ gchar *store_url = "mbox:///home/notzed/evolution/local/Inbox";
+ CamelFolder *folder;
+ CamelMimeMessage *message;
+ GList *uid_list;
+ GPtrArray *summary;
+
+ gtk_init (&argc, &argv);
+ camel_init ();
+ ex = camel_exception_new ();
+
+ session = camel_session_new (auth_callback);
+ store = camel_session_get_store (session, store_url, ex);
+ if (camel_exception_get_id (ex)) {
+ printf ("Exception caught in camel_session_get_store\n"
+ "Full description : %s\n", camel_exception_get_description (ex));
+ return -1;
+ }
+
+ folder = camel_store_get_folder (store, "mbox", TRUE, ex);
+ if (camel_exception_get_id (ex)) {
+ printf ("Exception caught in camel_store_get_folder\n"
+ "Full description : %s\n", camel_exception_get_description (ex));
+ return -1;
+ }
+
+#if 0
+ camel_folder_open (folder, FOLDER_OPEN_RW, ex);
+ if (camel_exception_get_id (ex)) {
+ printf ("Exception caught when trying to open the folder\n"
+ "Full description : %s\n", camel_exception_get_description (ex));
+ return -1;
+ }
+#endif
+
+ summary = camel_folder_get_summary(folder, ex);
+ thread_messages((CamelMessageInfo **)summary->pdata, summary->len);
+
+ return 0;
+}
+
+#endif
+
+/*
+
+ msgid: d
+ references: a b c
+
+ msgid: f
+ references: c d
+
+ msgid: e
+ references: c
+
+ a
+ \
+ b
+ \
+ c
+ \
+ d
+ |\
+ e f
+ */
+/*
+ lookup d
+ create new node d
+ child = d
+ loop on c b a
+ lookup node?
+ if no node, create node
+ add child to node
+ child = node
+ endloop
+
+ */
diff --git a/mail/message-thread.h b/mail/message-thread.h
new file mode 100644
index 0000000000..6c3eaad79a
--- /dev/null
+++ b/mail/message-thread.h
@@ -0,0 +1,20 @@
+#ifndef _MESSAGE_THREAD_H
+#define _MESSAGE_THREAD_H
+
+struct _container {
+ struct _container *next,
+ *parent,
+ *child;
+ CamelMessageInfo *message;
+ char *root_subject; /* cached root equivalent subject */
+ int re; /* re version of subject? */
+};
+
+struct _container *thread_messages(CamelMessageInfo **messages, int count);
+void thread_messages_free(struct _container *);
+
+/* for debug only */
+int dump_tree(struct _container *c, int depth);
+
+#endif /* !_MESSAGE_THREAD_H */
+