Initial revision

9 files changed, 4402 insertions, 0 deletions

diff --git a/libetpan/src/driver/tools/generic_cache.c b/libetpan/src/driver/tools/generic_cache.c
new file mode 100644
index 0000000..3ff6e43
--- a/dev/null
+++ b/libetpan/src/driver/tools/generic_cache.c
@@ -0,0 +1,729 @@
+/*
+ * libEtPan! -- a mail stuff library
+ *
+ * Copyright (C) 2001, 2005 - DINH Viet Hoa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the libEtPan! project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * $Id$
+ */
+
+#include "generic_cache.h"
+
+#include "libetpan-config.h"
+
+#include <unistd.h>
+#include <string.h>
+#include <sys/mman.h>
+#include <stdio.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <stdlib.h>
+
+#include "maildriver_types.h"
+#include "imfcache.h"
+#include "chash.h"
+#include "mailmessage.h"
+#include "mail_cache_db.h"
+
+int generic_cache_create_dir(char * dirname)
+{
+  struct stat buf;
+  int r;
+
+  r = stat(dirname, &buf);
+  if (r != 0) {
+    r = mkdir(dirname, 0700);
+
+    if (r < 0)
+      return MAIL_ERROR_FILE;
+  }
+  else {
+    if (!S_ISDIR(buf.st_mode))
+      return MAIL_ERROR_FILE;
+  }
+
+  return MAIL_NO_ERROR;
+}
+
+int generic_cache_store(char * filename, char * content, size_t length)
+{
+  int fd;
+  char * str;
+
+  fd = open(filename, O_CREAT | O_RDWR, S_IRUSR | S_IWUSR);
+  if (fd == -1)
+    return MAIL_ERROR_FILE;
+
+  if (ftruncate(fd, length) < 0)
+    return MAIL_ERROR_FILE;
+  
+  str = mmap(NULL, length, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
+  if (str == MAP_FAILED)
+    return MAIL_ERROR_FILE;
+
+  memcpy(str, content, length);
+  msync(str, length, MS_SYNC);
+  munmap(str, length);
+
+  close(fd);
+
+  return MAIL_NO_ERROR;
+}
+
+int generic_cache_read(char * filename, char ** result, size_t * result_len)
+{
+  int fd;
+  char * str;
+  struct stat buf;
+  MMAPString * mmapstr;
+  char * content;
+  int res;
+
+  if (stat(filename, &buf) < 0) {
+    res = MAIL_ERROR_CACHE_MISS;
+    goto err;
+  }
+
+  fd = open(filename, O_RDONLY);
+  if (fd == -1) {
+    res = MAIL_ERROR_CACHE_MISS;
+    goto err;
+  }
+
+  str = mmap(NULL, buf.st_size, PROT_READ, MAP_PRIVATE, fd, 0);
+  if (str == MAP_FAILED) {
+    res = MAIL_ERROR_FILE;
+    goto close;
+  }
+
+  mmapstr = mmap_string_new_len(str, buf.st_size);
+  if (mmapstr == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto unmap;
+  }
+  
+  if (mmap_string_ref(mmapstr) < 0) {
+    res = MAIL_ERROR_MEMORY;
+    goto free;
+  }
+  
+  content = mmapstr->str;
+
+  munmap(str, buf.st_size);
+  close(fd);
+
+  * result = content;
+  * result_len = buf.st_size;
+
+  return MAIL_NO_ERROR;
+
+ free:
+  mmap_string_free(mmapstr);
+ unmap:
+  munmap(str, buf.st_size);
+ close:
+  close(fd);
+ err:
+  return res;
+}
+
+static int flags_extension_read(MMAPString * mmapstr, size_t * index,
+				clist ** result)
+{
+  clist * list;
+  int r;
+  uint32_t count;
+  uint32_t i;
+  int res;
+
+  r = mailimf_cache_int_read(mmapstr, index, &count);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  list = clist_new();
+  if (list == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+
+  for(i = 0 ; i < count ; i++) {
+    char * str;
+
+    r = mailimf_cache_string_read(mmapstr, index, &str);
+    if (r != MAIL_NO_ERROR) {
+      res = r;
+      goto free_list;
+    }
+
+    r = clist_append(list, str);
+    if (r < 0) {
+      free(str);
+      res = MAIL_ERROR_MEMORY;
+      goto free_list;
+    }
+  }
+
+  * result = list;
+
+  return MAIL_NO_ERROR;
+
+ free_list:
+  clist_foreach(list, (clist_func) free, NULL);
+  clist_free(list);
+ err:
+  return res;
+}
+
+static int generic_flags_read(MMAPString * mmapstr, size_t * index,
+			      struct mail_flags ** result)
+{
+  clist * ext;
+  int r;
+  struct mail_flags * flags;
+  uint32_t value;
+  int res;
+  
+  r = mailimf_cache_int_read(mmapstr, index, &value);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+  
+  r = flags_extension_read(mmapstr, index, &ext);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+  
+  flags = mail_flags_new(value, ext);
+  if (flags == NULL) {
+    res = r;
+    goto free;
+  }
+
+  * result = flags;
+  
+  return MAIL_NO_ERROR;
+
+ free:
+  clist_foreach(ext, (clist_func) free, NULL);
+  clist_free(ext);
+ err:
+  return res;
+}
+
+static int flags_extension_write(MMAPString * mmapstr, size_t * index,
+				 clist * ext)
+{
+  int r;
+  clistiter * cur;
+
+  r = mailimf_cache_int_write(mmapstr, index, clist_count(ext));
+  if (r != MAIL_NO_ERROR)
+    return r;
+  
+  for(cur = clist_begin(ext) ; cur != NULL ; cur = clist_next(cur)) {
+    r = mailimf_cache_string_write(mmapstr, index,
+        clist_content(cur), strlen(clist_content(cur)));
+    if (r != MAIL_NO_ERROR)
+      return r;
+  }
+
+  return MAIL_NO_ERROR;
+}
+
+static int generic_flags_write(MMAPString * mmapstr, size_t * index,
+			       struct mail_flags * flags)
+{
+  int r;
+
+  r = mailimf_cache_int_write(mmapstr, index,
+      flags->fl_flags & ~MAIL_FLAG_NEW);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = flags_extension_write(mmapstr, index,
+      flags->fl_extension);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  return MAIL_NO_ERROR;
+}
+
+
+
+
+static struct mail_flags * mail_flags_dup(struct mail_flags * flags)
+{
+  clist * list;
+  struct mail_flags * new_flags;
+  int r;
+  clistiter * cur;
+
+  list = clist_new();
+  if (list == NULL) {
+    goto err;
+  }
+
+  for(cur = clist_begin(flags->fl_extension) ; cur != NULL ;
+      cur = clist_next(cur)) {
+    char * ext;
+    
+    ext = strdup(clist_content(cur));
+    if (ext == NULL) {
+      goto free;
+    }
+
+    r = clist_append(list, ext);
+    if (r < 0) {
+      free(ext);
+      goto free;
+    }
+  }
+
+  new_flags = mail_flags_new(flags->fl_flags, list);
+  if (new_flags == NULL) {
+    goto free;
+  }
+
+  return new_flags;
+
+ free:
+  clist_foreach(list, (clist_func) free, NULL);
+  clist_free(list);
+ err:
+  return NULL;
+}
+
+static mailmessage * mailmessage_build(mailmessage * msg)
+{
+  mailmessage * new_msg;
+
+  new_msg = malloc(sizeof(* new_msg));
+  if (new_msg == NULL)
+    goto err;
+
+  new_msg->msg_session = msg->msg_session;
+  new_msg->msg_driver = msg->msg_driver;
+  new_msg->msg_index = msg->msg_index;
+  if (msg->msg_uid == NULL)
+    new_msg->msg_uid = NULL;
+  else {
+    new_msg->msg_uid = strdup(msg->msg_uid);
+    if (new_msg->msg_uid == NULL)
+      goto free;
+  }
+
+  new_msg->msg_cached = msg->msg_cached;
+  new_msg->msg_size = msg->msg_size;
+  new_msg->msg_fields = NULL;
+  new_msg->msg_flags = mail_flags_dup(msg->msg_flags);
+  if (new_msg->msg_flags == NULL) {
+    free(new_msg->msg_uid);
+    goto free;
+  }
+
+  new_msg->msg_mime = NULL;
+  new_msg->msg_data = NULL;
+
+  return new_msg;
+
+ free:
+  free(new_msg);
+ err:
+  return NULL;
+}
+
+struct mail_flags_store * mail_flags_store_new(void)
+{
+  struct mail_flags_store * flags_store;
+
+  flags_store = malloc(sizeof(struct mail_flags_store));
+  if (flags_store == NULL)
+    goto err;
+
+  flags_store->fls_tab = carray_new(128);
+  if (flags_store->fls_tab == NULL)
+    goto free;
+
+  flags_store->fls_hash = chash_new(128, CHASH_COPYALL);
+  if (flags_store->fls_hash == NULL)
+    goto free_tab;
+  
+  return flags_store;
+
+ free_tab:
+  carray_free(flags_store->fls_tab);
+ free:
+  free(flags_store);
+ err:
+  return NULL;
+}
+
+void mail_flags_store_clear(struct mail_flags_store * flags_store)
+{
+  unsigned int i;
+
+  for(i = 0 ; i < carray_count(flags_store->fls_tab) ; i ++) {
+    chashdatum key;
+    mailmessage * msg;
+
+    msg = carray_get(flags_store->fls_tab, i);
+
+    key.data = &msg->msg_index;
+    key.len = sizeof(msg->msg_index);
+    chash_delete(flags_store->fls_hash, &key, NULL);
+
+    mailmessage_free(msg);
+  }
+  carray_set_size(flags_store->fls_tab, 0);
+}
+
+void mail_flags_store_free(struct mail_flags_store * flags_store)
+{
+  mail_flags_store_clear(flags_store);
+  chash_free(flags_store->fls_hash);
+  carray_free(flags_store->fls_tab);
+  free(flags_store);
+}
+
+int mail_flags_store_set(struct mail_flags_store * flags_store,
+			 mailmessage * msg)
+{
+  chashdatum key;
+  chashdatum value;
+  unsigned int index;
+  int res;
+  int r;
+  mailmessage * new_msg;
+
+  if (msg->msg_flags == NULL) {
+    res = MAIL_NO_ERROR;
+    goto err;
+  }
+
+  /* duplicate needed message info */
+  new_msg = mailmessage_build(msg);
+  if (new_msg == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+
+  key.data = &new_msg->msg_index;
+  key.len = sizeof(new_msg->msg_index);
+
+  r = chash_get(flags_store->fls_hash, &key, &value);
+  if (r == 0) {
+    mailmessage * old_msg;
+
+    index = * (unsigned int *) value.data;
+    old_msg = carray_get(flags_store->fls_tab, index);
+    mailmessage_free(old_msg);
+  }
+  else {
+    r = carray_set_size(flags_store->fls_tab,
+        carray_count(flags_store->fls_tab) + 1);
+    if (r != 0) {
+      res = MAIL_ERROR_MEMORY;
+      goto err;
+    }
+    index = carray_count(flags_store->fls_tab) - 1;
+  }
+
+  carray_set(flags_store->fls_tab, index, new_msg);
+  
+  value.data = &index;
+  value.len = sizeof(index);
+
+  r = chash_set(flags_store->fls_hash, &key, &value, NULL);
+  if (r < 0) {
+    carray_delete(flags_store->fls_tab, index);
+    res = MAIL_ERROR_MEMORY;
+    goto free;
+  }
+
+  return MAIL_NO_ERROR;
+
+ free:
+  mailmessage_free(new_msg);
+ err:
+  return res;
+}
+
+static int msg_index_compare(mailmessage ** msg1, mailmessage ** msg2)
+{
+  return (* msg1)->msg_index - (* msg2)->msg_index;
+}
+
+void mail_flags_store_sort(struct mail_flags_store * flags_store)
+{
+  qsort(carray_data(flags_store->fls_tab),
+      carray_count(flags_store->fls_tab), sizeof(mailmessage *),
+      (int (*)(const void *, const void *)) msg_index_compare);
+}
+
+struct mail_flags *
+mail_flags_store_get(struct mail_flags_store * flags_store, uint32_t index)
+{
+  struct mail_flags * flags;
+  chashdatum key;
+  chashdatum value;
+  int r;
+  unsigned int tab_index;
+  mailmessage * msg;
+  
+  key.data = &index;
+  key.len = sizeof(index);
+
+  r = chash_get(flags_store->fls_hash, &key, &value);
+  
+  if (r < 0)
+    return NULL;
+  
+#if 0
+  flags = mail_flags_dup((struct mail_flags *) value.data);
+#endif
+  tab_index = * (unsigned int *) value.data;
+  msg = carray_get(flags_store->fls_tab, tab_index);
+  if (msg->msg_flags == NULL)
+    return NULL;
+  
+  flags = mail_flags_dup(msg->msg_flags);
+  
+  return flags;
+}
+
+int mail_flags_compare(struct mail_flags * flags1, struct mail_flags * flags2)
+{
+  clistiter * cur1;
+
+  if (clist_count(flags1->fl_extension) != clist_count(flags2->fl_extension))
+    return -1;
+
+  for(cur1 = clist_begin(flags1->fl_extension) ; cur1 != NULL ;
+      cur1 = clist_next(cur1)) {
+    char * flag1;
+    clistiter * cur2;
+    int found;
+
+    flag1 = clist_content(cur1);
+
+    found = 0;
+    for(cur2 = clist_begin(flags2->fl_extension) ; cur2 != NULL ;
+        cur2 = clist_next(cur2)) {
+      char * flag2;
+
+      flag2 = clist_content(cur2);
+
+      if (strcasecmp(flag1, flag2) == 0) {
+        found = 1;
+        break;
+      }
+    }
+
+    if (!found)
+      return -1;
+  }
+
+  return flags1->fl_flags - flags2->fl_flags;
+}
+
+
+int generic_cache_fields_read(struct mail_cache_db * cache_db,
+    MMAPString * mmapstr,
+    char * keyname, struct mailimf_fields ** result)
+{
+  int r;
+  int res;
+  size_t cur_token;
+  struct mailimf_fields * fields;
+  void * data;
+  size_t data_len;
+  
+  r = mail_cache_db_get(cache_db, keyname, strlen(keyname), &data, &data_len);
+  if (r != 0) {
+    res = MAIL_ERROR_CACHE_MISS;
+    goto err;
+  }
+  
+  r = mail_serialize_clear(mmapstr, &cur_token);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  if (mmap_string_append_len(mmapstr, data, data_len) == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+
+  r = mailimf_cache_fields_read(mmapstr, &cur_token, &fields);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  * result = fields;
+
+  return MAIL_NO_ERROR;
+
+ err:
+  return res;
+}
+
+int generic_cache_fields_write(struct mail_cache_db * cache_db,
+    MMAPString * mmapstr,
+    char * keyname, struct mailimf_fields * fields)
+{
+  int r;
+  int res;
+  size_t cur_token;
+
+  r = mail_serialize_clear(mmapstr, &cur_token);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  r = mailimf_cache_fields_write(mmapstr, &cur_token, fields);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  r = mail_cache_db_put(cache_db, keyname, strlen(keyname),
+      mmapstr->str, mmapstr->len);
+  if (r != 0) {
+    res = MAIL_ERROR_FILE;
+    goto err;
+  }
+
+  return MAIL_NO_ERROR;
+  
+ err:
+  return res;
+}
+
+int generic_cache_flags_read(struct mail_cache_db * cache_db,
+    MMAPString * mmapstr,
+    char * keyname, struct mail_flags ** result)
+{
+  int r;
+  int res;
+  size_t cur_token;
+  struct mail_flags * flags;
+  void * data;
+  size_t data_len;
+
+  r = mail_cache_db_get(cache_db, keyname, strlen(keyname), &data, &data_len);
+  if (r != 0) {
+    res = MAIL_ERROR_CACHE_MISS;
+    goto err;
+  }
+  
+  r = mail_serialize_clear(mmapstr, &cur_token);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  if (mmap_string_append_len(mmapstr, data, data_len) == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+
+  r = generic_flags_read(mmapstr, &cur_token, &flags);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  * result = flags;
+
+  return MAIL_NO_ERROR;
+
+ err:
+  return res;
+}
+
+int generic_cache_flags_write(struct mail_cache_db * cache_db,
+    MMAPString * mmapstr,
+    char * keyname, struct mail_flags * flags)
+{
+  int r;
+  int res;
+  size_t cur_token;
+
+  r = mail_serialize_clear(mmapstr, &cur_token);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  r = generic_flags_write(mmapstr, &cur_token, flags);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  r = mail_cache_db_put(cache_db, keyname, strlen(keyname),
+      mmapstr->str, mmapstr->len);
+  if (r != 0) {
+    res = MAIL_ERROR_FILE;
+    goto err;
+  }
+
+  return MAIL_NO_ERROR;
+  
+ err:
+  return res;
+}
+
+
+int generic_cache_delete(struct mail_cache_db * cache_db,
+    char * keyname)
+{
+  int r;
+  int res;
+
+  r = mail_cache_db_del(cache_db, keyname, strlen(keyname));
+  if (r != 0) {
+    res = MAIL_ERROR_FILE;
+    goto err;
+  }
+
+  return MAIL_NO_ERROR;
+  
+ err:
+  return res;
+}
diff --git a/libetpan/src/driver/tools/generic_cache.h b/libetpan/src/driver/tools/generic_cache.h
new file mode 100644
index 0000000..934a53d
--- a/dev/null
+++ b/libetpan/src/driver/tools/generic_cache.h
@@ -0,0 +1,109 @@
+/*
+ * libEtPan! -- a mail stuff library
+ *
+ * Copyright (C) 2001, 2005 - DINH Viet Hoa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the libEtPan! project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * $Id$
+ */
+
+#ifndef GENERIC_CACHE_H
+
+#define GENERIC_CACHE_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include "generic_cache_types.h"
+#include "mailmessage_types.h"
+#include "chash.h"
+#include "carray.h"
+#include "mail_cache_db_types.h"
+
+int generic_cache_create_dir(char * dirname);
+
+int generic_cache_store(char * filename, char * content, size_t length);
+int generic_cache_read(char * filename, char ** result, size_t * result_len);
+
+int generic_cache_fields_read(struct mail_cache_db * cache_db,
+    MMAPString * mmapstr,
+    char * keyname, struct mailimf_fields ** result);
+  
+int generic_cache_fields_write(struct mail_cache_db * cache_db,
+    MMAPString * mmapstr,
+    char * keyname, struct mailimf_fields * fields);
+  
+int generic_cache_flags_read(struct mail_cache_db * cache_db,
+    MMAPString * mmapstr,
+    char * keyname, struct mail_flags ** result);
+  
+int generic_cache_flags_write(struct mail_cache_db * cache_db,
+    MMAPString * mmapstr,
+    char * keyname, struct mail_flags * flags);
+  
+int generic_cache_delete(struct mail_cache_db * cache_db, char * keyname);
+
+#if 0
+int generic_cache_fields_read(DB * dbp, MMAPString * mmapstr,
+			      char * keyname, struct mailimf_fields ** result);
+
+int generic_cache_fields_write(DB * dbp, MMAPString * mmapstr,
+			       char * keyname, struct mailimf_fields * fields);
+
+int generic_cache_flags_read(DB * dbp, MMAPString * mmapstr,
+			     char * keyname, struct mail_flags ** result);
+
+int generic_cache_flags_write(DB * dbp, MMAPString * mmapstr,
+			      char * keyname, struct mail_flags * flags);
+
+int generic_cache_delete(DB * dbp, char * keyname);
+#endif
+
+struct mail_flags_store * mail_flags_store_new(void);
+
+void mail_flags_store_clear(struct mail_flags_store * flags_store);
+
+void mail_flags_store_free(struct mail_flags_store * flags_store);
+
+int mail_flags_store_set(struct mail_flags_store * flags_store,
+    mailmessage * msg);
+
+void mail_flags_store_sort(struct mail_flags_store * flags_store);
+
+struct mail_flags *
+mail_flags_store_get(struct mail_flags_store * flags_store, uint32_t index);
+
+int mail_flags_compare(struct mail_flags * flags1, struct mail_flags * flags2);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/libetpan/src/driver/tools/generic_cache_types.h b/libetpan/src/driver/tools/generic_cache_types.h
new file mode 100644
index 0000000..bc69b3c
--- a/dev/null
+++ b/libetpan/src/driver/tools/generic_cache_types.h
@@ -0,0 +1,56 @@
+/*
+ * libEtPan! -- a mail stuff library
+ *
+ * Copyright (C) 2001, 2005 - DINH Viet Hoa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the libEtPan! project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * $Id$
+ */
+
+#ifndef GENERIC_CACHE_TYPE_H
+
+#define GENERIC_CACHE_TYPE_H
+
+#include <libetpan/carray.h>
+#include <libetpan/chash.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+struct mail_flags_store {
+  carray * fls_tab;
+  chash * fls_hash;
+};
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/libetpan/src/driver/tools/imfcache.c b/libetpan/src/driver/tools/imfcache.c
new file mode 100644
index 0000000..7c6a5be
--- a/dev/null
+++ b/libetpan/src/driver/tools/imfcache.c
@@ -0,0 +1,1429 @@
+/*
+ * libEtPan! -- a mail stuff library
+ *
+ * Copyright (C) 2001, 2005 - DINH Viet Hoa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the libEtPan! project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * $Id$
+ */
+
+#include "imfcache.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+static int mailimf_cache_field_write(MMAPString * mmapstr, size_t * index,
+				     struct mailimf_field * field);
+static int mailimf_cache_orig_date_write(MMAPString * mmapstr, size_t * index,
+					 struct mailimf_orig_date * date);
+static int mailimf_cache_date_time_write(MMAPString * mmapstr, size_t * index,
+					 struct mailimf_date_time * date_time);
+static int mailimf_cache_from_write(MMAPString * mmapstr, size_t * index,
+				    struct mailimf_from * from);
+static int mailimf_cache_sender_write(MMAPString * mmapstr, size_t * index,
+				      struct mailimf_sender * sender);
+static int mailimf_cache_reply_to_write(MMAPString * mmapstr, size_t * index,
+					struct mailimf_reply_to * reply_to);
+static int mailimf_cache_to_write(MMAPString * mmapstr, size_t * index,
+				  struct mailimf_to * to);
+static int mailimf_cache_cc_write(MMAPString * mmapstr, size_t * index,
+				  struct mailimf_cc * to);
+static int mailimf_cache_bcc_write(MMAPString * mmapstr, size_t * index,
+				   struct mailimf_bcc * to);
+static int mailimf_cache_message_id_write(MMAPString * mmapstr, size_t * index,
+					  struct mailimf_message_id * message_id);
+static int mailimf_cache_msg_id_list_write(MMAPString * mmapstr, size_t * index,
+					   clist * list);
+static int mailimf_cache_in_reply_to_write(MMAPString * mmapstr, size_t * index,
+					   struct mailimf_in_reply_to *
+					   in_reply_to);
+static int mailimf_cache_references_write(MMAPString * mmapstr, size_t * index,
+					  struct mailimf_references * references);
+static int mailimf_cache_subject_write(MMAPString * mmapstr, size_t * index,
+				       struct mailimf_subject * subject);
+static int mailimf_cache_address_list_write(MMAPString * mmapstr,
+					    size_t * index,
+					    struct mailimf_address_list *
+					    addr_list);
+static int mailimf_cache_address_write(MMAPString * mmapstr, size_t * index,
+				       struct mailimf_address * addr);
+static int mailimf_cache_group_write(MMAPString * mmapstr, size_t * index,
+				     struct mailimf_group * group);
+static int mailimf_cache_mailbox_list_write(MMAPString * mmapstr,
+					    size_t * index,
+					    struct mailimf_mailbox_list * mb_list);
+static int mailimf_cache_mailbox_write(MMAPString * mmapstr, size_t * index,
+				       struct mailimf_mailbox * mb);
+
+
+static int mailimf_cache_field_read(MMAPString * mmapstr, size_t * index,
+				    struct mailimf_field ** result);
+static int mailimf_cache_orig_date_read(MMAPString * mmapstr, size_t * index,
+					struct mailimf_orig_date ** result);
+static int mailimf_cache_date_time_read(MMAPString * mmapstr, size_t * index,
+					struct mailimf_date_time ** result);
+static int mailimf_cache_from_read(MMAPString * mmapstr, size_t * index,
+				   struct mailimf_from ** result);
+static int mailimf_cache_sender_read(MMAPString * mmapstr, size_t * index,
+				     struct mailimf_sender ** result);
+static int mailimf_cache_reply_to_read(MMAPString * mmapstr, size_t * index,
+				       struct mailimf_reply_to ** result);
+static int mailimf_cache_to_read(MMAPString * mmapstr, size_t * index,
+				 struct mailimf_to ** result);
+static int mailimf_cache_cc_read(MMAPString * mmapstr, size_t * index,
+				 struct mailimf_cc ** result);
+static int mailimf_cache_bcc_read(MMAPString * mmapstr, size_t * index,
+				  struct mailimf_bcc ** result);
+static int mailimf_cache_message_id_read(MMAPString * mmapstr, size_t * index,
+					 struct mailimf_message_id ** result);
+static int mailimf_cache_msg_id_list_read(MMAPString * mmapstr, size_t * index,
+					  clist ** result);
+static int
+mailimf_cache_in_reply_to_read(MMAPString * mmapstr, size_t * index,
+			       struct mailimf_in_reply_to ** result);
+
+static int mailimf_cache_references_read(MMAPString * mmapstr, size_t * index,
+					 struct mailimf_references ** result);
+static int mailimf_cache_subject_read(MMAPString * mmapstr, size_t * index,
+				      struct mailimf_subject ** result);
+static int mailimf_cache_address_list_read(MMAPString * mmapstr, size_t * index,
+					   struct mailimf_address_list ** result);
+static int mailimf_cache_address_read(MMAPString * mmapstr, size_t * index,
+				      struct mailimf_address ** result);
+static int mailimf_cache_group_read(MMAPString * mmapstr, size_t * index,
+				    struct mailimf_group ** result);
+static int
+mailimf_cache_mailbox_list_read(MMAPString * mmapstr, size_t * index,
+				struct mailimf_mailbox_list ** result);
+static int mailimf_cache_mailbox_read(MMAPString * mmapstr, size_t * index,
+				      struct mailimf_mailbox ** result);
+
+enum {
+  CACHE_NULL_POINTER = 0,
+  CACHE_NOT_NULL     = 1,
+};
+
+int mail_serialize_clear(MMAPString * mmapstr, size_t * index)
+{
+  if (mmap_string_set_size(mmapstr, 0) == NULL)
+    return MAIL_ERROR_MEMORY;
+
+  * index = 0;
+
+  return MAIL_NO_ERROR;
+}
+
+int mail_serialize_write(MMAPString * mmapstr, size_t * index,
+			 char * buf, size_t size)
+{
+  if (mmap_string_append_len(mmapstr, buf, size) == NULL)
+    return MAIL_ERROR_MEMORY;
+
+  * index = * index + size;
+
+  return MAIL_NO_ERROR;
+}
+
+int mail_serialize_read(MMAPString * mmapstr, size_t * index,
+			char * buf, size_t size)
+{
+  size_t cur_token;
+  
+  cur_token = * index;
+
+  if (cur_token + size > mmapstr->len)
+    return MAIL_ERROR_STREAM;
+
+  memcpy(buf, mmapstr->str + cur_token, size);
+  * index = cur_token + size;
+
+  return MAIL_NO_ERROR;
+}
+
+int mailimf_cache_int_write(MMAPString * mmapstr, size_t * index,
+			    uint32_t value)
+{
+  unsigned char ch;
+  int r;
+  int i;
+
+  for(i = 0 ; i < 4 ; i ++) {
+    ch = value % 256;
+
+    r = mail_serialize_write(mmapstr, index, &ch, 1);
+    if (r != MAIL_NO_ERROR)
+      return r;
+    value /= 256;
+  }
+
+  return MAIL_NO_ERROR;
+}
+
+int mailimf_cache_int_read(MMAPString * mmapstr, size_t * index,
+			   uint32_t * result)
+{
+  unsigned char ch;
+  uint32_t value;
+  int i;
+  int r;
+  
+  value = 0;
+  for(i = 0 ; i < 4 ; i ++) {
+    r = mail_serialize_read(mmapstr, index, &ch, 1);
+    if (r != MAIL_NO_ERROR)
+      return r;
+    value = value | ch << (i << 3);
+  }
+  
+  * result = value;
+
+  return MAIL_NO_ERROR;
+}
+
+
+int mailimf_cache_string_write(MMAPString * mmapstr, size_t * index,
+			       char * str, size_t length)
+{
+  int r;
+
+  if (str == NULL) {
+    r = mailimf_cache_int_write(mmapstr, index, CACHE_NULL_POINTER);
+    if (r != MAIL_NO_ERROR)
+      return r;
+  }
+  else {
+    r = mailimf_cache_int_write(mmapstr, index, CACHE_NOT_NULL);
+    if (r != MAIL_NO_ERROR)
+      return r;
+    
+    r = mailimf_cache_int_write(mmapstr, index, length);
+    if (r != MAIL_NO_ERROR)
+      return r;
+    
+    if (length != 0) {
+      r = mail_serialize_write(mmapstr, index, str, length);
+      if (r != MAIL_NO_ERROR)
+        return MAIL_ERROR_FILE;
+    }
+  }
+
+  return MAIL_NO_ERROR;
+}
+
+int mailimf_cache_string_read(MMAPString * mmapstr, size_t * index,
+			      char ** result)
+{
+  int r;
+  uint32_t length;
+  char * str;
+  uint32_t type;
+  
+  r = mailimf_cache_int_read(mmapstr, index, &type);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  if (type == CACHE_NULL_POINTER) {
+    str = NULL;
+  }
+  else {
+    r = mailimf_cache_int_read(mmapstr, index, &length);
+    if (r != MAIL_NO_ERROR)
+      return r;
+    
+    str = malloc(length + 1);
+    if (str == NULL)
+      return MAIL_ERROR_MEMORY;
+    
+    r = mail_serialize_read(mmapstr, index, str, length);
+    if (r != MAIL_NO_ERROR)
+      return MAIL_ERROR_FILE;
+    
+    str[length] = 0;
+  }
+
+  * result = str;
+
+  return MAIL_NO_ERROR;
+}
+
+int mailimf_cache_fields_write(MMAPString * mmapstr, size_t * index,
+			       struct mailimf_fields * fields)
+{
+  clistiter * cur;
+  int r;
+
+  r = mailimf_cache_int_write(mmapstr, index,
+      clist_count(fields->fld_list));
+  if (r != MAIL_NO_ERROR)
+    return r;
+  
+  for(cur = clist_begin(fields->fld_list) ; cur != NULL ;
+      cur = clist_next(cur)) {
+    r = mailimf_cache_field_write(mmapstr, index, clist_content(cur));
+    if (r != MAIL_NO_ERROR)
+      return r;
+  }
+
+  return MAIL_NO_ERROR;
+}
+
+int mailimf_cache_fields_read(MMAPString * mmapstr, size_t * index,
+			      struct mailimf_fields ** result)
+{
+  clist * list;
+  int r;
+  uint32_t count;
+  uint32_t i;
+  struct mailimf_fields * fields;
+  int res;
+
+  r = mailimf_cache_int_read(mmapstr, index, &count);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  list = clist_new();
+  if (list == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+
+  for(i = 0 ; i < count ; i++) {
+    struct mailimf_field * field;
+
+    r = mailimf_cache_field_read(mmapstr, index, &field);
+    if (r != MAIL_NO_ERROR) {
+      res = r;
+      goto free_list;
+    }
+
+    r = clist_append(list, field);
+    if (r < 0) {
+      mailimf_field_free(field);
+      res = MAIL_ERROR_MEMORY;
+      goto free_list;
+    }
+  }
+
+  fields = mailimf_fields_new(list);
+  if (fields == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto free_list;
+  }
+  
+  * result = fields;
+
+  return MAIL_NO_ERROR;
+
+ free_list:
+  clist_foreach(list, (clist_func) mailimf_field_free, NULL);
+  clist_free(list);
+ err:
+  return res;
+}
+
+
+static int mailimf_cache_field_write(MMAPString * mmapstr, size_t * index,
+				     struct mailimf_field * field)
+{
+  int r;
+  
+  r = mailimf_cache_int_write(mmapstr, index, field->fld_type);
+  if (r != MAIL_NO_ERROR)
+    return r;
+  
+  switch (field->fld_type) {
+  case MAILIMF_FIELD_ORIG_DATE:
+    r = mailimf_cache_orig_date_write(mmapstr, index,
+        field->fld_data.fld_orig_date);
+    break;
+  case MAILIMF_FIELD_FROM:
+    r = mailimf_cache_from_write(mmapstr, index,
+        field->fld_data.fld_from);
+    break;
+  case MAILIMF_FIELD_SENDER:
+    r = mailimf_cache_sender_write(mmapstr, index,
+        field->fld_data.fld_sender);
+    break;
+  case MAILIMF_FIELD_REPLY_TO:
+    r = mailimf_cache_reply_to_write(mmapstr, index,
+        field->fld_data.fld_reply_to);
+    break;
+  case MAILIMF_FIELD_TO:
+    r = mailimf_cache_to_write(mmapstr, index,
+        field->fld_data.fld_to);
+    break;
+  case MAILIMF_FIELD_CC:
+    r = mailimf_cache_cc_write(mmapstr, index,
+        field->fld_data.fld_cc);
+    break;
+  case MAILIMF_FIELD_BCC:
+    r = mailimf_cache_bcc_write(mmapstr, index,
+        field->fld_data.fld_bcc);
+    break;
+  case MAILIMF_FIELD_MESSAGE_ID:
+    r = mailimf_cache_message_id_write(mmapstr, index,
+        field->fld_data.fld_message_id);
+    break;
+  case MAILIMF_FIELD_IN_REPLY_TO:
+    r = mailimf_cache_in_reply_to_write(mmapstr, index,
+        field->fld_data.fld_in_reply_to);
+    break;
+  case MAILIMF_FIELD_REFERENCES:
+    r = mailimf_cache_references_write(mmapstr, index,
+        field->fld_data.fld_references);
+    break;
+  case MAILIMF_FIELD_SUBJECT:
+    r = mailimf_cache_subject_write(mmapstr, index,
+        field->fld_data.fld_subject);
+    break;
+  default:
+    r = 0;
+    break;
+  }
+
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  return MAIL_NO_ERROR;
+}
+
+
+static int mailimf_cache_field_read(MMAPString * mmapstr, size_t * index,
+				    struct mailimf_field ** result)
+{
+  int r;
+  uint32_t type;
+  struct mailimf_orig_date * orig_date;
+  struct mailimf_from * from;
+  struct mailimf_sender * sender;
+  struct mailimf_to * to;
+  struct mailimf_reply_to * reply_to;
+  struct mailimf_cc * cc;
+  struct mailimf_bcc * bcc;
+  struct mailimf_message_id * message_id;
+  struct mailimf_in_reply_to * in_reply_to;
+  struct mailimf_references * references;
+  struct mailimf_subject * subject;
+  struct mailimf_field * field;
+  int res;
+
+  orig_date = NULL;
+  from = NULL;
+  sender = NULL;
+  to = NULL;
+  reply_to = NULL;
+  cc = NULL;
+  bcc = NULL;
+  message_id = NULL;
+  in_reply_to = NULL;
+  references = NULL;
+  subject = NULL;
+  field = NULL;
+
+  r = mailimf_cache_int_read(mmapstr, index, &type);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  switch (type) {
+  case MAILIMF_FIELD_ORIG_DATE:
+    r = mailimf_cache_orig_date_read(mmapstr, index, &orig_date);
+    break;
+  case MAILIMF_FIELD_FROM:
+    r = mailimf_cache_from_read(mmapstr, index, &from);
+    break;
+  case MAILIMF_FIELD_SENDER:
+    r = mailimf_cache_sender_read(mmapstr, index, &sender);
+    break;
+  case MAILIMF_FIELD_REPLY_TO:
+    r = mailimf_cache_reply_to_read(mmapstr, index, &reply_to);
+    break;
+  case MAILIMF_FIELD_TO:
+    r = mailimf_cache_to_read(mmapstr, index, &to);
+    break;
+  case MAILIMF_FIELD_CC:
+    r = mailimf_cache_cc_read(mmapstr, index, &cc);
+    break;
+  case MAILIMF_FIELD_BCC:
+    r = mailimf_cache_bcc_read(mmapstr, index, &bcc);
+    break;
+  case MAILIMF_FIELD_MESSAGE_ID:
+    r = mailimf_cache_message_id_read(mmapstr, index, &message_id);
+    break;
+  case MAILIMF_FIELD_IN_REPLY_TO:
+    r = mailimf_cache_in_reply_to_read(mmapstr, index, &in_reply_to);
+    break;
+  case MAILIMF_FIELD_REFERENCES:
+    r = mailimf_cache_references_read(mmapstr, index, &references);
+    break;
+  case MAILIMF_FIELD_SUBJECT:
+    r = mailimf_cache_subject_read(mmapstr, index, &subject);
+    break;
+  default:
+    r = MAIL_ERROR_INVAL;
+    break;
+  }
+
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto free;
+  }
+
+  field = mailimf_field_new(type, NULL, NULL, NULL, NULL, NULL,
+      NULL, NULL, NULL, orig_date, from, sender, reply_to,
+      to, cc, bcc, message_id,
+      in_reply_to, references,
+      subject, NULL, NULL, NULL);
+  if (field == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto free;
+  }
+
+  * result = field;
+
+  return MAIL_NO_ERROR;
+
+ free:
+  if (orig_date != NULL)
+    mailimf_orig_date_free(orig_date);
+  if (from != NULL)
+    mailimf_from_free(from);
+  if (sender != NULL)
+    mailimf_sender_free(sender);
+  if (reply_to != NULL)
+    mailimf_reply_to_free(reply_to);
+  if (to != NULL)
+    mailimf_to_free(to);
+  if (cc != NULL)
+    mailimf_cc_free(cc);
+  if (bcc != NULL)
+    mailimf_bcc_free(bcc);
+  if (message_id != NULL)
+    mailimf_message_id_free(message_id);
+  if (in_reply_to != NULL)
+    mailimf_in_reply_to_free(in_reply_to);
+  if (references != NULL)
+    mailimf_references_free(references);
+  if (subject != NULL)
+    mailimf_subject_free(subject);
+ err:
+  return res;
+}
+
+static int mailimf_cache_orig_date_write(MMAPString * mmapstr, size_t * index,
+					 struct mailimf_orig_date * date)
+{
+  return mailimf_cache_date_time_write(mmapstr, index, date->dt_date_time);
+}
+
+static int mailimf_cache_orig_date_read(MMAPString * mmapstr, size_t * index,
+					struct mailimf_orig_date ** result)
+{
+  int r;
+  struct mailimf_date_time * date_time;
+  struct mailimf_orig_date * orig_date;
+
+  r = mailimf_cache_date_time_read(mmapstr, index, &date_time);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  orig_date = mailimf_orig_date_new(date_time);
+  if (orig_date == NULL) {
+    mailimf_date_time_free(date_time);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = orig_date;
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_date_time_write(MMAPString * mmapstr, size_t * index,
+					 struct mailimf_date_time * date_time)
+{
+  int r;
+
+  r = mailimf_cache_int_write(mmapstr, index, date_time->dt_day);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_write(mmapstr, index, date_time->dt_month);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_write(mmapstr, index, date_time->dt_year);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_write(mmapstr, index, date_time->dt_hour);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_write(mmapstr, index, date_time->dt_min);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_write(mmapstr, index, date_time->dt_sec);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_write(mmapstr, index, date_time->dt_zone);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_date_time_read(MMAPString * mmapstr, size_t * index,
+					struct mailimf_date_time ** result)
+{
+  int r;
+  uint32_t day;
+  uint32_t month;
+  uint32_t year;
+  uint32_t hour;
+  uint32_t min;
+  uint32_t sec;
+  uint32_t zone;
+  struct mailimf_date_time * date_time;
+
+  r = mailimf_cache_int_read(mmapstr, index, &day);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_read(mmapstr, index, &month);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_read(mmapstr, index, &year);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_read(mmapstr, index, &hour);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_read(mmapstr, index, &min);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_read(mmapstr, index, &sec);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_int_read(mmapstr, index, &zone);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  date_time = mailimf_date_time_new(day, month, year, hour, min, sec, zone);
+  if (date_time == NULL)
+    return MAIL_ERROR_MEMORY;
+
+  * result = date_time;
+
+  return MAIL_NO_ERROR;
+  
+}
+
+
+static int mailimf_cache_from_write(MMAPString * mmapstr, size_t * index,
+				    struct mailimf_from * from)
+{
+  return mailimf_cache_mailbox_list_write(mmapstr, index, from->frm_mb_list);
+}
+
+static int mailimf_cache_from_read(MMAPString * mmapstr, size_t * index,
+				   struct mailimf_from ** result)
+{
+  struct mailimf_mailbox_list * mb_list;
+  struct mailimf_from * from;
+  int r;
+  
+  r = mailimf_cache_mailbox_list_read(mmapstr, index, &mb_list);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  from = mailimf_from_new(mb_list);
+  if (from == NULL) {
+    mailimf_mailbox_list_free(mb_list);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = from;
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_sender_write(MMAPString * mmapstr, size_t * index,
+				      struct mailimf_sender * sender)
+{
+  return mailimf_cache_mailbox_write(mmapstr, index, sender->snd_mb);
+}
+
+static int mailimf_cache_sender_read(MMAPString * mmapstr, size_t * index,
+				     struct mailimf_sender ** result)
+{
+  int r;
+  struct mailimf_mailbox * mb;
+  struct mailimf_sender * sender;
+
+  r = mailimf_cache_mailbox_read(mmapstr, index, &mb);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  sender = mailimf_sender_new(mb);
+  if (sender == NULL) {
+    mailimf_mailbox_free(mb);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = sender;
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_reply_to_write(MMAPString * mmapstr, size_t * index,
+					struct mailimf_reply_to * reply_to)
+{
+  return mailimf_cache_address_list_write(mmapstr, index,
+      reply_to->rt_addr_list);
+}
+
+static int mailimf_cache_reply_to_read(MMAPString * mmapstr, size_t * index,
+				       struct mailimf_reply_to ** result)
+{
+  int r;
+  struct mailimf_address_list * addr_list;
+  struct mailimf_reply_to * reply_to;
+
+  r = mailimf_cache_address_list_read(mmapstr, index, &addr_list);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  reply_to = mailimf_reply_to_new(addr_list);
+  if (reply_to == NULL) {
+    mailimf_address_list_free(addr_list);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = reply_to;
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_to_write(MMAPString * mmapstr, size_t * index,
+				  struct mailimf_to * to)
+{
+  return mailimf_cache_address_list_write(mmapstr, index, to->to_addr_list);
+}
+
+static int mailimf_cache_to_read(MMAPString * mmapstr, size_t * index,
+				 struct mailimf_to ** result)
+{
+  int r;
+  struct mailimf_address_list * addr_list;
+  struct mailimf_to * to;
+
+  r = mailimf_cache_address_list_read(mmapstr, index, &addr_list);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  to = mailimf_to_new(addr_list);
+  if (to == NULL) {
+    mailimf_address_list_free(addr_list);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = to;
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_cc_write(MMAPString * mmapstr, size_t * index,
+				  struct mailimf_cc * cc)
+{
+  return mailimf_cache_address_list_write(mmapstr, index, cc->cc_addr_list);
+}
+
+static int mailimf_cache_cc_read(MMAPString * mmapstr, size_t * index,
+    struct mailimf_cc ** result)
+{
+  int r;
+  struct mailimf_address_list * addr_list;
+  struct mailimf_cc * cc;
+
+  r = mailimf_cache_address_list_read(mmapstr, index, &addr_list);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  cc = mailimf_cc_new(addr_list);
+  if (cc == NULL) {
+    mailimf_address_list_free(addr_list);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = cc;
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_bcc_write(MMAPString * mmapstr, size_t * index,
+				   struct mailimf_bcc * bcc)
+{
+  return mailimf_cache_address_list_write(mmapstr, index, bcc->bcc_addr_list);
+}
+
+static int mailimf_cache_bcc_read(MMAPString * mmapstr, size_t * index,
+				  struct mailimf_bcc ** result)
+{
+  int r;
+  struct mailimf_address_list * addr_list;
+  struct mailimf_bcc * bcc;
+
+  r = mailimf_cache_address_list_read(mmapstr, index, &addr_list);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  bcc = mailimf_bcc_new(addr_list);
+  if (bcc == NULL) {
+    mailimf_address_list_free(addr_list);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = bcc;
+
+  return MAIL_NO_ERROR;
+}
+
+static int
+mailimf_cache_message_id_write(MMAPString * mmapstr, size_t * index,
+			       struct mailimf_message_id * message_id)
+{
+  return mailimf_cache_string_write(mmapstr, index,
+      message_id->mid_value, strlen(message_id->mid_value));
+}
+
+static int mailimf_cache_message_id_read(MMAPString * mmapstr, size_t * index,
+					 struct mailimf_message_id ** result)
+{
+  struct mailimf_message_id * message_id;
+  char * str;
+  int r;
+
+  r = mailimf_cache_string_read(mmapstr, index, &str);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  message_id = mailimf_message_id_new(str);
+  if (message_id == NULL) {
+    free(str);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = message_id;
+  
+  return MAIL_NO_ERROR;
+}
+
+static int
+mailimf_cache_msg_id_list_write(MMAPString * mmapstr, size_t * index,
+				clist * list)
+{
+  clistiter * cur;
+  int r;
+
+  r = mailimf_cache_int_write(mmapstr, index, clist_count(list));
+  if (r != MAIL_NO_ERROR)
+    return r;
+  
+  for(cur = clist_begin(list) ; cur != NULL ; cur = clist_next(cur)) {
+    char * msgid;
+
+    msgid = clist_content(cur);
+
+    r = mailimf_cache_string_write(mmapstr, index, msgid, strlen(msgid));
+    if (r != MAIL_NO_ERROR)
+      return r;
+  }
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_msg_id_list_read(MMAPString * mmapstr, size_t * index,
+					  clist ** result)
+{
+  clist * list;
+  int r;
+  uint32_t count;
+  uint32_t i;
+  int res;
+
+  r = mailimf_cache_int_read(mmapstr, index, &count);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+  
+  list = clist_new();
+  if (list == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+
+  for(i = 0 ; i < count ; i++) {
+    char * msgid;
+    
+    r = mailimf_cache_string_read(mmapstr, index, &msgid);
+    if (r != MAIL_NO_ERROR) {
+      res = r;
+      goto err;
+    }
+
+    r = clist_append(list, msgid);
+    if (r < 0) {
+      free(msgid);
+      res = MAIL_ERROR_MEMORY;
+      goto free_list;
+    }
+  }
+
+  * result = list;
+
+  return MAIL_NO_ERROR;
+
+ free_list:
+  clist_foreach(list, (clist_func) free, NULL);
+  clist_free(list);
+ err:
+  return res;
+}
+
+static int
+mailimf_cache_in_reply_to_write(MMAPString * mmapstr, size_t * index,
+				struct mailimf_in_reply_to * in_reply_to)
+{
+  return mailimf_cache_msg_id_list_write(mmapstr, index,
+      in_reply_to->mid_list);
+}
+
+static int mailimf_cache_in_reply_to_read(MMAPString * mmapstr, size_t * index,
+					  struct mailimf_in_reply_to ** result)
+{
+  int r;
+  clist * msg_id_list;
+  struct mailimf_in_reply_to * in_reply_to;
+
+  r = mailimf_cache_msg_id_list_read(mmapstr, index, &msg_id_list);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  in_reply_to = mailimf_in_reply_to_new(msg_id_list);
+  if (in_reply_to == NULL) {
+    clist_foreach(msg_id_list, (clist_func) free, NULL);
+    clist_free(msg_id_list);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = in_reply_to;
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_references_write(MMAPString * mmapstr, size_t * index,
+					  struct mailimf_references * references)
+{
+  return mailimf_cache_msg_id_list_write(mmapstr, index,
+      references->mid_list);
+}
+
+static int mailimf_cache_references_read(MMAPString * mmapstr, size_t * index,
+					 struct mailimf_references ** result)
+{
+  int r;
+  clist * msg_id_list;
+  struct mailimf_references * references;
+
+  r = mailimf_cache_msg_id_list_read(mmapstr, index, &msg_id_list);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  references = mailimf_references_new(msg_id_list);
+  if (references == NULL) {
+    clist_foreach(msg_id_list, (clist_func) free, NULL);
+    clist_free(msg_id_list);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = references;
+
+  return MAIL_NO_ERROR;
+}
+
+
+static int mailimf_cache_subject_write(MMAPString * mmapstr, size_t * index,
+				       struct mailimf_subject * subject)
+{
+  return mailimf_cache_string_write(mmapstr, index,
+      subject->sbj_value, strlen(subject->sbj_value));
+}
+
+static int mailimf_cache_subject_read(MMAPString * mmapstr, size_t * index,
+				      struct mailimf_subject ** result)
+{
+  char * str;
+  struct mailimf_subject * subject;
+  int r;
+
+  r = mailimf_cache_string_read(mmapstr, index, &str);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  if (str == NULL) {
+    str = strdup("");
+    if (str == NULL)
+      return MAIL_ERROR_MEMORY;
+  }
+
+  subject = mailimf_subject_new(str);
+  if (subject == NULL) {
+    free(str);
+    return MAIL_ERROR_MEMORY;
+  }
+
+  * result = subject;
+
+  return MAIL_NO_ERROR;
+}
+
+
+static int
+mailimf_cache_address_list_write(MMAPString * mmapstr, size_t * index,
+				 struct mailimf_address_list * addr_list)
+{
+  clistiter * cur;
+  int r;
+
+  if (addr_list == NULL) {
+    r = mailimf_cache_int_write(mmapstr, index, CACHE_NULL_POINTER);
+    if (r != MAIL_NO_ERROR)
+      return r;
+  }
+  else {
+    r = mailimf_cache_int_write(mmapstr, index, CACHE_NOT_NULL);
+    if (r != MAIL_NO_ERROR)
+      return r;
+    
+    r = mailimf_cache_int_write(mmapstr, index,
+        clist_count(addr_list->ad_list));
+    if (r != MAIL_NO_ERROR)
+      return r;
+    
+    for(cur = clist_begin(addr_list->ad_list) ; cur != NULL ;
+        cur = clist_next(cur)) {
+      struct mailimf_address * addr;
+      
+      addr = clist_content(cur);
+      
+      r = mailimf_cache_address_write(mmapstr, index, addr);
+      if (r != MAIL_NO_ERROR)
+	return r;
+    }
+  }
+
+  return MAIL_NO_ERROR;
+}
+
+static int
+mailimf_cache_address_list_read(MMAPString * mmapstr, size_t * index,
+				struct mailimf_address_list ** result)
+{
+  struct mailimf_address_list * addr_list;
+  uint32_t count;
+  uint32_t i;
+  int r;
+  clist * list;
+  int res;
+  uint32_t type;
+  
+  r = mailimf_cache_int_read(mmapstr, index, &type);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+  
+  if (type == CACHE_NULL_POINTER) {
+    * result = NULL;
+    return MAIL_NO_ERROR;
+  }
+  
+  r = mailimf_cache_int_read(mmapstr, index, &count);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  list = clist_new();
+  if (list == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+
+  for(i = 0 ; i < count ; i++) {
+    struct mailimf_address * addr;
+    
+    r = mailimf_cache_address_read(mmapstr, index, &addr);
+    if (r != MAIL_NO_ERROR) {
+      res = r;
+      goto free_list;
+    }
+
+    r = clist_append(list, addr);
+    if (r < 0) {
+      mailimf_address_free(addr);
+      res = MAIL_ERROR_MEMORY;
+      goto free_list;
+    }
+  }
+
+  addr_list = mailimf_address_list_new(list);
+  if (addr_list == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto free_list;
+  }
+
+  * result = addr_list;
+
+  return MAIL_NO_ERROR;
+
+ free_list:
+  clist_foreach(list, (clist_func) mailimf_address_free, NULL);
+  clist_free(list);
+ err:
+  return res;
+}
+
+static int mailimf_cache_address_write(MMAPString * mmapstr, size_t * index,
+				       struct mailimf_address * addr)
+{
+  int r;
+
+  r = mailimf_cache_int_write(mmapstr, index, addr->ad_type);
+  if (r != MAIL_NO_ERROR)
+    return r;
+  
+  switch(addr->ad_type) {
+  case MAILIMF_ADDRESS_MAILBOX:
+    r = mailimf_cache_mailbox_write(mmapstr, index, addr->ad_data.ad_mailbox);
+    if (r != MAIL_NO_ERROR)
+      return r;
+
+    break;
+
+  case MAILIMF_ADDRESS_GROUP:
+    r = mailimf_cache_group_write(mmapstr, index, addr->ad_data.ad_group);
+    if (r != MAIL_NO_ERROR)
+      return r;
+    
+    break;
+  }
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_address_read(MMAPString * mmapstr, size_t * index,
+				      struct mailimf_address ** result)
+{
+  uint32_t type;
+  int r;
+  struct mailimf_mailbox * mailbox;
+  struct mailimf_group * group;
+  struct mailimf_address * addr;
+
+  r = mailimf_cache_int_read(mmapstr, index, &type);
+  if (r != MAIL_NO_ERROR)
+    return r;
+  
+  mailbox = NULL;
+  group = NULL;
+
+  switch (type) {
+  case MAILIMF_ADDRESS_MAILBOX:
+    r = mailimf_cache_mailbox_read(mmapstr, index, &mailbox);
+    if (r != MAIL_NO_ERROR)
+      return r;
+
+    break;
+
+  case MAILIMF_ADDRESS_GROUP:
+    r = mailimf_cache_group_read(mmapstr, index, &group);
+    if (r != MAIL_NO_ERROR)
+      return r;
+    
+    break;
+  }
+
+  addr = mailimf_address_new(type, mailbox, group);
+  if (addr == NULL)
+    goto free;
+
+  * result = addr;
+
+  return MAIL_NO_ERROR;
+
+ free:
+  if (mailbox != NULL)
+    mailimf_mailbox_free(mailbox);
+  if (group != NULL)
+    mailimf_group_free(group);
+  return MAIL_ERROR_MEMORY;
+}
+
+static int mailimf_cache_group_write(MMAPString * mmapstr, size_t * index,
+				     struct mailimf_group * group)
+{
+  int r;
+
+  r = mailimf_cache_string_write(mmapstr, index, group->grp_display_name,
+			   strlen(group->grp_display_name));
+  if (r != MAIL_NO_ERROR)
+    return r;
+  
+  r = mailimf_cache_mailbox_list_write(mmapstr, index, group->grp_mb_list);
+  if (r != MAIL_NO_ERROR)
+    return r;
+  
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_group_read(MMAPString * mmapstr, size_t * index,
+				    struct mailimf_group ** result)
+{
+  int r;
+  char * display_name;
+  struct mailimf_mailbox_list * mb_list;
+  struct mailimf_group * group;
+  int res;
+
+  r = mailimf_cache_string_read(mmapstr, index, &display_name);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  r = mailimf_cache_mailbox_list_read(mmapstr, index, &mb_list);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto free_dsp_name;
+  }
+
+  group = mailimf_group_new(display_name, mb_list);
+  if (group == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto free_mb_list;
+  }
+
+  * result = group;
+
+  return MAIL_NO_ERROR;
+
+ free_mb_list:
+  mailimf_mailbox_list_free(mb_list);
+ free_dsp_name:
+  free(display_name);
+ err:
+  return res;
+}
+
+static int
+mailimf_cache_mailbox_list_write(MMAPString * mmapstr, size_t * index,
+				 struct mailimf_mailbox_list * mb_list)
+{
+  clistiter * cur;
+  int r;
+
+  if (mb_list == NULL) {
+    r = mailimf_cache_int_write(mmapstr, index, CACHE_NULL_POINTER);
+    if (r != MAIL_NO_ERROR)
+      return r;
+  }
+  else {
+    r = mailimf_cache_int_write(mmapstr, index, CACHE_NOT_NULL);
+    if (r != MAIL_NO_ERROR)
+      return r;
+    
+    r = mailimf_cache_int_write(mmapstr, index,
+        clist_count(mb_list->mb_list));
+    if (r != MAIL_NO_ERROR)
+      return r;
+    
+    for(cur = clist_begin(mb_list->mb_list) ; cur != NULL ;
+        cur = clist_next(cur)) {
+      struct mailimf_mailbox * mb;
+      
+      mb = clist_content(cur);
+      
+      r = mailimf_cache_mailbox_write(mmapstr, index, mb);
+      if (r != MAIL_NO_ERROR)
+        return r;
+    }
+  }
+
+  return MAIL_NO_ERROR;
+}
+
+static int
+mailimf_cache_mailbox_list_read(MMAPString * mmapstr, size_t * index,
+				struct mailimf_mailbox_list ** result)
+{
+  clist * list;
+  int r;
+  uint32_t count;
+  uint32_t i;
+  struct mailimf_mailbox_list * mb_list;
+  int res;
+  uint32_t type;
+  
+  r = mailimf_cache_int_read(mmapstr, index, &type);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+  
+  if (type == CACHE_NULL_POINTER) {
+    * result = NULL;
+    return MAIL_NO_ERROR;
+  }
+  
+  r = mailimf_cache_int_read(mmapstr, index, &count);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto err;
+  }
+
+  list = clist_new();
+  if (list == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+
+  for(i = 0 ; i < count ; i++) {
+    struct mailimf_mailbox * mb;
+    
+    r = mailimf_cache_mailbox_read(mmapstr, index, &mb);
+    if (r != MAIL_NO_ERROR) {
+      res = r;
+      goto free_list;
+    }
+
+    r = clist_append(list, mb);
+    if (r < 0) {
+      mailimf_mailbox_free(mb);
+      res = MAIL_ERROR_MEMORY;
+      goto free_list;
+    }
+  }
+
+  mb_list = mailimf_mailbox_list_new(list);
+  if (mb_list == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto free_list;
+  }
+
+  * result = mb_list;
+
+  return MAIL_NO_ERROR;
+
+ free_list:
+  clist_foreach(list, (clist_func) mailimf_mailbox_free, NULL);
+  clist_free(list);
+ err:
+  return res;
+}
+
+static int mailimf_cache_mailbox_write(MMAPString * mmapstr, size_t * index,
+				       struct mailimf_mailbox * mb)
+{
+  int r;
+
+  if (mb->mb_display_name) {
+    r = mailimf_cache_string_write(mmapstr, index, 
+        mb->mb_display_name, strlen(mb->mb_display_name));
+    if (r != MAIL_NO_ERROR)
+      return r;
+  }
+  else {
+    r = mailimf_cache_string_write(mmapstr, index, NULL, 0);
+    if (r != MAIL_NO_ERROR)
+      return r;
+  }
+
+  r = mailimf_cache_string_write(mmapstr, index,
+      mb->mb_addr_spec, strlen(mb->mb_addr_spec));
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  return MAIL_NO_ERROR;
+}
+
+static int mailimf_cache_mailbox_read(MMAPString * mmapstr, size_t * index,
+				      struct mailimf_mailbox ** result)
+{
+  int r;
+  char * dsp_name;
+  char * addr_spec;
+  struct mailimf_mailbox * mb;
+
+  dsp_name = NULL;
+
+  r = mailimf_cache_string_read(mmapstr, index, &dsp_name);
+  if (r != MAIL_NO_ERROR)
+    return r;
+
+  r = mailimf_cache_string_read(mmapstr, index, &addr_spec);
+  if (r != MAIL_NO_ERROR)
+    goto free_dsp_name;
+
+  mb = mailimf_mailbox_new(dsp_name, addr_spec);
+  if (mb == NULL)
+    goto free_addr;
+
+  * result = mb;
+
+  return MAIL_NO_ERROR;
+
+ free_addr:
+  free(addr_spec);
+ free_dsp_name:
+  if (dsp_name != NULL)
+    free(dsp_name);
+  return MAIL_ERROR_MEMORY;
+}
diff --git a/libetpan/src/driver/tools/imfcache.h b/libetpan/src/driver/tools/imfcache.h
new file mode 100644
index 0000000..f054a12
--- a/dev/null
+++ b/libetpan/src/driver/tools/imfcache.h
@@ -0,0 +1,75 @@
+/*
+ * libEtPan! -- a mail stuff library
+ *
+ * Copyright (C) 2001, 2005 - DINH Viet Hoa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the libEtPan! project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * $Id$
+ */
+
+#ifndef IMFCACHE_H
+
+#define IMFCACHE_H
+
+#include <stdio.h>
+#include "mailimf.h"
+#include "maildriver_types.h"
+#include "mmapstring.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+int mail_serialize_clear(MMAPString * mmapstr, size_t * index);
+
+int mail_serialize_write(MMAPString * mmapstr, size_t * index,
+			 char * buf, size_t size);
+
+int mail_serialize_read(MMAPString * mmapstr, size_t * index,
+			char * buf, size_t size);
+
+int mailimf_cache_int_write(MMAPString * mmapstr, size_t * index,
+			    uint32_t value);
+int mailimf_cache_string_write(MMAPString * mmapstr, size_t * index,
+			       char * str, size_t length);
+int mailimf_cache_int_read(MMAPString * mmapstr, size_t * index,
+			   uint32_t * result);
+int mailimf_cache_string_read(MMAPString * mmapstr, size_t * index,
+			      char ** result);
+
+int mailimf_cache_fields_write(MMAPString * mmapstr, size_t * index,
+			       struct mailimf_fields * fields);
+int mailimf_cache_fields_read(MMAPString * mmapstr, size_t * index,
+			      struct mailimf_fields ** result);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/libetpan/src/driver/tools/mailthread.c b/libetpan/src/driver/tools/mailthread.c
new file mode 100644
index 0000000..32f73cd
--- a/dev/null
+++ b/libetpan/src/driver/tools/mailthread.c
@@ -0,0 +1,1742 @@
+/*
+ * libEtPan! -- a mail stuff library
+ *
+ * Copyright (C) 2001, 2005 - DINH Viet Hoa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the libEtPan! project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * $Id$
+ */
+
+#include "mailthread.h"
+#include "mailthread_types.h"
+
+#include <string.h>
+#include <time.h>
+#include <stdlib.h>
+#include <ctype.h>
+
+#include "mail.h"
+#include "chash.h"
+#include "carray.h"
+#include "clist.h"
+#include "mailmessage.h"
+
+static inline char * get_msg_id(mailmessage * msg)
+{
+  if (msg->msg_single_fields.fld_message_id != NULL)
+    return msg->msg_single_fields.fld_message_id->mid_value;
+  else
+    return NULL;
+}
+
+static inline clist * get_ref(mailmessage * msg)
+{
+  if (msg->msg_single_fields.fld_references != NULL)
+    return msg->msg_single_fields.fld_references->mid_list;
+  else
+    return NULL;
+}
+
+static inline clist * get_in_reply_to(mailmessage * msg)
+{
+  if (msg->msg_single_fields.fld_in_reply_to != NULL)
+    return msg->msg_single_fields.fld_in_reply_to->mid_list;
+  else
+    return NULL;
+}
+
+static inline int skip_subj_blob(char * subj, size_t * begin,
+				 size_t length)
+{
+  /* subj-blob       = "[" *BLOBCHAR "]" *WSP */
+  size_t cur_token;
+
+  cur_token = * begin;
+
+  if (subj[cur_token] != '[')
+    return FALSE;
+
+  cur_token ++;
+
+  while (1) {
+    if (cur_token >= length)
+      return FALSE;
+
+    if (subj[cur_token] == '[')
+      return FALSE;
+
+    if (subj[cur_token] == ']')
+      break;
+
+    cur_token ++;
+  }
+
+  cur_token ++;
+
+  while (1) {
+    if (cur_token >= length)
+      break;
+
+    if (subj[cur_token] != ' ')
+      break;
+
+    cur_token ++;
+  }
+
+  * begin = cur_token;
+
+  return TRUE;
+}
+
+static inline int skip_subj_refwd(char * subj, size_t * begin,
+				  size_t length)
+{
+  /* subj-refwd      = ("re" / ("fw" ["d"])) *WSP [subj-blob] ":" */
+  size_t cur_token;
+  int prefix;
+
+  cur_token = * begin;
+
+  prefix = FALSE;
+  if (length >= 3) {
+    if (strncasecmp(subj + cur_token, "fwd", 3) == 0) {
+      cur_token += 3;
+      prefix = TRUE;
+    }
+  }
+  if (!prefix) {
+    if (length >= 2) {
+      if (strncasecmp(subj + cur_token, "fw", 2) == 0) {
+	cur_token += 2;
+	prefix = TRUE;
+      }
+      else if (strncasecmp(subj + cur_token, "re", 2) == 0) {
+	cur_token += 2;
+	prefix = TRUE;
+      }
+    }
+  }
+
+  if (!prefix)
+    return FALSE;
+
+  while (1) {
+    if (cur_token >= length)
+      break;
+      
+    if (subj[cur_token] != ' ')
+      break;
+
+    cur_token ++;
+  }
+  
+  skip_subj_blob(subj, &cur_token, length);
+
+  if (subj[cur_token] != ':')
+    return FALSE;
+
+  cur_token ++;
+
+  * begin = cur_token;
+
+  return TRUE;
+}
+
+static inline int skip_subj_leader(struct mailmessage_tree * tree,
+				   char * subj, size_t * begin,
+				   size_t length)
+{
+  size_t cur_token;
+
+  cur_token = * begin;
+
+  /* subj-leader     = (*subj-blob subj-refwd) / WSP */
+  
+  if (subj[cur_token] == ' ') {
+    cur_token ++;
+  }
+  else {
+    while (cur_token < length) {
+      if (!skip_subj_blob(subj, &cur_token, length))
+	break;
+    }
+    if (!skip_subj_refwd(subj, &cur_token, length))
+      return FALSE;
+    tree->node_is_reply = TRUE;
+  }
+
+  * begin = cur_token;
+
+  return TRUE;
+}
+
+
+static char * extract_subject(char * default_from,
+    struct mailmessage_tree * tree,
+    char * str)
+{
+  char * subj;
+  char * cur;
+  char * write_pos;
+  size_t len;
+  size_t begin;
+
+  char * decoded;
+  size_t cur_token;
+
+  int do_repeat_5;
+  int do_repeat_6;
+  int r;
+
+  /*
+    (1) Convert any RFC 2047 encoded-words in the subject to
+    UTF-8.
+  */
+
+  decoded = NULL;
+
+  cur_token = 0;
+  r = mailmime_encoded_phrase_parse(default_from, str, strlen(str),
+				    &cur_token, "utf-8",
+				    &decoded);
+
+  if (r == MAILIMF_NO_ERROR) {
+    subj = decoded;
+  }
+  else
+    subj = strdup(str);
+
+  len = strlen(subj);
+
+  /*
+    Convert all tabs and continuations to space.
+    Convert all multiple spaces to a single space.
+  */
+
+  cur = subj;
+  write_pos = subj;
+  while (* cur != '\0') {
+    int cont;
+
+    switch (* cur) {
+    case '\t':
+    case '\r':
+    case '\n':
+      cont = TRUE;
+
+      cur ++;
+      while (* cur && cont) {
+	switch (* cur) {
+	case '\t':
+	case '\r':
+	case '\n':
+	  cont = TRUE;
+	  break;
+	default:
+	  cont = FALSE;
+	  break;
+	}
+	cur ++;
+      }
+      
+      * write_pos = ' ';
+      write_pos ++;
+
+      break;
+      
+    default:
+      * write_pos = * cur;
+      write_pos ++;
+
+      cur ++;
+
+      break;
+    }
+  }
+  * write_pos = '\0';
+
+  begin = 0;
+
+  do {
+    do_repeat_6 = FALSE;
+
+    /*
+      (2) Remove all trailing text of the subject that matches
+      the subj-trailer ABNF, repeat until no more matches are
+      possible.
+    */
+
+    while (len > 0) {
+      int chg;
+
+      chg = FALSE;
+
+      /* subj-trailer    = "(fwd)" / WSP */
+      if (subj[len - 1] == ' ') {
+	subj[len - 1] = '\0';
+	len --;
+      }
+      else {
+	if (len < 5)
+	  break;
+
+	if (strncasecmp(subj + len - 5, "(fwd)", 5) != 0)
+	  break;
+
+	subj[len - 5] = '\0';
+	len -= 5;
+	tree->node_is_reply = TRUE;
+      }
+    }
+
+    do {
+      size_t saved_begin;
+
+      do_repeat_5 = FALSE;
+
+      /*
+	(3) Remove all prefix text of the subject that matches the
+	subj-leader ABNF.
+      */
+    
+      if (skip_subj_leader(tree, subj, &begin, len))
+	do_repeat_5 = TRUE;
+
+      /*
+	(4) If there is prefix text of the subject that matches the
+	subj-blob ABNF, and removing that prefix leaves a non-empty
+	subj-base, then remove the prefix text.
+      */
+    
+      saved_begin = begin;
+      if (skip_subj_blob(subj, &begin, len)) {
+	if (begin == len) {
+	  /* this will leave a empty subject base */
+	  begin = saved_begin;
+	}
+	else
+	  do_repeat_5 = TRUE;
+      }
+
+      /*
+	(5) Repeat (3) and (4) until no matches remain.
+	Note: it is possible to defer step (2) until step (6),
+	but this requires checking for subj-trailer in step (4).
+      */
+    
+    }
+    while (do_repeat_5);
+
+    /*
+      (6) If the resulting text begins with the subj-fwd-hdr ABNF
+      and ends with the subj-fwd-trl ABNF, remove the
+      subj-fwd-hdr and subj-fwd-trl and repeat from step (2).
+    */
+
+    if (len >= 5) {
+      size_t saved_begin;
+
+      saved_begin = begin;
+      if (strncasecmp(subj + begin, "[fwd:", 5) == 0) {
+	begin += 5;
+	
+	if (subj[len - 1] != ']')
+	  saved_begin = begin;
+	else {
+	  tree->node_is_reply = TRUE;
+
+	  subj[len - 1] = '\0';
+	  len --;
+	  do_repeat_6 = TRUE;
+	}
+      }
+    }
+
+  }
+  while (do_repeat_6);
+
+  /*
+    (7) The resulting text is the "base subject" used in
+    threading.
+  */
+
+  /* convert to upper case */
+
+  cur = subj + begin;
+  write_pos = subj;
+
+  while (* cur != '\0') {
+    * write_pos = (char) toupper((unsigned char) * cur);
+    cur ++;
+    write_pos ++;
+  }
+  * write_pos = '\0';
+
+  return subj;
+}
+
+static int get_extracted_subject(char * default_from,
+    struct mailmessage_tree * tree,
+    char ** result)
+{
+  if (tree->node_msg->msg_single_fields.fld_subject != NULL) {
+    char * subj;
+
+    subj = extract_subject(default_from,
+        tree, tree->node_msg->msg_single_fields.fld_subject->sbj_value);
+    if (subj == NULL)
+      return MAIL_ERROR_MEMORY;
+    
+    * result = subj;
+    
+    return MAIL_NO_ERROR;
+  }
+
+  return MAIL_ERROR_SUBJECT_NOT_FOUND;
+}
+
+static int get_thread_subject(char * default_from,
+    struct mailmessage_tree * tree,
+    char ** result)
+{
+  char * thread_subject;
+  int r;
+  unsigned int i;
+
+  if (tree->node_msg != NULL) {
+    if (tree->node_msg->msg_fields != NULL) {
+      r = get_extracted_subject(default_from, tree, &thread_subject);
+
+      if (r != MAIL_NO_ERROR)
+	return r;
+
+      * result = thread_subject;
+      return MAIL_NO_ERROR;
+    }
+  }
+
+  for(i = 0 ; i < carray_count(tree->node_children) ; i ++) {
+    struct mailmessage_tree * child;
+    
+    child = carray_get(tree->node_children, i);
+
+    r = get_thread_subject(default_from, child, &thread_subject);
+    
+    switch (r) {
+    case MAIL_NO_ERROR:
+      * result = thread_subject;
+      return MAIL_NO_ERROR;
+
+    case MAIL_ERROR_SUBJECT_NOT_FOUND:
+      /* do nothing */
+      break;
+
+    default:
+      return r;
+    }
+  }
+
+  return MAIL_ERROR_SUBJECT_NOT_FOUND;
+}
+
+
+
+#ifndef WRONG
+#define WRONG	(-1)
+#endif /* !defined WRONG */
+
+static int tmcomp(struct tm * atmp, struct tm * btmp)
+{
+  register int	result;
+  
+  if ((result = (atmp->tm_year - btmp->tm_year)) == 0 &&
+      (result = (atmp->tm_mon - btmp->tm_mon)) == 0 &&
+      (result = (atmp->tm_mday - btmp->tm_mday)) == 0 &&
+      (result = (atmp->tm_hour - btmp->tm_hour)) == 0 &&
+      (result = (atmp->tm_min - btmp->tm_min)) == 0)
+    result = atmp->tm_sec - btmp->tm_sec;
+  return result;
+}
+
+static time_t mkgmtime(struct tm * tmp)
+{
+  register int			dir;
+  register int			bits;
+  register int			saved_seconds;
+  time_t				t;
+  struct tm			yourtm, *mytm;
+  
+  yourtm = *tmp;
+  saved_seconds = yourtm.tm_sec;
+  yourtm.tm_sec = 0;
+  /*
+  ** Calculate the number of magnitude bits in a time_t
+  ** (this works regardless of whether time_t is
+  ** signed or unsigned, though lint complains if unsigned).
+  */
+  for (bits = 0, t = 1; t > 0; ++bits, t <<= 1)
+    ;
+  /*
+  ** If time_t is signed, then 0 is the median value,
+  ** if time_t is unsigned, then 1 << bits is median.
+  */
+  t = (t < 0) ? 0 : ((time_t) 1 << bits);
+  for ( ; ; ) {
+    mytm = gmtime(&t);
+    dir = tmcomp(mytm, &yourtm);
+    if (dir != 0) {
+      if (bits-- < 0)
+	return WRONG;
+      if (bits < 0)
+	--t;
+      else if (dir > 0)
+	t -= (time_t) 1 << bits;
+      else	t += (time_t) 1 << bits;
+      continue;
+    }
+    break;
+  }
+  t += saved_seconds;
+  return t;
+}
+
+static inline time_t get_date(mailmessage * msg)
+{
+  struct tm tmval;
+  time_t timeval;
+  struct mailimf_date_time * date_time;
+
+  if (msg->msg_single_fields.fld_orig_date == NULL)
+    return (time_t) -1;
+  
+  date_time = msg->msg_single_fields.fld_orig_date->dt_date_time;
+  
+  tmval.tm_sec  = date_time->dt_sec;
+  tmval.tm_min  = date_time->dt_min;
+  tmval.tm_hour = date_time->dt_hour;
+  tmval.tm_sec  = date_time->dt_sec;
+  tmval.tm_mday = date_time->dt_day;
+  tmval.tm_mon  = date_time->dt_month - 1;
+  tmval.tm_year = date_time->dt_year - 1900;
+  
+  timeval = mkgmtime(&tmval);
+  
+  timeval -= date_time->dt_zone * 36;
+  
+  return timeval;
+}
+
+static inline int is_descendant(struct mailmessage_tree * node,
+			 struct mailmessage_tree * maybe_child)
+{
+  unsigned int i;
+
+  for(i = 0 ; i < carray_count(node->node_children) ; i++) {
+    struct mailmessage_tree * tree;
+
+    tree = carray_get(node->node_children, i);
+    if (tree == maybe_child)
+      return TRUE;
+    if (carray_count(tree->node_children) != 0)
+      if (is_descendant(tree, maybe_child))
+	return TRUE;
+  }
+
+  return FALSE;
+}
+
+static int delete_dummy(carray * rootlist, carray * sibling_list,
+    unsigned int cur, unsigned int * pnext)
+{
+  struct mailmessage_tree * env_tree;
+  int res;
+  int r;
+  unsigned int cur_child;
+  unsigned int next;
+
+  env_tree = carray_get(sibling_list, cur);
+
+  cur_child = 0;
+  while (cur_child < carray_count(env_tree->node_children)) {
+    delete_dummy(rootlist, env_tree->node_children, cur_child, &cur_child);
+  }
+
+  if (env_tree->node_msg == NULL) {
+    if (carray_count(env_tree->node_children) == 0) {
+
+      /* If it is a dummy message with NO children, delete it. */
+      mailmessage_tree_free(env_tree);
+      carray_delete(sibling_list, cur);
+      next = cur;
+    }
+    else {
+      /* If it is a dummy message with children, delete it, but
+	 promote its children to the current level. */
+
+      /*
+	Do not promote the children if doing so would make them
+	children of the root, unless there is only one child.
+      */
+
+      cur_child = 0;
+      if ((sibling_list != rootlist) ||
+          (carray_count(env_tree->node_children) == 1)) {
+	while (cur_child < carray_count(env_tree->node_children)) {
+	  struct mailmessage_tree * child;
+	  
+	  child = carray_get(env_tree->node_children, cur_child);
+	  r = carray_add(sibling_list, child, NULL);
+	  if (r < 0) {
+	    res = MAIL_ERROR_MEMORY;
+	    goto err;
+	  }
+          /* set new parent of the children */
+          child->node_parent = env_tree->node_parent;
+
+	  carray_delete(env_tree->node_children, cur_child);
+	}
+        mailmessage_tree_free(env_tree);
+	carray_delete(sibling_list, cur);
+        next = cur;
+      }
+      else
+	next = cur + 1;
+    }
+  }
+  else
+    next = cur + 1;
+
+  * pnext = next;
+
+  return MAIL_NO_ERROR;
+
+ err:
+  return res;       
+}
+
+static inline time_t tree_get_date(struct mailmessage_tree * tree)
+{
+  if (tree->node_msg != NULL) {
+    return tree->node_date;
+  }
+  else {
+    struct mailmessage_tree * subtree;
+    
+    if (carray_count(tree->node_children) == 0)
+      return (time_t) -1;
+    
+    subtree = carray_get(tree->node_children, 0);
+    
+    return subtree->node_date;
+  }
+}
+
+static inline uint32_t tree_get_index(struct mailmessage_tree * tree)
+{
+  if (tree->node_msg == NULL)
+    return 0;
+
+  return tree->node_msg->msg_index;
+}
+
+int mailthread_tree_timecomp(struct mailmessage_tree ** ptree1,
+    struct mailmessage_tree ** ptree2)
+{
+  time_t date1;
+  time_t date2;
+
+  date1 = tree_get_date(* ptree1);
+  date2 = tree_get_date(* ptree2);
+
+  if ((date1 == (time_t) -1) || (date2 == (time_t) -1)) {
+    uint32_t index1;
+    uint32_t index2;
+
+    index1 = tree_get_index(* ptree1);
+    index2 = tree_get_index(* ptree2);
+    return (int) ((long) index1 - (long) index2);
+  }
+
+  return (int) ((long) date1 - (long) date2);
+}
+
+static int tree_subj_time_comp(struct mailmessage_tree ** ptree1,
+			       struct mailmessage_tree ** ptree2)
+{
+  char * subj1;
+  char * subj2;
+  time_t date1;
+  time_t date2;
+  int r;
+
+  subj1 = (* ptree1)->node_base_subject;
+  subj2 = (* ptree2)->node_base_subject;
+
+  if ((subj1 != NULL) && (subj2 != NULL))
+    r = strcmp(subj1, subj2);
+  else {
+    if ((subj1 == NULL) && (subj2 == NULL))
+      r = 0;
+    else if (subj1 == NULL)
+      r = -1;
+    else /* subj2 == NULL */
+      r = 1;
+  }   
+
+  if (r != 0)
+    return r;
+
+  date1 = (* ptree1)->node_date;
+  date2 = (* ptree2)->node_date;
+  
+  if ((date1 == (time_t) -1) || (date2 == (time_t) -1))
+    return ((int32_t) (* ptree1)->node_msg->msg_index) -
+      ((int32_t) (* ptree2)->node_msg->msg_index);
+  
+  return (int) ((long) date1 - (long) date2);
+}
+
+
+
+int mail_thread_sort(struct mailmessage_tree * tree,
+    int (* comp_func)(struct mailmessage_tree **,
+        struct mailmessage_tree **),
+    int sort_sub)
+{
+  unsigned int cur;
+  int r;
+  int res;
+
+  for(cur = 0 ; cur < carray_count(tree->node_children) ; cur ++) {
+    struct mailmessage_tree * subtree;
+
+    subtree = carray_get(tree->node_children, cur);
+
+    if (sort_sub) {
+      r = mail_thread_sort(subtree, comp_func, sort_sub);
+      if (r != MAIL_NO_ERROR) {
+	res = r;
+	goto err;
+      }
+    }
+  }
+
+  qsort(carray_data(tree->node_children), carray_count(tree->node_children),
+      sizeof(struct mailmessage_tree *),
+	(int (*)(const void *, const void *)) comp_func);
+
+  return MAIL_NO_ERROR;
+  
+ err:
+  return res;
+}
+
+
+static int
+mail_build_thread_references(char * default_from,
+    struct mailmessage_list * env_list,
+    struct mailmessage_tree ** result,
+    int use_subject, 
+    int (* comp_func)(struct mailmessage_tree **,
+        struct mailmessage_tree **))
+{
+  int r;
+  int res;
+  chash * msg_id_hash;
+  unsigned int cur;
+  struct mailmessage_tree * root;
+  carray * rootlist;
+  carray * msg_list;
+  unsigned int i;
+  chash * subject_hash;
+
+  msg_id_hash = chash_new(128, CHASH_COPYNONE);
+  if (msg_id_hash == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+
+  root = mailmessage_tree_new(NULL, (time_t) -1, NULL);
+  if (root == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto free_hash;
+  }
+  rootlist = root->node_children;
+
+  msg_list = carray_new(128);
+  if (msg_list == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto free_root;
+  }
+
+  /* collect message-ID */
+  for(i = 0 ; i < carray_count(env_list->msg_tab) ; i ++) {
+    mailmessage * msg;
+    char * msgid;
+    struct mailmessage_tree * env_tree;
+    chashdatum hashkey;
+    chashdatum hashdata;
+    chashdatum hashold;
+    time_t date;
+
+    msg = carray_get(env_list->msg_tab, i);
+
+    if (msg == NULL)
+      continue;
+
+    if (msg->msg_fields != NULL) {
+      msgid = get_msg_id(msg);
+
+      if (msgid == NULL) {
+	msgid = mailimf_get_message_id();
+      }
+      else {
+	hashkey.data = msgid;
+	hashkey.len = strlen(msgid);
+	
+	if (chash_get(msg_id_hash, &hashkey, &hashdata) == 0)
+	  msgid = mailimf_get_message_id();
+	else
+	  msgid = strdup(msgid);
+      }
+      
+      if (msgid == NULL) {
+	res = MAIL_ERROR_MEMORY;
+	goto free_list;
+      }
+      
+      date = get_date(msg);
+      
+      env_tree = mailmessage_tree_new(msgid, date, msg);
+      if (env_tree == NULL) {
+	res = MAIL_ERROR_MEMORY;
+	goto free_list;
+      }
+      
+      r = carray_add(msg_list, env_tree, NULL);
+      if (r < 0) {
+	mailmessage_tree_free(env_tree);
+	res = MAIL_ERROR_MEMORY;
+	goto free_list;
+      }
+      
+      hashkey.data = msgid;
+      hashkey.len = strlen(msgid);
+      
+      hashdata.data = env_tree;
+      hashdata.len = 0;
+      
+      r = chash_set(msg_id_hash, &hashkey, &hashdata, &hashold);
+      if (r < 0) {
+	res = MAIL_ERROR_MEMORY;
+	goto free_list;
+      }
+    }
+  }
+
+  /* (1) for all messages */
+
+  for(cur = 0 ; cur < carray_count(msg_list) ; cur ++) {
+    struct mailmessage_tree * env_tree;
+    mailmessage * msg;
+    clist * ref;
+
+    env_tree = carray_get(msg_list, cur);
+
+    msg = env_tree->node_msg;
+
+    ref = NULL;
+    if (msg != NULL) {
+      ref = get_ref(msg);
+      if (ref == NULL)
+	ref = get_in_reply_to(msg);
+    }      
+
+    /* (A) Using the Message IDs in the message's references, link
+       the corresponding messages (those whose Message-ID header
+       line contains the given reference Message ID) together as
+       parent/child.
+    */
+
+    if (ref != NULL) {
+      /* try to start a tree */
+
+      clistiter * cur_ref;
+      chashdatum hashkey;
+      chashdatum hashdata;
+      chashdatum hashold;
+      struct mailmessage_tree * env_cur_tree;
+      struct mailmessage_tree * last_env_cur_tree;
+
+      env_cur_tree = NULL;
+      for(cur_ref = clist_begin(ref) ; cur_ref != NULL ;
+	  cur_ref = clist_next(cur_ref)) {
+	char * msgid;
+
+	last_env_cur_tree = env_cur_tree;
+
+	msgid = clist_content(cur_ref);
+
+	hashkey.data = msgid;
+	hashkey.len = strlen(msgid);
+	
+	r = chash_get(msg_id_hash, &hashkey, &hashdata);
+	if (r < 0) {
+	  /* not found, create a dummy message */
+	  msgid = strdup(msgid);
+	  if (msgid == NULL) {
+	    res = MAIL_ERROR_MEMORY;
+	    goto free_list;
+	  }
+
+	  env_cur_tree = mailmessage_tree_new(msgid, (time_t) -1, NULL);
+	  if (env_cur_tree == NULL) {
+	    free(msgid);
+	    res = MAIL_ERROR_MEMORY;
+	    goto free_list;
+	  }
+
+	  r = carray_add(msg_list, env_cur_tree, NULL);
+	  if (r < 0) {
+	    mailmessage_tree_free(env_cur_tree);
+	    res = MAIL_ERROR_MEMORY;
+	    goto free_list;
+	  }
+
+	  hashkey.data = msgid;
+	  hashkey.len = strlen(msgid);
+	    
+	  hashdata.data = env_cur_tree;
+	  hashdata.len = 0;
+	  
+	  r = chash_set(msg_id_hash, &hashkey, &hashdata, &hashold);
+	  if (r < 0) {
+	    res = MAIL_ERROR_MEMORY;
+	    goto free_list;
+	  }
+	}
+	else {
+	  env_cur_tree = hashdata.data;
+	}
+
+	if (last_env_cur_tree != NULL) {
+	  if (env_cur_tree->node_parent == NULL) {
+	    /* make it one child */
+	    if (env_cur_tree != last_env_cur_tree) {
+	      if (!is_descendant(env_cur_tree, last_env_cur_tree)) {
+                /* set parent */
+		env_cur_tree->node_parent = last_env_cur_tree;
+		r = carray_add(last_env_cur_tree->node_children,
+                    env_cur_tree, NULL);
+		if (r < 0) {
+		  res = MAIL_ERROR_MEMORY;
+		  goto free_list;
+		}
+	      }
+	    }
+	  }
+	}
+      }
+
+      /* (B) Create a parent/child link between the last reference
+	 (or NIL if there are no references) and the current message.
+	 If the current message already has a parent, it is probably
+	 the result of a truncated References header line, so break
+	 the current parent/child link before creating the new
+	 correct one.
+      */
+      
+      last_env_cur_tree = env_cur_tree;
+      
+      if (last_env_cur_tree != NULL) {
+	if (env_tree->node_parent == NULL) {
+	  if (last_env_cur_tree != env_tree) {
+	    if (!is_descendant(env_tree, last_env_cur_tree)) {
+              /* set parent */
+	      env_tree->node_parent = last_env_cur_tree;
+	      r = carray_add(last_env_cur_tree->node_children, env_tree, NULL);
+	      if (r < 0) {
+		res = MAIL_ERROR_MEMORY;
+		goto free_list;
+	      }
+	    }
+	  }
+	}
+      }
+    }
+  }
+
+  chash_free(msg_id_hash);
+  msg_id_hash = NULL;
+
+  /* (2) Gather together all of the messages that have no parents
+     and make them all children (siblings of one another) of a dummy
+     parent (the "root").
+  */
+
+  for(cur = 0 ; cur < carray_count(msg_list) ; cur ++) {
+    struct mailmessage_tree * env_tree;
+
+    env_tree = carray_get(msg_list, cur);
+    if (env_tree->node_parent == NULL) {
+      r = carray_add(rootlist, env_tree, NULL);
+      if (r < 0) {
+	res = MAIL_ERROR_MEMORY;
+	goto free_list;
+      }
+      /* set parent */
+      env_tree->node_parent = root;
+    }
+  }
+
+  carray_free(msg_list);
+  msg_list = NULL;
+
+  /* (3) Prune dummy messages from the thread tree.
+   */
+
+  cur = 0;
+  while (cur < carray_count(rootlist)) {
+    r = delete_dummy(rootlist, rootlist, cur, &cur);
+    if (r != MAIL_NO_ERROR) {
+      res = r;
+      goto free_list;
+    }
+  }
+
+  /* (4) Sort the messages under the root (top-level siblings only)
+     by sent date.
+  */
+
+  r = mail_thread_sort(root, mailthread_tree_timecomp, FALSE);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto free_list;
+  }
+
+  if (use_subject) {
+
+    /* (5) Gather together messages under the root that have the same
+       extracted subject text.
+
+       (A) Create a table for associating extracted subjects with
+       messages.
+    */
+
+    subject_hash = chash_new(128, CHASH_COPYVALUE);
+    if (subject_hash == NULL) {
+      res = MAIL_ERROR_MEMORY;
+      goto free_list;
+    }
+
+    /*
+      (B) Populate the subject table with one message per
+      extracted subject.  For each child of the root:
+    */
+
+    for(cur = 0 ; cur < carray_count(rootlist) ; cur ++) {
+      struct mailmessage_tree * env_tree;
+      chashdatum key;
+      chashdatum data;
+      char * base_subject;
+      int r;
+
+      env_tree = carray_get(rootlist, cur);
+
+      /*
+	(i) Find the subject of this thread by extracting the
+	base subject from the current message, or its first child
+	if the current message is a dummy.
+      */
+
+      r = get_thread_subject(default_from, env_tree, &base_subject);
+
+      /*
+	(ii) If the extracted subject is empty, skip this
+	message.
+      */
+
+      if (r == MAIL_ERROR_SUBJECT_NOT_FOUND) {
+	/* no subject found */
+	continue;
+      }
+      else if (r == MAIL_NO_ERROR) {
+	if (* base_subject == '\0') {
+	  /* subject empty */
+	  free(base_subject);
+	  continue;
+	}
+	else {
+	  /* do nothing */
+	}
+      }
+      else {
+	res = r;
+	goto free_subject_hash;
+      }
+
+      env_tree->node_base_subject = base_subject;
+
+      /*
+	(iii) Lookup the message associated with this extracted
+	subject in the table.
+      */
+
+      key.data = base_subject;
+      key.len = strlen(base_subject);
+
+      r = chash_get(subject_hash, &key, &data);
+
+      if (r < 0) {
+	/*
+	  (iv) If there is no message in the table with this
+	  subject, add the current message and the extracted
+	  subject to the subject table.
+	*/
+
+	data.data = &cur;
+	data.len = sizeof(cur);
+
+	r = chash_set(subject_hash, &key, &data, NULL);
+	if (r < 0) {
+	  res = MAIL_ERROR_MEMORY;
+	  goto free_subject_hash;
+	}
+      }
+      else {
+	/*
+	  Otherwise, replace the message in the table with the
+	  current message if the message in the table is not a
+	  dummy AND either of the following criteria are true:
+	  The current message is a dummy, OR                  
+	  The message in the table is a reply or forward (its
+	  original subject contains a subj-refwd part and/or a
+	  "(fwd)" subj-trailer) and the current message is not.
+	*/
+	struct mailmessage_tree * msg_in_table;
+	unsigned int * iter_in_table;
+	int replace;
+
+	iter_in_table = data.data;
+	msg_in_table = carray_get(rootlist, cur);
+
+	replace = FALSE;
+	/* message is dummy if info is NULL */
+	if (msg_in_table->node_msg != NULL) {
+
+	  if (env_tree->node_msg == NULL)
+	    replace = TRUE;
+	  else {
+	    if (env_tree->node_is_reply && !env_tree->node_is_reply)
+	      replace = TRUE;
+	  }
+	}
+ 
+	if (replace) {
+	  data.data = &cur;
+	  data.len = sizeof(cur);
+	
+	  r = chash_set(subject_hash, &key, &data, NULL);
+	  if (r < 0) {
+	    res = MAIL_ERROR_MEMORY;
+	    goto free_subject_hash;
+	  }
+	}
+      }
+    }
+
+    /*
+      (C) Merge threads with the same subject.  For each child of
+      the root:
+    */
+
+    cur = 0;
+    while (cur < carray_count(rootlist)) {
+      struct mailmessage_tree * env_tree;
+      chashdatum key;
+      chashdatum data;
+      int r;
+      struct mailmessage_tree * main_tree;
+      unsigned int * main_cur;
+
+      env_tree = carray_get(rootlist, cur);
+
+      if (env_tree == NULL)
+        goto next_msg;
+
+      /*
+	(i) Find the subject of this thread as in step 4.B.i
+	above.
+      */
+    
+      /* already done in tree->node_base_subject */
+    
+      /*
+	(ii) If the extracted subject is empty, skip this
+	message.
+      */
+    
+      if (env_tree->node_base_subject == NULL)
+	goto next_msg;
+
+      if (* env_tree->node_base_subject == '\0')
+	goto next_msg;
+
+      /*
+	(iii) Lookup the message associated with this extracted
+	subject in the table.
+      */
+
+      key.data = env_tree->node_base_subject;
+      key.len = strlen(env_tree->node_base_subject);
+
+      r = chash_get(subject_hash, &key, &data);
+      if (r < 0)
+	goto next_msg;
+
+      /*
+	(iv) If the message in the table is the current message,
+	skip this message. 
+      */
+    
+      main_cur = data.data;
+      if (* main_cur == cur)
+	goto next_msg;
+
+      /*
+	Otherwise, merge the current message with the one in the
+	table using the following rules:
+      */
+
+      main_tree = carray_get(rootlist, * main_cur);
+
+      /*
+	If both messages are dummies, append the current
+	message's children to the children of the message in
+	the table (the children of both messages become
+	siblings), and then delete the current message.
+      */
+
+      if ((env_tree->node_msg == NULL) && (main_tree->node_msg == NULL)) {
+        unsigned int old_size;
+
+        old_size = carray_count(main_tree->node_children);
+
+        r = carray_set_size(main_tree->node_children, old_size +
+            carray_count(env_tree->node_children));
+        if (r < 0) {
+          res = MAIL_ERROR_MEMORY;
+          goto free_subject_hash;
+        }
+
+        for(i = 0 ; i < carray_count(env_tree->node_children) ; i ++) {
+          struct mailmessage_tree * child;
+
+          child = carray_get(env_tree->node_children, i);
+          carray_set(main_tree->node_children, old_size + i, child);
+          /* set parent */
+          child->node_parent = main_tree;
+        }
+        carray_set_size(env_tree->node_children, 0);
+	/* this is the only case where children can be NULL,
+	   this is before freeing it */
+	mailmessage_tree_free(env_tree);
+        carray_delete_fast(rootlist, cur);
+      }
+
+      /*
+	If the message in the table is a dummy and the current
+	message is not, make the current message a child of
+	the message in the table (a sibling of it's children).
+      */
+
+      else if (main_tree->node_msg == NULL) {
+	r = carray_add(main_tree->node_children, env_tree, NULL);
+	if (r < 0) {
+	  res = MAIL_ERROR_MEMORY;
+	  goto free_subject_hash;
+	}
+        /* set parent */
+        env_tree->node_parent = main_tree;
+
+	carray_delete_fast(rootlist, cur);
+      }
+
+      /*
+	If the current message is a reply or forward and the
+	message in the table is not, make the current message
+	a child of the message in the table (a sibling of it's
+	children).
+      */
+
+      else if (env_tree->node_is_reply && !main_tree->node_is_reply) {
+	r = carray_add(main_tree->node_children, env_tree, NULL);
+	if (r < 0) {
+	  res = MAIL_ERROR_MEMORY;
+	  goto free_subject_hash;
+	}
+        /* set parent */
+        env_tree->node_parent = main_tree;
+
+	carray_delete_fast(rootlist, cur);
+      }
+
+      /*
+	Otherwise, create a new dummy message and make both
+	the current message and the message in the table
+	children of the dummy.  Then replace the message in
+	the table with the dummy message.
+	Note: Subject comparisons are case-insensitive, as
+	described under "Internationalization
+	Considerations."
+      */
+
+      else {
+	struct mailmessage_tree * new_main_tree;
+	char * base_subject;
+        unsigned int last;
+
+	new_main_tree = mailmessage_tree_new(NULL, (time_t) -1, NULL);
+	if (new_main_tree == NULL) {
+	  res = MAIL_ERROR_MEMORY;
+	  goto free_subject_hash;
+	}
+
+	/* main_tree->node_base_subject is never NULL */
+
+	base_subject = strdup(main_tree->node_base_subject);
+	if (base_subject == NULL) {
+	  mailmessage_tree_free(new_main_tree);
+	  res = MAIL_ERROR_MEMORY;
+	  goto free_subject_hash;
+	}
+
+	new_main_tree->node_base_subject = base_subject;
+
+	r = carray_add(rootlist, new_main_tree, &last);
+	if (r < 0) {
+	  mailmessage_tree_free(new_main_tree);
+	  res = MAIL_ERROR_MEMORY;
+	  goto free_subject_hash;
+	}
+
+	r = carray_add(new_main_tree->node_children, main_tree, NULL);
+	if (r < 0) {
+	  res = MAIL_ERROR_MEMORY;
+	  goto free_subject_hash;
+	}
+        /* set parent */
+        main_tree->node_parent = new_main_tree;
+
+	carray_delete_fast(rootlist, * main_cur);
+
+	r = carray_add(new_main_tree->node_children, env_tree, NULL);
+	if (r < 0) {
+	  res = MAIL_ERROR_MEMORY;
+	  goto free_subject_hash;
+	}
+        /* set parent */
+        env_tree->node_parent = new_main_tree;
+
+	carray_delete_fast(rootlist, cur);
+
+	data.data = &last;
+	data.len = sizeof(last);
+      
+	r = chash_set(subject_hash, &key, &data, NULL);
+
+	if (r < 0) {
+	  res = MAIL_ERROR_MEMORY;
+	  goto free_subject_hash;
+	}
+      }
+
+      continue;
+
+    next_msg:
+      cur ++;
+      continue;
+    }
+    
+    i = 0;
+    for(cur = 0 ; cur < carray_count(rootlist) ; cur ++) {
+      struct mailmessage_tree * env_tree;
+
+      env_tree = carray_get(rootlist, cur);
+      if (env_tree == NULL)
+        continue;
+      
+      carray_set(rootlist, i, env_tree);
+      i ++;
+    }
+    carray_set_size(rootlist, i);
+    
+    chash_free(subject_hash);
+  }
+
+  /*
+    (6) Traverse the messages under the root and sort each set of
+    siblings by sent date.  Traverse the messages in such a way
+    that the "youngest" set of siblings are sorted first, and the
+    "oldest" set of siblings are sorted last (grandchildren are
+    sorted before children, etc).
+
+    In the case of an exact match on
+    sent date or if either of the Date: headers used in a
+    comparison can not be parsed, use the order in which the
+    messages appear in the mailbox (that is, by sequence number) to
+    determine the order.  In the case of a dummy message (which can
+    only occur with top-level siblings), use its first child for
+    sorting.
+  */
+
+#if 0
+  if (comp_func != NULL) {
+    r = mail_thread_sort(root, comp_func, TRUE);
+    if (r != MAIL_NO_ERROR) {
+      res = r;
+      goto free_list;
+    }
+  }
+#endif
+  if (comp_func == NULL)
+    comp_func = mailthread_tree_timecomp;
+  
+  r = mail_thread_sort(root, comp_func, TRUE);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto free_list;
+  }
+  
+  * result = root;
+
+  return MAIL_NO_ERROR;
+
+ free_subject_hash:
+  chash_free(subject_hash);
+ free_list:
+  if (msg_list != NULL) {
+    for(i = 0 ; i < carray_count(msg_list) ; i ++)
+      mailmessage_tree_free(carray_get(msg_list, i));
+    carray_free(msg_list);
+  }
+ free_root:
+  mailmessage_tree_free_recursive(root);
+ free_hash:
+  if (msg_id_hash != NULL)
+    chash_free(msg_id_hash);
+ err:
+  return res;
+}
+
+
+
+static int
+mail_build_thread_orderedsubject(char * default_from,
+    struct mailmessage_list * env_list,
+    struct mailmessage_tree ** result,
+    int (* comp_func)(struct mailmessage_tree **,
+        struct mailmessage_tree **))
+{
+  unsigned int i;
+  carray * rootlist;
+  unsigned int cur;
+  struct mailmessage_tree * root;
+  int res;
+  int r;
+  struct mailmessage_tree * current_thread;
+
+  root = mailmessage_tree_new(NULL, (time_t) -1, NULL);
+  if (root == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+  rootlist = root->node_children;
+
+  /*
+    The ORDEREDSUBJECT threading algorithm is also referred to as
+    "poor man's threading."
+  */
+
+  for(i = 0 ; i < carray_count(env_list->msg_tab) ; i ++) {
+    mailmessage * msg;
+    struct mailmessage_tree * env_tree;
+    char * base_subject;
+    time_t date;
+
+    msg = carray_get(env_list->msg_tab, i);
+
+    if (msg == NULL)
+      continue;
+
+    if (msg->msg_fields != NULL) {
+
+      date = get_date(msg);
+
+      env_tree = mailmessage_tree_new(NULL, date, msg);
+      if (env_tree == NULL) {
+	res = MAIL_ERROR_MEMORY;
+	goto free;
+      }
+
+      /* set parent */
+      env_tree->node_parent = root;
+      r = carray_add(rootlist, env_tree, NULL);
+      if (r < 0) {
+	mailmessage_tree_free(env_tree);
+	res = MAIL_ERROR_MEMORY;
+	goto free;
+      }
+
+      r = get_extracted_subject(default_from, env_tree, &base_subject);
+      switch (r) {
+      case MAIL_NO_ERROR:
+	env_tree->node_base_subject = base_subject;
+	break;
+
+      case MAIL_ERROR_SUBJECT_NOT_FOUND:
+	break;
+	
+      default:
+	res = r;
+	goto free;
+      }
+    }
+  }
+
+  /*
+    The searched messages are sorted by
+    subject and then by the sent date.
+  */
+
+  r = mail_thread_sort(root, tree_subj_time_comp, FALSE);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto free;
+  }
+
+  /*
+    The messages are then split
+    into separate threads, with each thread containing messages
+    with the same extracted subject text.
+  */
+
+  current_thread = NULL;
+
+  cur = 0;
+  while (cur < carray_count(rootlist)) {
+    struct mailmessage_tree * cur_env_tree;
+
+    cur_env_tree = carray_get(rootlist, cur);
+    if (current_thread == NULL) {
+      current_thread = cur_env_tree;
+      cur ++;
+      continue;
+    }
+
+    if ((cur_env_tree->node_base_subject == NULL) ||
+	(current_thread->node_base_subject == NULL)) {
+      current_thread = cur_env_tree;
+      cur ++;
+      continue;
+    }
+
+    if (strcmp(cur_env_tree->node_base_subject,
+            current_thread->node_base_subject) == 0) {
+
+      /* set parent */
+      cur_env_tree->node_parent = current_thread;
+      r = carray_add(current_thread->node_children, cur_env_tree, NULL);
+      if (r < 0) {
+	res = MAIL_ERROR_MEMORY;
+	goto free;
+      }
+      
+      carray_delete(rootlist, cur);
+    }
+    else
+      cur ++;
+    current_thread = cur_env_tree;
+  }
+
+  /*
+    Finally, the threads are
+    sorted by the sent date of the first message in the thread.
+    Note that each message in a thread is a child (as opposed to a
+    sibling) of the previous message.
+  */
+
+#if 0
+  if (comp_func != NULL) {
+    r = mail_thread_sort(root, comp_func, FALSE);
+    if (r != MAIL_NO_ERROR) {
+      res = r;
+      goto free;
+    }
+  }
+#endif
+  
+  if (comp_func == NULL)
+    comp_func = mailthread_tree_timecomp;
+  
+  r = mail_thread_sort(root, comp_func, FALSE);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto free;
+  }
+
+  * result = root;
+
+  return MAIL_NO_ERROR;
+
+ free:
+  mailmessage_tree_free_recursive(root);
+ err:
+  return res;
+}
+
+
+static int
+mail_build_thread_none(char * default_from,
+    struct mailmessage_list * env_list,
+    struct mailmessage_tree ** result,
+    int (* comp_func)(struct mailmessage_tree **,
+        struct mailmessage_tree **))
+{
+  unsigned int i;
+  carray * rootlist;
+  struct mailmessage_tree * root;
+  int res;
+  int r;
+
+  root = mailmessage_tree_new(NULL, (time_t) -1, NULL);
+  if (root == NULL) {
+    res = MAIL_ERROR_MEMORY;
+    goto err;
+  }
+  rootlist = root->node_children;
+
+  for(i = 0 ; i < carray_count(env_list->msg_tab) ; i ++) {
+    mailmessage * msg;
+    struct mailmessage_tree * env_tree;
+    char * base_subject;
+    time_t date;
+
+    msg = carray_get(env_list->msg_tab, i);
+
+    if (msg == NULL)
+      continue;
+
+    if (msg->msg_fields != NULL) {
+
+      date = get_date(msg);
+
+      env_tree = mailmessage_tree_new(NULL, date, msg);
+      if (env_tree == NULL) {
+	res = MAIL_ERROR_MEMORY;
+	goto free;
+      }
+
+      /* set parent */
+      env_tree->node_parent = root;
+      r = carray_add(rootlist, env_tree, NULL);
+      if (r < 0) {
+	mailmessage_tree_free(env_tree);
+	res = MAIL_ERROR_MEMORY;
+	goto free;
+      }
+
+      r = get_extracted_subject(default_from, env_tree, &base_subject);
+      switch (r) {
+      case MAIL_NO_ERROR:
+	env_tree->node_base_subject = base_subject;
+	break;
+
+      case MAIL_ERROR_SUBJECT_NOT_FOUND:
+	break;
+	
+      default:
+	res = r;
+	goto free;
+      }
+    }
+  }
+  
+  if (comp_func == NULL)
+    comp_func = mailthread_tree_timecomp;
+  
+  r = mail_thread_sort(root, comp_func, FALSE);
+  if (r != MAIL_NO_ERROR) {
+    res = r;
+    goto free;
+  }
+  
+  * result = root;
+
+  return MAIL_NO_ERROR;
+
+ free:
+  mailmessage_tree_free_recursive(root);
+ err:
+  return res;
+}
+
+
+int mail_build_thread(int type, char * default_from,
+    struct mailmessage_list * env_list,
+    struct mailmessage_tree ** result,
+     int (* comp_func)(struct mailmessage_tree **,
+         struct mailmessage_tree **))
+{
+  unsigned int i;
+
+  for(i = 0 ; i < carray_count(env_list->msg_tab) ; i ++)
+    mailmessage_resolve_single_fields(carray_get(env_list->msg_tab, i));
+
+  switch (type) {
+  case MAIL_THREAD_REFERENCES:
+    return mail_build_thread_references(default_from,
+        env_list, result, TRUE, comp_func);
+
+  case MAIL_THREAD_REFERENCES_NO_SUBJECT:
+    return mail_build_thread_references(default_from,
+        env_list, result, FALSE, comp_func);
+
+  case MAIL_THREAD_ORDEREDSUBJECT:
+    return mail_build_thread_orderedsubject(default_from,
+        env_list, result, comp_func);
+    
+  case MAIL_THREAD_NONE:
+    return mail_build_thread_none(default_from,
+        env_list, result, comp_func);
+    
+  default:
+    return MAIL_ERROR_NOT_IMPLEMENTED;
+  }
+}
diff --git a/libetpan/src/driver/tools/mailthread.h b/libetpan/src/driver/tools/mailthread.h
new file mode 100644
index 0000000..fa2f4bc
--- a/dev/null
+++ b/libetpan/src/driver/tools/mailthread.h
@@ -0,0 +1,108 @@
+/*
+ * libEtPan! -- a mail stuff library
+ *
+ * Copyright (C) 2001, 2005 - DINH Viet Hoa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the libEtPan! project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * $Id$
+ */
+
+#ifndef MAILTHREAD_H
+
+#define MAILTHREAD_H
+
+#include <libetpan/mailthread_types.h>
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/*
+  mail_build_thread constructs a tree with the message using the 
+  given style.
+
+  @param type is the type of threading to apply, the value can be
+    MAIL_THREAD_REFERENCES, MAIL_THREAD_REFERENCES_NO_SUBJECT,
+    MAIL_THREAD_ORDEREDSUBJECT or MAIL_THREAD_NONE,
+
+  @param default_from is the default charset to use whenever the
+    subject is not tagged with a charset. "US-ASCII" can be used
+    if you don't know what to use.
+
+  @param env_list is the message list (with header fields fetched)
+    to use to build the message tree.
+
+  @param result * result) will contain the resulting message tree.
+
+  @param if comp_func is NULL, no sorting algorithm is used.
+
+  @return MAIL_NO_ERROR is returned on success, MAIL_ERROR_XXX is returned
+    on error
+*/
+
+int mail_build_thread(int type, char * default_from,
+    struct mailmessage_list * env_list,
+    struct mailmessage_tree ** result,
+     int (* comp_func)(struct mailmessage_tree **,
+         struct mailmessage_tree **));
+
+/*
+  mail_thread_sort sort the messages in the message tree, using the
+  given sort function.
+
+  @param tree is the message tree to sort.
+  
+  @param comp_func is the sort function to use (this is the same kind of
+    functions than those used for qsort()). mailthread_tree_timecomp can be
+    used for default sort.
+
+  @param sort_sub if this value is 0, only the children of the root message
+    are sorted.
+*/
+
+int mail_thread_sort(struct mailmessage_tree * tree,
+    int (* comp_func)(struct mailmessage_tree **,
+        struct mailmessage_tree **),
+    int sort_sub);
+
+/*
+  mailthread_tree_timecomp is the default sort function.
+
+  The message are compared by date, then by message numbers.
+  The tree are given in (* ptree1) and (* ptree2).
+*/
+
+int mailthread_tree_timecomp(struct mailmessage_tree ** ptree1,
+    struct mailmessage_tree ** ptree2);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/libetpan/src/driver/tools/mailthread_types.c b/libetpan/src/driver/tools/mailthread_types.c
new file mode 100644
index 0000000..dc2a4ca
--- a/dev/null
+++ b/libetpan/src/driver/tools/mailthread_types.c
@@ -0,0 +1,90 @@
+/*
+ * libEtPan! -- a mail stuff library
+ *
+ * Copyright (C) 2001, 2005 - DINH Viet Hoa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the libEtPan! project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * $Id$
+ */
+
+#include "mailthread_types.h"
+
+#include "mail.h"
+#include <stdlib.h>
+
+struct mailmessage_tree *
+mailmessage_tree_new(char * node_msgid, time_t node_date,
+    mailmessage * node_msg)
+{
+  struct mailmessage_tree * tree;
+  carray * array;
+
+  array = carray_new(16);
+  if (array == NULL)
+    return NULL;
+
+  tree = malloc(sizeof(* tree));
+  tree->node_parent = NULL;
+  tree->node_date = node_date;
+  tree->node_msgid = node_msgid;
+  tree->node_msg = node_msg;
+  tree->node_children = array;
+  tree->node_base_subject = NULL;
+  tree->node_is_reply = FALSE;
+
+  return tree;
+}
+
+void mailmessage_tree_free(struct mailmessage_tree * tree)
+{
+  if (tree->node_base_subject != NULL)
+    free(tree->node_base_subject);
+
+  if (tree->node_children != NULL)
+    carray_free(tree->node_children);
+  if (tree->node_msgid != NULL)
+    free(tree->node_msgid);
+
+  free(tree);
+}
+
+void mailmessage_tree_free_recursive(struct mailmessage_tree * tree)
+{
+  unsigned int i;
+
+  for(i = 0 ; i < carray_count(tree->node_children) ; i++) {
+    struct mailmessage_tree * child;
+
+    child = carray_get(tree->node_children, i);
+
+    mailmessage_tree_free_recursive(child);
+  }
+
+  mailmessage_tree_free(tree);
+}
diff --git a/libetpan/src/driver/tools/mailthread_types.h b/libetpan/src/driver/tools/mailthread_types.h
new file mode 100644
index 0000000..3325904
--- a/dev/null
+++ b/libetpan/src/driver/tools/mailthread_types.h
@@ -0,0 +1,64 @@
+/*
+ * libEtPan! -- a mail stuff library
+ *
+ * Copyright (C) 2001, 2005 - DINH Viet Hoa
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 3. Neither the name of the libEtPan! project nor the names of its
+ *    contributors may be used to endorse or promote products derived
+ *    from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHORS AND CONTRIBUTORS ``AS IS'' AND
+ * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHORS OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
+ * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+ * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
+ * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
+ * SUCH DAMAGE.
+ */
+
+/*
+ * $Id$
+ */
+
+#ifndef MAILTHREAD_TYPES_H
+
+#define MAILTHREAD_TYPES_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <libetpan/maildriver_types.h>
+#include <libetpan/mailmessage_types.h>
+
+/*
+  This is the type of tree construction to apply.
+*/
+
+enum {
+  MAIL_THREAD_REFERENCES,            /* this is threading using
+                                        References fields only) */
+  MAIL_THREAD_REFERENCES_NO_SUBJECT, /* this is threading using References
+                                        fields, then subject */
+  MAIL_THREAD_ORDEREDSUBJECT,        /* this is threading using only subject */
+  MAIL_THREAD_NONE,                  /* no thread */
+};
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif