camel/camel-folder-thread.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
   2 /*
   3  *  Copyright (C) 1999-2008 Novell, Inc. (www.novell.com)
   4  *
   5  *  Authors: Michael Zucchi <notzed@ximian.com>
   6  *
   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.
  10  *
  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.
  15  *
  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.
  20  */
  21
  22 /* TODO: This could probably be made a camel object, but it isn't really required */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include <config.h>
  26 #endif
  27
  28 #include <ctype.h>
  29 #include <errno.h>
  30 #include <fcntl.h>
  31 #include <string.h>
  32 #include <unistd.h>
  33 #include <sys/stat.h>
  34 #include <sys/types.h>
  35
  36 #include "camel-folder-thread.h"
  37
  38 #define d(x)
  39 #define m(x)
  40
  41 /*#define TIMEIT*/
  42
  43 #ifdef TIMEIT
  44 #include <sys/time.h>
  45 #endif
  46
  47 static void
  48 container_add_child (CamelFolderThreadNode *node,
  49                      CamelFolderThreadNode *child)
  50 {
  51         d (printf ("\nAdding child %p to parent %p \n", child, node));
  52         child->next = node->child;
  53         node->child = child;
  54         child->parent = node;
  55 }
  56
  57 static void
  58 container_parent_child (CamelFolderThreadNode *parent,
  59                         CamelFolderThreadNode *child)
  60 {
  61         CamelFolderThreadNode *c, *node;
  62
  63         /* are we already the right parent? */
  64         if (child->parent == parent)
  65                 return;
  66
  67         /* would this create a loop? */
  68         node = parent->parent;
  69         while (node) {
  70                 if (node == child)
  71                         return;
  72                 node = node->parent;
  73         }
  74
  75         /* are we unparented? */
  76         if (child->parent == NULL) {
  77                 container_add_child (parent, child);
  78                 return;
  79         }
  80
  81         /* else remove child from its existing parent, and reparent */
  82         node = child->parent;
  83         c = (CamelFolderThreadNode *) &node->child;
  84         d (printf ("scanning children:\n"));
  85         while (c->next) {
  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;
  90                         child->parent = NULL;
  91                         container_add_child (parent, child);
  92                         return;
  93                 }
  94                 c = c->next;
  95         }
  96
  97         printf ("DAMN, we shouldn't  be here!\n");
  98 }
  99
 100 static void
 101 prune_empty (CamelFolderThread *thread,
 102              CamelFolderThreadNode **cp)
 103 {
 104         CamelFolderThreadNode *child, *next, *c, *lastc;
 105
 106         /* yes, this is intentional */
 107         lastc = (CamelFolderThreadNode *) cp;
 108         while (lastc->next) {
 109                 c = lastc->next;
 110                 prune_empty (thread, &c->child);
 111
 112                 d (printf (
 113                         "checking message %p %p (%08x%08x)\n", c,
 114                         c->message,
 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);
 123                                 continue;
 124                         }
 125                         if (c->parent || c->child->next == NULL) {
 126                                 d (printf ("promoting child\n"));
 127                                 lastc->next = c->next; /* remove us */
 128                                 child = c->child;
 129                                 while (child) {
 130                                         next = child->next;
 131
 132                                         child->parent = c->parent;
 133                                         child->next = lastc->next;
 134                                         lastc->next = child;
 135
 136                                         child = next;
 137                                 }
 138                                 continue;
 139                         }
 140                 }
 141                 lastc = c;
 142         }
 143 }
 144
 145 static void
 146 hashloop (gpointer key,
 147           gpointer value,
 148           gpointer data)
 149 {
 150         CamelFolderThreadNode *c = value;
 151         CamelFolderThreadNode *tail = data;
 152
 153         if (c->parent == NULL) {
 154                 c->next = tail->next;
 155                 tail->next = c;
 156         }
 157 }
 158
 159 static gchar *
 160 get_root_subject (CamelFolderThreadNode *c)
 161 {
 162         gchar *s, *p;
 163         CamelFolderThreadNode *scan;
 164
 165         s = NULL;
 166         c->re = FALSE;
 167         if (c->message)
 168                 s = (gchar *) camel_message_info_subject (c->message);
 169         else {
 170                 /* one of the children will always have a message */
 171                 scan = c->child;
 172                 while (scan) {
 173                         if (scan->message) {
 174                                 s = (gchar *) camel_message_info_subject (scan->message);
 175                                 break;
 176                         }
 177                         scan = scan->next;
 178                 }
 179         }
 180         if (s != NULL) {
 181                 while (*s) {
 182                         while (isspace (*s))
 183                                 s++;
 184                         if (s[0] == 0)
 185                                 break;
 186                         if ((s[0] == 'r' || s[0]=='R')
 187                             && (s[1] == 'e' || s[1]=='E')) {
 188                                 p = s + 2;
 189                                 while (isdigit (*p) || (ispunct (*p) && (*p != ':')))
 190                                         p++;
 191                                 if (*p == ':') {
 192                                         c->re = TRUE;
 193                                         s = p + 1;
 194                                 } else
 195                                         break;
 196                         } else
 197                                 break;
 198                 }
 199                 if (*s)
 200                         return s;
 201         }
 202         return NULL;
 203 }
 204
 205 /* this can be pretty slow, but not used often */
 206 /* clast cannot be null */
 207 static void
 208 remove_node (CamelFolderThreadNode **list,
 209              CamelFolderThreadNode *node,
 210              CamelFolderThreadNode **clast)
 211 {
 212         CamelFolderThreadNode *c;
 213
 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 */
 217         if (node->parent) {
 218                 c = (CamelFolderThreadNode *) &node->parent->child;
 219         } else {
 220                 c = (CamelFolderThreadNode *) list;
 221         }
 222         while (c->next) {
 223                 if (c->next == node) {
 224                         if (*clast == c->next)
 225                                 *clast = c;
 226                         c->next = c->next->next;
 227                         return;
 228                 }
 229                 c = c->next;
 230         }
 231
 232         printf ("ERROR: removing node %p failed\n", (gpointer) node);
 233 }
 234
 235 static void
 236 group_root_set (CamelFolderThread *thread,
 237                 CamelFolderThreadNode **cp)
 238 {
 239         GHashTable *subject_table = g_hash_table_new (g_str_hash, g_str_equal);
 240         CamelFolderThreadNode *c, *clast, *scan, *container;
 241
 242         /* gather subject lines */
 243         d (printf ("gathering subject lines\n"));
 244         clast = (CamelFolderThreadNode *) cp;
 245         c = clast->next;
 246         while (c) {
 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);
 254                         }
 255                 }
 256                 c = c->next;
 257         }
 258
 259         /* merge common subjects? */
 260         clast = (CamelFolderThreadNode *) cp;
 261         while (clast->next) {
 262                 c = clast->next;
 263                 d (printf ("checking %p %s\n", c, c->root_subject));
 264                 if (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;
 272                                 while (scan->next)
 273                                         scan = scan->next;
 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);
 278                                 continue;
 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);
 287                                 continue;
 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);
 292                                 continue;
 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);
 297                         } else {
 298                                 d (printf ("subjects are common %p and %p\n", c, container));
 299
 300                                 /* build a phantom node */
 301                                 remove_node (cp, container, &clast);
 302                                 remove_node (cp, c, &clast);
 303
 304                                 scan = camel_memchunk_alloc0 (thread->node_chunks);
 305
 306                                 scan->root_subject = c->root_subject;
 307                                 scan->re = c->re && container->re;
 308                                 scan->next = c->next;
 309                                 clast->next = scan;
 310                                 container_add_child (scan, c);
 311                                 container_add_child (scan, container);
 312                                 clast = scan;
 313                                 g_hash_table_insert (subject_table, scan->root_subject, scan);
 314                                 continue;
 315                         }
 316                 }
 317                 clast = c;
 318         }
 319         g_hash_table_destroy (subject_table);
 320 }
 321
 322 struct _tree_info {
 323         GHashTable *visited;
 324 };
 325
 326 static gint
 327 dump_tree_rec (struct _tree_info *info,
 328                CamelFolderThreadNode *c,
 329                gint depth)
 330 {
 331         gchar *p;
 332         gint count = 0;
 333
 334         p = alloca (depth * 2 + 1);
 335         memset (p, ' ', depth * 2);
 336         p[depth * 2] = 0;
 337
 338         while (c) {
 339                 if (g_hash_table_lookup (info->visited, c)) {
 340                         printf ("WARNING: NODE REVISITED: %p\n", (gpointer) c);
 341                 } else {
 342                         g_hash_table_insert (info->visited, c, c);
 343                 }
 344                 if (c->message) {
 345                         printf (
 346                                 "%s %p Subject: %s <%08x%08x>\n",
 347                                 p, (gpointer) c,
 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);
 351                         count += 1;
 352                 } else {
 353                         printf ("%s %p <empty>\n", p, (gpointer) c);
 354                 }
 355                 if (c->child)
 356                         count += dump_tree_rec (info, c->child, depth + 1);
 357                 c = c->next;
 358         }
 359         return count;
 360 }
 361
 362 gint
 363 camel_folder_threaded_messages_dump (CamelFolderThreadNode *c)
 364 {
 365         gint count;
 366         struct _tree_info info;
 367
 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);
 371         return count;
 372 }
 373
 374 static gint
 375 sort_node (gconstpointer a,
 376            gconstpointer b)
 377 {
 378         const CamelFolderThreadNode *a1 = ((CamelFolderThreadNode **) a)[0];
 379         const CamelFolderThreadNode *b1 = ((CamelFolderThreadNode **) b)[0];
 380
 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)
 385                 a1 = a1->child;
 386         if (b1->message == NULL)
 387                 b1 = b1->child;
 388         if (a1->order == b1->order)
 389                 return 0;
 390         if (a1->order < b1->order)
 391                 return -1;
 392         else
 393                 return 1;
 394 }
 395
 396 static void
 397 sort_thread (CamelFolderThreadNode **cp)
 398 {
 399         CamelFolderThreadNode *c, *head, **carray;
 400         gint size = 0;
 401
 402         c = *cp;
 403         while (c) {
 404                 /* sort the children while we're at it */
 405                 if (c->child)
 406                         sort_thread (&c->child);
 407                 size++;
 408                 c = c->next;
 409         }
 410         if (size < 2)
 411                 return;
 412         carray = alloca (size * sizeof (CamelFolderThreadNode *));
 413         c = *cp;
 414         size = 0;
 415         while (c) {
 416                 carray[size] = c;
 417                 c = c->next;
 418                 size++;
 419         }
 420         qsort (carray, size, sizeof (CamelFolderThreadNode *), sort_node);
 421         size--;
 422         head = carray[size];
 423         head->next = NULL;
 424         size--;
 425         do {
 426                 c = carray[size];
 427                 c->next = head;
 428                 head = c;
 429                 size--;
 430         } while (size >= 0);
 431         *cp = head;
 432 }
 433
 434 static guint
 435 id_hash (gpointer key)
 436 {
 437         CamelSummaryMessageID *id = (CamelSummaryMessageID *) key;
 438
 439         return id->id.part.lo;
 440 }
 441
 442 static gint
 443 id_equal (gpointer a,
 444           gpointer b)
 445 {
 446         return ((CamelSummaryMessageID *) a)->id.id == ((CamelSummaryMessageID *) b)->id.id;
 447 }
 448
 449 /* perform actual threading */
 450 static void
 451 thread_summary (CamelFolderThread *thread,
 452                 GPtrArray *summary)
 453 {
 454         GHashTable *id_table, *no_id_table;
 455         gint i;
 456         CamelFolderThreadNode *c, *child, *head;
 457 #ifdef TIMEIT
 458         struct timeval start, end;
 459         gulong diff;
 460
 461         gettimeofday (&start, NULL);
 462 #endif
 463
 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);
 470
 471                 if (mid != NULL && mid->id.id) {
 472                         c = g_hash_table_lookup (id_table, mid);
 473                         /* check for duplicate messages */
 474                         if (c && c->order) {
 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);
 480                         } else if (!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);
 484                         }
 485                 } else {
 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);
 489                 }
 490
 491                 c->message = mi;
 492                 c->order = i + 1;
 493                 child = c;
 494                 if (references) {
 495                         gint j;
 496
 497                         d (printf ("%s (%s) references:\n", G_STRLOC, G_STRFUNC); )
 498                         for (j = 0; j < references->size; j++) {
 499                                 gboolean found = FALSE;
 500
 501                                 /* should never be empty, but just incase */
 502                                 if (references->references[j].id.id == 0)
 503                                         continue;
 504
 505                                 c = g_hash_table_lookup (id_table, &references->references[j]);
 506                                 if (c == NULL) {
 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);
 510                                 } else
 511                                         found = TRUE;
 512                                 if (c != child) {
 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. */
 517                                         if (found)
 518                                                 break;
 519                                 }
 520                                 child = c;
 521                         }
 522                 }
 523         }
 524
 525         d (printf ("\n\n"));
 526         /* build a list of root messages (no parent) */
 527         head = NULL;
 528         g_hash_table_foreach (id_table, hashloop, &head);
 529         g_hash_table_foreach (no_id_table, hashloop, &head);
 530
 531         g_hash_table_destroy (id_table);
 532         g_hash_table_destroy (no_id_table);
 533
 534         /* remove empty parent nodes */
 535         prune_empty (thread, &head);
 536
 537         /* find any siblings which missed out - but only if we are allowing threading by subject */
 538         if (thread->subject)
 539                 group_root_set (thread, &head);
 540
 541 #if 0
 542         printf ("finished\n");
 543         i = camel_folder_threaded_messages_dump (head);
 544         printf ("%d count, %d items in tree\n", summary->len, i);
 545 #endif
 546
 547         sort_thread (&head);
 548
 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;
 553
 554                 child = c->next;
 555                 if (child->message == NULL) {
 556                         newtop = child->child;
 557                         newtop->parent = NULL;
 558                         /* unlink pseudo node */
 559                         c->next = newtop;
 560
 561                         /* link its siblings onto the end of its children, fix all parent pointers */
 562                         scan = (CamelFolderThreadNode *) &newtop->child;
 563                         while (scan->next) {
 564                                 scan = scan->next;
 565                         }
 566                         scan->next = newtop->next;
 567                         while (scan->next) {
 568                                 scan = scan->next;
 569                                 scan->parent = newtop;
 570                         }
 571
 572                         /* and link the now 'real' node into the list */
 573                         newtop->next = child->next;
 574                         c = newtop;
 575                         m (memset (child, 0xde, sizeof (*child)));
 576                         camel_memchunk_free (thread->node_chunks, child);
 577                 } else {
 578                         c = child;
 579                 }
 580         }
 581
 582         /* this is only debug assertion stuff */
 583         c = (CamelFolderThreadNode *) &head;
 584         while (c->next) {
 585                 c = c->next;
 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);
 590         }
 591
 592         thread->tree = head;
 593
 594 #ifdef TIMEIT
 595         gettimeofday (&end, NULL);
 596         diff = end.tv_sec * 1000 + end.tv_usec / 1000;
 597         diff -= start.tv_sec * 1000 + start.tv_usec / 1000;
 598         printf (
 599                 "Message threading %d messages took %ld.%03ld seconds\n",
 600                 summary->len, diff / 1000, diff % 1000);
 601 #endif
 602 }
 603
 604 /**
 605  * camel_folder_thread_messages_new:
 606  * @folder:
 607  * @uids: The subset of uid's to thread.  If NULL. then thread all
 608  * uid's in @folder.
 609  * @thread_subject: thread based on subject also
 610  *
 611  * Thread a (subset) of the messages in a folder.  And sort the result
 612  * in summary order.
 613  *
 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.
 617  *
 618  * This function is probably to be removed soon.
 619  *
 620  * Returns: A CamelFolderThread contianing a tree of CamelFolderThreadNode's
 621  * which represent the threaded structure of the messages.
 622  **/
 623 CamelFolderThread *
 624 camel_folder_thread_messages_new (CamelFolder *folder,
 625                                   GPtrArray *uids,
 626                                   gboolean thread_subject)
 627 {
 628         CamelFolderThread *thread;
 629         GPtrArray *summary;
 630         GPtrArray *fsummary = NULL;
 631         gint i;
 632
 633         thread = g_malloc (sizeof (*thread));
 634         thread->refcount = 1;
 635         thread->subject = thread_subject;
 636         thread->tree = NULL;
 637         thread->node_chunks = camel_memchunk_new (32, sizeof (CamelFolderThreadNode));
 638         thread->folder = g_object_ref (folder);
 639
 640         camel_folder_summary_prepare_fetch_all (folder->summary, NULL);
 641         thread->summary = summary = g_ptr_array_new ();
 642
 643         /* prefer given order from the summary order */
 644         if (!uids) {
 645                 fsummary = camel_folder_summary_get_array (folder->summary);
 646                 uids = fsummary;
 647         }
 648
 649         for (i = 0; i < uids->len; i++) {
 650                 CamelMessageInfo *info;
 651                 gchar *uid = uids->pdata[i];
 652
 653                 info = camel_folder_get_message_info (folder, uid);
 654                 if (info)
 655                         g_ptr_array_add (summary, info);
 656                 /* FIXME: Check if the info is leaking */
 657         }
 658
 659         if (fsummary)
 660                 camel_folder_summary_free_array (fsummary);
 661
 662         thread_summary (thread, summary);
 663
 664         return thread;
 665 }
 666
 667 /* add any still there, in the existing order */
 668 static void
 669 add_present_rec (CamelFolderThread *thread,
 670                  GHashTable *have,
 671                  GPtrArray *summary,
 672                  CamelFolderThreadNode *node)
 673 {
 674         while (node) {
 675                 const gchar *uid = camel_message_info_uid (node->message);
 676
 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);
 680                 } else {
 681                         camel_folder_free_message_info (thread->folder, (CamelMessageInfo *) node->message);
 682                 }
 683
 684                 if (node->child)
 685                         add_present_rec (thread, have, summary, node->child);
 686                 node = node->next;
 687         }
 688 }
 689
 690 void
 691 camel_folder_thread_messages_apply (CamelFolderThread *thread,
 692                                     GPtrArray *uids)
 693 {
 694         gint i;
 695         GPtrArray *all;
 696         GHashTable *table;
 697         CamelMessageInfo *info;
 698
 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]);
 703
 704         add_present_rec (thread, table, all, thread->tree);
 705
 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);
 710
 711         g_hash_table_destroy (table);
 712
 713         thread->tree = NULL;
 714         camel_memchunk_destroy (thread->node_chunks);
 715         thread->node_chunks = camel_memchunk_new (32, sizeof (CamelFolderThreadNode));
 716         thread_summary (thread, all);
 717
 718         g_ptr_array_free (thread->summary, TRUE);
 719         thread->summary = all;
 720 }
 721
 722 void
 723 camel_folder_thread_messages_ref (CamelFolderThread *thread)
 724 {
 725         thread->refcount++;
 726 }
 727
 728 /**
 729  * camel_folder_thread_messages_unref:
 730  * @thread:
 731  *
 732  * Free all memory associated with the thread descriptor @thread.
 733  **/
 734 void
 735 camel_folder_thread_messages_unref (CamelFolderThread *thread)
 736 {
 737         if (thread->refcount > 1) {
 738                 thread->refcount--;
 739                 return;
 740         }
 741
 742         if (thread->folder) {
 743                 gint i;
 744
 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);
 749         }
 750         camel_memchunk_destroy (thread->node_chunks);
 751         g_free (thread);
 752 }
 753
 754 #if 0
 755 /**
 756  * camel_folder_thread_messages_new_summary:
 757  * @summary: Array of CamelMessageInfo's to thread.
 758  *
 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.
 762  *
 763  * Returns: A CamelFolderThread contianing a tree of CamelFolderThreadNode's
 764  * which represent the threaded structure of the messages.
 765  **/
 766 CamelFolderThread *
 767 camel_folder_thread_messages_new_summary (GPtrArray *summary)
 768 {
 769         CamelFolderThread *thread;
 770
 771 #ifdef TIMEIT
 772         struct timeval start, end;
 773         gulong diff;
 774
 775         gettimeofday (&start, NULL);
 776 #endif
 777
 778         thread = g_malloc (sizeof (*thread));
 779         thread->refcount = 1;
 780         thread->tree = NULL;
 781         thread->node_chunks = camel_memchunk_new (32, sizeof (CamelFolderThreadNode));
 782         thread->folder = NULL;
 783         thread->summary = NULL;
 784
 785         thread_summary (thread, summary);
 786
 787         return thread;
 788 }
 789
 790 /* scan the list in depth-first fashion */
 791 static void
 792 build_summary_rec (GHashTable *have,
 793                    GPtrArray *summary,
 794                    CamelFolderThreadNode *node)
 795 {
 796         while (node) {
 797                 if (node->message)
 798                         g_hash_table_insert (have, (gchar *) camel_message_info_uid (node->message), node->message);
 799                 g_ptr_array_add (summary, node);
 800                 if (node->child)
 801                         build_summary_rec (have, summary, node->child);
 802                 node = node->next;
 803         }
 804 }
 805
 806 void
 807 camel_folder_thread_messages_add (CamelFolderThread *thread,
 808                                   GPtrArray *summary)
 809 {
 810         GPtrArray *all;
 811         gint i;
 812         GHashTable *table;
 813
 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 */
 818
 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];
 824
 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);
 828         }
 829         g_hash_table_destroy (table);
 830
 831         /* reset the tree, and rebuild fully */
 832         thread->tree = NULL;
 833         camel_memchunk_empty (thread->node_chunks);
 834         thread_summary (thread, all);
 835 }
 836
 837 static void
 838 remove_uid_node_rec (CamelFolderThread *thread,
 839                      GHashTable *table,
 840                      CamelFolderThreadNode **list,
 841                      CamelFolderThreadNode *parent)
 842 {
 843         CamelFolderThreadNode *prev = NULL;
 844         CamelFolderThreadNode *node, *next, *child, *rest;
 845
 846         node = (CamelFolderThreadNode *) list;
 847         next = node->next;
 848         while (next) {
 849
 850                 if (next->child)
 851                         remove_uid_node_rec (thread, table, &next->child, next);
 852
 853                 /* do we have a node to remove? */
 854                 if (next->message && g_hash_table_lookup (table, (gchar *) camel_message_info_uid (node->message))) {
 855                         child = next->child;
 856                         if (child) {
 857                                 /*
 858                                  * node
 859                                  * next
 860                                  * child
 861                                  * lchild
 862                                  * rest
 863                                  *
 864                                  * becomes:
 865                                  * node
 866                                  * child
 867                                  * lchild
 868                                  * rest
 869                                  */
 870
 871                                 rest = next->next;
 872                                 node->next = child;
 873                                 camel_memchunk_free (thread->node_chunks, next);
 874                                 next = child;
 875                                 do {
 876                                         lchild = child;
 877                                         child->parent = parent;
 878                                         child = child->next;
 879                                 } while (child);
 880                                 lchild->next = rest;
 881                         } else {
 882                                 /*
 883                                  * node
 884                                  * next
 885                                  * rest
 886                                  * becomes:
 887                                  * node
 888                                  * rest */
 889                                 node->next = next->next;
 890                                 camel_memchunk_free (thread->node_chunks, next);
 891                                 next = node->next;
 892                         }
 893                 } else {
 894                         node = next;
 895                         next = node->next;
 896                 }
 897         }
 898 }
 899
 900 void
 901 camel_folder_thread_messages_remove (CamelFolderThread *thread,
 902                                      GPtrArray *uids)
 903 {
 904         GHashTable *table;
 905         gint i;
 906
 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]);
 910
 911         remove_uid_node_rec (thread, table, &thread->tree, NULL);
 912         g_hash_table_destroy (table);
 913 }
 914
 915 #endif