camel/camel-folder-thread.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: t; c-basic-offset: 8 -*- */
   2 /*
   3  *  Copyright (C) 2000 Ximian Inc.
   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 <glib.h>
  37
  38 #include <libedataserver/e-memory.h>
  39
  40 #include "camel-folder-thread.h"
  41
  42 #define d(x)
  43 #define m(x)
  44
  45 /*#define TIMEIT*/
  46
  47 #ifdef TIMEIT
  48 #include <sys/time.h>
  49 #include <unistd.h>
  50 #endif
  51
  52 static void
  53 container_add_child(CamelFolderThreadNode *node, CamelFolderThreadNode *child)
  54 {
  55         d(printf("\nAdding child %p to parent %p \n", child, node));
  56         child->next = node->child;
  57         node->child = child;
  58         child->parent = node;
  59 }
  60
  61 static void
  62 container_parent_child(CamelFolderThreadNode *parent, CamelFolderThreadNode *child)
  63 {
  64         CamelFolderThreadNode *c, *node;
  65
  66         /* are we already the right parent? */
  67         if (child->parent == parent)
  68                 return;
  69
  70         /* would this create a loop? */
  71         node = parent->parent;
  72         while (node) {
  73                 if (node == child)
  74                         return;
  75                 node = node->parent;
  76         }
  77
  78         /* are we unparented? */
  79         if (child->parent == NULL) {
  80                 container_add_child(parent, child);
  81                 return;
  82         }
  83
  84         /* else remove child from its existing parent, and reparent */
  85         node = child->parent;
  86         c = (CamelFolderThreadNode *)&node->child;
  87         d(printf("scanning children:\n"));
  88         while (c->next) {
  89                 d(printf(" %p\n", c));
  90                 if (c->next==child) {
  91                         d(printf("found node %p\n", child));
  92                         c->next = c->next->next;
  93                         child->parent = NULL;
  94                         container_add_child(parent, child);
  95                         return;
  96                 }
  97                 c = c->next;
  98         }
  99
 100         printf("DAMN, we shouldn't  be here!\n");
 101 }
 102
 103 static void
 104 prune_empty(CamelFolderThread *thread, CamelFolderThreadNode **cp)
 105 {
 106         CamelFolderThreadNode *child, *next, *c, *lastc;
 107
 108         /* yes, this is intentional */
 109         lastc = (CamelFolderThreadNode *)cp;
 110         while (lastc->next) {
 111                 c = lastc->next;
 112                 prune_empty(thread, &c->child);
 113
 114                 d(printf("checking message %p %p (%08x%08x)\n", c,
 115                          c->message, 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                                 e_memchunk_free(thread->node_chunks, c);
 123                                 continue;
 124                         }
 125                         if (c->parent || c->child->next==0) {
 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(void *key, void *value, void *data)
 147 {
 148         CamelFolderThreadNode *c = value;
 149         CamelFolderThreadNode *tail = data;
 150
 151         if (c->parent == NULL) {
 152                 c->next = tail->next;
 153                 tail->next = c;
 154         }
 155 }
 156
 157 static char *
 158 get_root_subject(CamelFolderThreadNode *c)
 159 {
 160         char *s, *p;
 161         CamelFolderThreadNode *scan;
 162
 163         s = NULL;
 164         c->re = FALSE;
 165         if (c->message)
 166                 s = (char *)camel_message_info_subject(c->message);
 167         else {
 168                 /* one of the children will always have a message */
 169                 scan = c->child;
 170                 while (scan) {
 171                         if (scan->message) {
 172                                 s = (char *)camel_message_info_subject(scan->message);
 173                                 break;
 174                         }
 175                         scan = scan->next;
 176                 }
 177         }
 178         if (s != NULL) {
 179                 while (*s) {
 180                         while (isspace(*s))
 181                                 s++;
 182                         if (s[0] == 0)
 183                                 break;
 184                         if ((s[0] == 'r' || s[0]=='R')
 185                             && (s[1] == 'e' || s[1]=='E')) {
 186                                 p = s+2;
 187                                 while (isdigit(*p) || (ispunct(*p) && (*p != ':')))
 188                                         p++;
 189                                 if (*p==':') {
 190                                         c->re = TRUE;
 191                                         s = p+1;
 192                                 } else
 193                                         break;
 194                         } else
 195                                 break;
 196                 }
 197                 if (*s)
 198                         return s;
 199         }
 200         return NULL;
 201 }
 202
 203 /* this can be pretty slow, but not used often */
 204 /* clast cannot be null */
 205 static void
 206 remove_node(CamelFolderThreadNode **list, CamelFolderThreadNode *node, CamelFolderThreadNode **clast)
 207 {
 208         CamelFolderThreadNode *c;
 209
 210         /* this is intentional, even if it looks funny */
 211         /* if we have a parent, then we should remove it from the parent list,
 212            otherwise we remove it from the root list */
 213         if (node->parent) {
 214                 c = (CamelFolderThreadNode *)&node->parent->child;
 215         } else {
 216                 c = (CamelFolderThreadNode *)list;
 217         }
 218         while (c->next) {
 219                 if (c->next == node) {
 220                         if (*clast == c->next)
 221                                 *clast = c;
 222                         c->next = c->next->next;
 223                         return;
 224                 }
 225                 c = c->next;
 226         }
 227
 228         printf("ERROR: removing node %p failed\n", node);
 229 }
 230
 231 static void
 232 group_root_set(CamelFolderThread *thread, CamelFolderThreadNode **cp)
 233 {
 234         GHashTable *subject_table = g_hash_table_new(g_str_hash, g_str_equal);
 235         CamelFolderThreadNode *c, *clast, *scan, *container;
 236
 237         /* gather subject lines */
 238         d(printf("gathering subject lines\n"));
 239         clast = (CamelFolderThreadNode *)cp;
 240         c = clast->next;
 241         while (c) {
 242                 c->root_subject = get_root_subject(c);
 243                 if (c->root_subject) {
 244                         container = g_hash_table_lookup(subject_table, c->root_subject);
 245                         if (container == NULL
 246                             || (container->message == NULL && c->message)
 247                             || (container->re == TRUE && !c->re)) {
 248                                 g_hash_table_insert(subject_table, c->root_subject, c);
 249                         }
 250                 }
 251                 c = c->next;
 252         }
 253
 254         /* merge common subjects? */
 255         clast = (CamelFolderThreadNode *)cp;
 256         while (clast->next) {
 257                 c = clast->next;
 258                 d(printf("checking %p %s\n", c, c->root_subject));
 259                 if (c->root_subject
 260                     && (container = g_hash_table_lookup(subject_table, c->root_subject))
 261                     && (container != c)) {
 262                         d(printf(" matching %p %s\n", container, container->root_subject));
 263                         if (c->message == NULL && container->message == NULL) {
 264                                 d(printf("merge containers children\n"));
 265                                 /* steal the children from c onto container, and unlink c */
 266                                 scan = (CamelFolderThreadNode *)&container->child;
 267                                 while (scan->next)
 268                                         scan = scan->next;
 269                                 scan->next = c->child;
 270                                 clast->next = c->next;
 271                                 m(memset(c, 0xee, sizeof(*c)));
 272                                 e_memchunk_free(thread->node_chunks, c);
 273                                 continue;
 274                         } if (c->message == NULL && container->message != NULL) {
 275                                 d(printf("container is non-empty parent\n"));
 276                                 remove_node(cp, container, &clast);
 277                                 container_add_child(c, container);
 278                         } else if (c->message != NULL && container->message == NULL) {
 279                                 d(printf("container is empty child\n"));
 280                                 clast->next = c->next;
 281                                 container_add_child(container, c);
 282                                 continue;
 283                         } else if (c->re && !container->re) {
 284                                 d(printf("container is re\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 not re\n"));
 290                                 remove_node(cp, container, &clast);
 291                                 container_add_child(c, container);
 292                         } else if (c->re && container->re) {
 293                                 d(printf("subjects are common %p and %p\n", c, container));
 294
 295                                 /* build a phantom node */
 296                                 remove_node(cp, container, &clast);
 297                                 remove_node(cp, c, &clast);
 298
 299                                 scan = e_memchunk_alloc0(thread->node_chunks);
 300
 301                                 scan->root_subject = c->root_subject;
 302                                 scan->re = c->re && container->re;
 303                                 scan->next = c->next;
 304                                 clast->next = scan;
 305                                 container_add_child(scan, c);
 306                                 container_add_child(scan, container);
 307                                 clast = scan;
 308                                 g_hash_table_insert(subject_table, scan->root_subject, scan);
 309                                 continue;
 310                         }
 311                 }
 312                 clast = c;
 313         }
 314         g_hash_table_destroy(subject_table);
 315 }
 316
 317 struct _tree_info {
 318         GHashTable *visited;
 319 };
 320
 321 static int
 322 dump_tree_rec(struct _tree_info *info, CamelFolderThreadNode *c, int depth)
 323 {
 324         char *p;
 325         int count=0;
 326
 327         p = alloca(depth*2+1);
 328         memset(p, ' ', depth*2);
 329         p[depth*2] = 0;
 330
 331         while (c) {
 332                 if (g_hash_table_lookup(info->visited, c)) {
 333                         printf("WARNING: NODE REVISITED: %p\n", c);
 334                 } else {
 335                         g_hash_table_insert(info->visited, c, c);
 336                 }
 337                 if (c->message) {
 338                         printf("%s %p Subject: %s <%08x%08x>\n", p, c, camel_message_info_subject(c->message),
 339                                camel_message_info_message_id(c->message)->id.part.hi, camel_message_info_message_id(c->message)->id.part.lo);
 340                         count += 1;
 341                 } else {
 342                         printf("%s %p <empty>\n", p, c);
 343                 }
 344                 if (c->child)
 345                         count += dump_tree_rec(info, c->child, depth+1);
 346                 c = c->next;
 347         }
 348         return count;
 349 }
 350
 351 int
 352 camel_folder_threaded_messages_dump(CamelFolderThreadNode *c)
 353 {
 354         int count;
 355         struct _tree_info info;
 356
 357         info.visited = g_hash_table_new(g_direct_hash, g_direct_equal);
 358         count = dump_tree_rec(&info, c, 0);
 359         g_hash_table_destroy(info.visited);
 360         return count;
 361 }
 362
 363 static int
 364 sort_node(const void *a, const void *b)
 365 {
 366         const CamelFolderThreadNode *a1 = ((CamelFolderThreadNode **)a)[0];
 367         const CamelFolderThreadNode *b1 = ((CamelFolderThreadNode **)b)[0];
 368
 369         /* if we have no message, it must be a dummy node, which
 370            also means it must have a child, just use that as the
 371            sort data (close enough?) */
 372         if (a1->message == NULL)
 373                 a1 = a1->child;
 374         if (b1->message == NULL)
 375                 b1 = b1->child;
 376         if (a1->order == b1->order)
 377                 return 0;
 378         if (a1->order < b1->order)
 379                 return -1;
 380         else
 381                 return 1;
 382 }
 383
 384 static void
 385 sort_thread(CamelFolderThreadNode **cp)
 386 {
 387         CamelFolderThreadNode *c, *head, **carray;
 388         int size=0;
 389
 390         c = *cp;
 391         while (c) {
 392                 /* sort the children while we're at it */
 393                 if (c->child)
 394                         sort_thread(&c->child);
 395                 size++;
 396                 c = c->next;
 397         }
 398         if (size<2)
 399                 return;
 400         carray = alloca(size*sizeof(CamelFolderThreadNode *));
 401         c = *cp;
 402         size=0;
 403         while (c) {
 404                 carray[size] = c;
 405                 c = c->next;
 406                 size++;
 407         }
 408         qsort(carray, size, sizeof(CamelFolderThreadNode *), sort_node);
 409         size--;
 410         head = carray[size];
 411         head->next = NULL;
 412         size--;
 413         do {
 414                 c = carray[size];
 415                 c->next = head;
 416                 head = c;
 417                 size--;
 418         } while (size>=0);
 419         *cp = head;
 420 }
 421
 422 static guint id_hash(void *key)
 423 {
 424         CamelSummaryMessageID *id = (CamelSummaryMessageID *)key;
 425
 426         return id->id.part.lo;
 427 }
 428
 429 static gint id_equal(void *a, void *b)
 430 {
 431         return ((CamelSummaryMessageID *)a)->id.id == ((CamelSummaryMessageID *)b)->id.id;
 432 }
 433
 434 /* perform actual threading */
 435 static void
 436 thread_summary(CamelFolderThread *thread, GPtrArray *summary)
 437 {
 438         GHashTable *id_table, *no_id_table;
 439         int i;
 440         CamelFolderThreadNode *c, *child, *head;
 441 #ifdef TIMEIT
 442         struct timeval start, end;
 443         unsigned long diff;
 444
 445         gettimeofday(&start, NULL);
 446 #endif
 447
 448         id_table = g_hash_table_new((GHashFunc)id_hash, (GCompareFunc)id_equal);
 449         no_id_table = g_hash_table_new(NULL, NULL);
 450         for (i=0;i<summary->len;i++) {
 451                 CamelMessageInfo *mi = summary->pdata[i];
 452                 const CamelSummaryMessageID *mid = camel_message_info_message_id(mi);
 453                 const CamelSummaryReferences *references = camel_message_info_references(mi);
 454
 455                 if (mid->id.id) {
 456                         c = g_hash_table_lookup(id_table, mid);
 457                         /* check for duplicate messages */
 458                         if (c && c->order) {
 459                                 /* if duplicate, just make out it is a no-id message,  but try and insert it
 460                                    into the right spot in the tree */
 461                                 d(printf("doing: (duplicate message id)\n"));
 462                                 c = e_memchunk_alloc0(thread->node_chunks);
 463                                 g_hash_table_insert(no_id_table, (void *)mi, c);
 464                         } else if (!c) {
 465                                 d(printf("doing : %08x%08x (%s)\n", mid->id.part.hi, mid->id.part.lo, camel_message_info_subject(mi)));
 466                                 c = e_memchunk_alloc0(thread->node_chunks);
 467                                 g_hash_table_insert(id_table, (void *)mid, c);
 468                         }
 469                 } else {
 470                         d(printf("doing : (no message id)\n"));
 471                         c = e_memchunk_alloc0(thread->node_chunks);
 472                         g_hash_table_insert(no_id_table, (void *)mi, c);
 473                 }
 474
 475                 c->message = mi;
 476                 c->order = i+1;
 477                 child = c;
 478                 if (references) {
 479                         int j;
 480
 481                         d(printf("%s (%s) references:\n", G_STRLOC, G_STRFUNC); )
 482                         for (j=0;j<references->size;j++) {
 483                                 /* should never be empty, but just incase */
 484                                 if (references->references[j].id.id == 0)
 485                                         continue;
 486
 487                                 c = g_hash_table_lookup(id_table, &references->references[j]);
 488                                 if (c == NULL) {
 489                                         d(printf("%s (%s) not found\n", G_STRLOC, G_STRFUNC));
 490                                         c = e_memchunk_alloc0(thread->node_chunks);
 491                                         g_hash_table_insert(id_table, (void *)&references->references[j], c);
 492                                 }
 493                                 if (c!=child)
 494                                         container_parent_child(c, child);
 495                                 child = c;
 496                         }
 497                 }
 498         }
 499
 500         d(printf("\n\n"));
 501         /* build a list of root messages (no parent) */
 502         head = NULL;
 503         g_hash_table_foreach(id_table, hashloop, &head);
 504         g_hash_table_foreach(no_id_table, hashloop, &head);
 505
 506         g_hash_table_destroy(id_table);
 507         g_hash_table_destroy(no_id_table);
 508
 509         /* remove empty parent nodes */
 510         prune_empty(thread, &head);
 511
 512         /* find any siblings which missed out - but only if we are allowing threading by subject */
 513         if (thread->subject)
 514                 group_root_set (thread, &head);
 515
 516 #if 0
 517         printf("finished\n");
 518         i = camel_folder_threaded_messages_dump(head);
 519         printf("%d count, %d items in tree\n", summary->len, i);
 520 #endif
 521
 522         sort_thread(&head);
 523
 524         /* remove any phantom nodes, this could possibly be put in group_root_set()? */
 525         c = (CamelFolderThreadNode *)&head;
 526         while (c && c->next) {
 527                 CamelFolderThreadNode *scan, *newtop;
 528
 529                 child = c->next;
 530                 if (child->message == NULL) {
 531                         newtop = child->child;
 532                         newtop->parent = NULL;
 533                         /* unlink pseudo node */
 534                         c->next = newtop;
 535
 536                         /* link its siblings onto the end of its children, fix all parent pointers */
 537                         scan = (CamelFolderThreadNode *)&newtop->child;
 538                         while (scan->next) {
 539                                 scan = scan->next;
 540                         }
 541                         scan->next = newtop->next;
 542                         while (scan->next) {
 543                                 scan = scan->next;
 544                                 scan->parent = newtop;
 545                         }
 546
 547                         /* and link the now 'real' node into the list */
 548                         newtop->next = child->next;
 549                         c = newtop;
 550                         m(memset(child, 0xde, sizeof(*child)));
 551                         e_memchunk_free(thread->node_chunks, child);
 552                 } else {
 553                         c = child;
 554                 }
 555         }
 556
 557         /* this is only debug assertion stuff */
 558         c = (CamelFolderThreadNode *)&head;
 559         while (c->next) {
 560                 c = c->next;
 561                 if (c->message == NULL)
 562                         g_warning("threading missed removing a pseudo node: %s\n", c->root_subject);
 563                 if (c->parent != NULL)
 564                         g_warning("base node has a non-null parent: %s\n", c->root_subject);
 565         }
 566
 567         thread->tree = head;
 568
 569 #ifdef TIMEIT
 570         gettimeofday(&end, NULL);
 571         diff = end.tv_sec * 1000 + end.tv_usec/1000;
 572         diff -= start.tv_sec * 1000 + start.tv_usec/1000;
 573         printf("Message threading %d messages took %ld.%03ld seconds\n",
 574                summary->len, diff / 1000, diff % 1000);
 575 #endif
 576 }
 577
 578 /**
 579  * camel_folder_thread_messages_new:
 580  * @folder:
 581  * @uids: The subset of uid's to thread.  If NULL. then thread all
 582  * uid's in @folder.
 583  * @thread_subject: thread based on subject also
 584  *
 585  * Thread a (subset) of the messages in a folder.  And sort the result
 586  * in summary order.
 587  *
 588  * If @thread_subject is %TRUE, messages with
 589  * related subjects will also be threaded. The default behaviour is to
 590  * only thread based on message-id.
 591  *
 592  * This function is probably to be removed soon.
 593  *
 594  * Return value: A CamelFolderThread contianing a tree of CamelFolderThreadNode's
 595  * which represent the threaded structure of the messages.
 596  **/
 597 CamelFolderThread *
 598 camel_folder_thread_messages_new (CamelFolder *folder, GPtrArray *uids, gboolean thread_subject)
 599 {
 600         CamelFolderThread *thread;
 601         GHashTable *wanted = NULL;
 602         GPtrArray *summary;
 603         GPtrArray *fsummary;
 604         int i;
 605
 606         thread = g_malloc(sizeof(*thread));
 607         thread->refcount = 1;
 608         thread->subject = thread_subject;
 609         thread->tree = NULL;
 610         thread->node_chunks = e_memchunk_new(32, sizeof(CamelFolderThreadNode));
 611         thread->folder = folder;
 612         camel_object_ref((CamelObject *)folder);
 613
 614         /* get all of the summary items of interest in summary order */
 615         if (uids) {
 616                 wanted = g_hash_table_new(g_str_hash, g_str_equal);
 617                 for (i=0;i<uids->len;i++)
 618                         g_hash_table_insert(wanted, uids->pdata[i], uids->pdata[i]);
 619         }
 620
 621         fsummary = camel_folder_get_summary(folder);
 622         thread->summary = summary = g_ptr_array_new();
 623
 624         for (i=0;i<fsummary->len;i++) {
 625                 CamelMessageInfo *info = fsummary->pdata[i];
 626
 627                 if (wanted == NULL || g_hash_table_lookup(wanted, camel_message_info_uid(info)) != NULL) {
 628                         camel_folder_ref_message_info(folder, info);
 629                         g_ptr_array_add(summary, info);
 630                 }
 631         }
 632
 633         camel_folder_free_summary(folder, fsummary);
 634
 635         thread_summary(thread, summary);
 636
 637         if (wanted)
 638                 g_hash_table_destroy(wanted);
 639
 640         return thread;
 641 }
 642
 643 /* add any still there, in the existing order */
 644 static void
 645 add_present_rec(CamelFolderThread *thread, GHashTable *have, GPtrArray *summary, CamelFolderThreadNode *node)
 646 {
 647         while (node) {
 648                 const char *uid = camel_message_info_uid(node->message);
 649
 650                 if (g_hash_table_lookup(have, (char *)uid)) {
 651                         g_hash_table_remove(have, (char *)camel_message_info_uid(node->message));
 652                         g_ptr_array_add(summary, (void *) node->message);
 653                 } else {
 654                         camel_folder_free_message_info(thread->folder, (CamelMessageInfo *)node->message);
 655                 }
 656
 657                 if (node->child)
 658                         add_present_rec(thread, have, summary, node->child);
 659                 node = node->next;
 660         }
 661 }
 662
 663 void
 664 camel_folder_thread_messages_apply(CamelFolderThread *thread, GPtrArray *uids)
 665 {
 666         int i;
 667         GPtrArray *all;
 668         GHashTable *table;
 669         CamelMessageInfo *info;
 670
 671         all = g_ptr_array_new();
 672         table = g_hash_table_new(g_str_hash, g_str_equal);
 673         for (i=0;i<uids->len;i++)
 674                 g_hash_table_insert(table, uids->pdata[i], uids->pdata[i]);
 675
 676         add_present_rec(thread, table, all, thread->tree);
 677
 678         /* add any new ones, in supplied order */
 679         for (i=0;i<uids->len;i++)
 680                 if (g_hash_table_lookup(table, uids->pdata[i]) && (info = camel_folder_get_message_info(thread->folder, uids->pdata[i])))
 681                         g_ptr_array_add(all, info);
 682
 683         g_hash_table_destroy(table);
 684
 685         thread->tree = NULL;
 686         e_memchunk_destroy(thread->node_chunks);
 687         thread->node_chunks = e_memchunk_new(32, sizeof(CamelFolderThreadNode));
 688         thread_summary(thread, all);
 689
 690         g_ptr_array_free(thread->summary, TRUE);
 691         thread->summary = all;
 692 }
 693
 694 void
 695 camel_folder_thread_messages_ref(CamelFolderThread *thread)
 696 {
 697         thread->refcount++;
 698 }
 699
 700 /**
 701  * camel_folder_thread_messages_unref:
 702  * @thread:
 703  *
 704  * Free all memory associated with the thread descriptor @thread.
 705  **/
 706 void
 707 camel_folder_thread_messages_unref(CamelFolderThread *thread)
 708 {
 709         if (thread->refcount > 1) {
 710                 thread->refcount--;
 711                 return;
 712         }
 713
 714         if (thread->folder) {
 715                 int i;
 716
 717                 for (i=0;i<thread->summary->len;i++)
 718                         camel_folder_free_message_info(thread->folder, thread->summary->pdata[i]);
 719                 g_ptr_array_free(thread->summary, TRUE);
 720                 camel_object_unref((CamelObject *)thread->folder);
 721         }
 722         e_memchunk_destroy(thread->node_chunks);
 723         g_free(thread);
 724 }
 725
 726 #if 0
 727 /**
 728  * camel_folder_thread_messages_new_summary:
 729  * @summary: Array of CamelMessageInfo's to thread.
 730  *
 731  * Thread a list of MessageInfo's.  The summary must remain valid for the
 732  * life of the CamelFolderThread created by this function, and it is upto the
 733  * caller to ensure this.
 734  *
 735  * Return value: A CamelFolderThread contianing a tree of CamelFolderThreadNode's
 736  * which represent the threaded structure of the messages.
 737  **/
 738 CamelFolderThread *
 739 camel_folder_thread_messages_new_summary(GPtrArray *summary)
 740 {
 741         CamelFolderThread *thread;
 742
 743 #ifdef TIMEIT
 744         struct timeval start, end;
 745         unsigned long diff;
 746
 747         gettimeofday(&start, NULL);
 748 #endif
 749
 750         thread = g_malloc(sizeof(*thread));
 751         thread->refcount = 1;
 752         thread->tree = NULL;
 753         thread->node_chunks = e_memchunk_new(32, sizeof(CamelFolderThreadNode));
 754         thread->folder = NULL;
 755         thread->summary = NULL;
 756
 757         thread_summary(thread, summary);
 758
 759         return thread;
 760 }
 761
 762 /* scan the list in depth-first fashion */
 763 static void
 764 build_summary_rec(GHashTable *have, GPtrArray *summary, CamelFolderThreadNode *node)
 765 {
 766         while (node) {
 767                 if (node->message)
 768                         g_hash_table_insert(have, (char *)camel_message_info_uid(node->message), node->message);
 769                 g_ptr_array_add(summary, node);
 770                 if (node->child)
 771                         build_summary_rec(have, summary, node->child);
 772                 node = node->next;
 773         }
 774 }
 775
 776 void
 777 camel_folder_thread_messages_add(CamelFolderThread *thread, GPtrArray *summary)
 778 {
 779         GPtrArray *all;
 780         int i;
 781         GHashTable *table;
 782
 783         /* Instead of working out all the complex in's and out's of
 784            trying to do an incremental summary generation, just redo the whole
 785            thing with the summary in the current order - so it comes out
 786            in the same order */
 787
 788         all = g_ptr_array_new();
 789         table = g_hash_table_new(g_str_hash, g_str_equal);
 790         build_summary_rec(table, all, thread->tree);
 791         for (i=0;i<summary->len;i++) {
 792                 CamelMessageInfo *info = summary->pdata[i];
 793
 794                 /* check its not already there, we dont want duplicates */
 795                 if (g_hash_table_lookup(table, camel_message_info_uid(info)) == NULL)
 796                         g_ptr_array_add(all, info);
 797         }
 798         g_hash_table_destroy(table);
 799
 800         /* reset the tree, and rebuild fully */
 801         thread->tree = NULL;
 802         e_memchunk_empty(thread->node_chunks);
 803         thread_summary(thread, all);
 804 }
 805
 806 static void
 807 remove_uid_node_rec(CamelFolderThread *thread, GHashTable *table, CamelFolderThreadNode **list, CamelFolderThreadNode *parent)
 808 {
 809         CamelFolderThreadNode *prev = NULL;
 810         CamelFolderThreadNode *node, *next, *child, *rest;
 811
 812         node = (CamelFolderThreadNode *)list;
 813         next = node->next;
 814         while (next) {
 815
 816                 if (next->child)
 817                         remove_uid_node_rec(thread, table, &next->child, next);
 818
 819                 /* do we have a node to remove? */
 820                 if (next->message && g_hash_table_lookup(table, (char *)camel_message_info_uid(node->message))) {
 821                         child = next->child;
 822                         if (child) {
 823                                 /*
 824                                   node
 825                                   next
 826                                    child
 827                                    lchild
 828                                   rest
 829
 830                                   becomes:
 831                                   node
 832                                   child
 833                                   lchild
 834                                   rest
 835                                 */
 836
 837                                 rest = next->next;
 838                                 node->next = child;
 839                                 e_memchunk_free(thread->node_chunks, next);
 840                                 next = child;
 841                                 do {
 842                                         lchild = child;
 843                                         child->parent = parent;
 844                                         child = child->next;
 845                                 } while (child);
 846                                 lchild->next = rest;
 847                         } else {
 848                                 /*
 849                                   node
 850                                   next
 851                                   rest
 852                                   becomes:
 853                                   node
 854                                   rest */
 855                                 node->next = next->next;
 856                                 e_memchunk_free(thread->node_chunks, next);
 857                                 next = node->next;
 858                         }
 859                 } else {
 860                         node = next;
 861                         next = node->next;
 862                 }
 863         }
 864 }
 865
 866 void
 867 camel_folder_thread_messages_remove(CamelFolderThread *thread, GPtrArray *uids)
 868 {
 869         GHashTable *table;
 870         int i;
 871
 872         table = g_hash_table_new(g_str_hash, g_str_equal);
 873         for (i=0;i<uids->len;i++)
 874                 g_hash_table_insert(table, uids->pdata[i], uids->pdata[i]);
 875
 876         remove_uid_node_rec(thread, table, &thread->tree, NULL);
 877         g_hash_table_destroy(table);
 878 }
 879
 880 #endif