diff -Nru a/PATCHES b/PATCHES
--- a/PATCHES
+++ b/PATCHES
@@ -0,0 +1 @@
+mutt-cvs-header-cache.30
--- a/configure.in
+++ b/configure.in
@@ -804,10 +804,23 @@
     OLDLIBS="$LIBS"
 
     need_md5="yes"
+
+    ac_prefer_qdbm=yes
+    AC_ARG_WITH(qdbm, AC_HELP_STRING([--without-qdbm], [Don't use qdbm even if it is available]),
+        ac_prefer_qdbm=$withval)
+    if test x$ac_prefer_qdbm != xno; then
+        CPPFLAGS="$OLDCPPFLAGS"
+        LIBS="$OLDLIBS -lqdbm";
+        AC_CACHE_CHECK(for vlopen, ac_cv_vlopen,[
+            ac_cv_vlopen=no
+            AC_TRY_LINK([#include <villa.h>],[vlopen(0,0,0);],[ac_cv_vlopen=yes])
+        ])
+    fi
+
     ac_prefer_gdbm=yes
     AC_ARG_WITH(gdbm, AC_HELP_STRING([--without-gdbm], [Don't use gdbm even if it is available]),
         ac_prefer_gdbm=$withval)
-    if test x$ac_prefer_gdbm != xno; then
+    if test x$ac_prefer_gdbm != xno -a x$ac_cv_vlopen != xyes; then
         CPPFLAGS="$OLDCPPFLAGS"
         LIBS="$OLDLIBS -lgdbm";
         AC_CACHE_CHECK(for gdbm_open, ac_cv_gdbmopen,[
@@ -819,7 +832,7 @@
     ac_bdb_prefix=yes
     AC_ARG_WITH(bdb, AC_HELP_STRING([--with-bdb[=DIR]], [Use BerkeleyDB4 if gdbm is not available]),
         ac_bdb_prefix=$withval)
-    if test x$ac_bdb_prefix != xno -a x$ac_cv_gdbmopen != xyes; then
+    if test x$ac_bdb_prefix != xno -a x$ac_cv_gdbmopen != xyes -a x$ac_cv_vlopen != xyes; then
         test x$ac_bdb_prefix = xyes && ac_bdb_prefix="$mutt_cv_prefix /opt/csw/bdb4 /opt /usr/local /usr"
         for d in $ac_bdb_prefix; do
             bdbpfx="$bdbpfx $d"
@@ -865,7 +878,11 @@
         fi
     fi
 
-    if test x$ac_cv_gdbmopen = xyes; then
+    if test x$ac_cv_vlopen = xyes; then
+        CPPFLAGS="$OLDCPPFLAGS"
+        LIBS="$OLDLIBS -lqdbm";
+        AC_DEFINE(HAVE_QDBM, 1, [QDBM Support])
+    elif test x$ac_cv_gdbmopen = xyes; then
         CPPFLAGS="$OLDCPPFLAGS"
         LIBS="$OLDLIBS -lgdbm";
         AC_DEFINE(HAVE_GDBM, 1, [GDBM Support])
--- a/hcache.c
+++ b/hcache.c
@@ -22,7 +22,11 @@
 #include "config.h"
 #endif				/* HAVE_CONFIG_H */
 
-#if HAVE_GDBM
+#if HAVE_QDBM
+#include <depot.h>
+#include <cabin.h>
+#include <villa.h>
+#elif HAVE_GDBM
 #include <gdbm.h>
 #elif HAVE_DB4
 #include <db.h>
@@ -42,7 +46,14 @@
 #include "lib.h"
 #include "md5.h"
 
-#if HAVE_GDBM
+#if HAVE_QDBM
+static struct header_cache
+{
+  VILLA *db;
+  char *folder;
+  unsigned int crc;
+} HEADER_CACHE;
+#elif HAVE_GDBM
 static struct header_cache
 {
   GDBM_FILE db;
@@ -615,7 +626,139 @@
   return h;
 }
 
-#if HAVE_GDBM
+#if HAVE_QDBM
+void *
+mutt_hcache_open(const char *path, const char *folder)
+{
+  struct header_cache *h = safe_calloc(1, sizeof (HEADER_CACHE));
+  int    flags = 0;
+#if 0 /* FIXME */
+  int pagesize = atoi(HeaderCachePageSize) ? atoi(HeaderCachePageSize) : 16384;
+#endif
+  h->db = NULL;
+  h->folder = safe_strdup(folder);
+  h->crc = generate_crc32();
+
+  if (!path || path[0] == '\0')
+  {
+    FREE(&h->folder);
+    FREE(&h);
+    return NULL;
+  }
+
+  path = mutt_hcache_per_folder(path, folder);
+
+  if (option(OPTHCACHECOMPRESS))
+    flags = VL_OZCOMP;
+
+  h->db = vlopen(path, flags | VL_OWRITER | VL_OCREAT, VL_CMPLEX);
+  if (h->db)
+    return h;
+
+  /* if rw failed try ro */
+  h->db = vlopen(path, flags | VL_OREADER, 0);
+  if (h->db)
+    return h;
+  else
+  {
+    FREE(&h->folder);
+    FREE(&h);
+
+    return NULL;
+  }
+}
+
+void
+mutt_hcache_close(void *db)
+{
+  struct header_cache *h = db;
+
+  if (!h)
+    return;
+
+  vlclose(h->db);
+  FREE(&h->folder);
+  FREE(&h);
+}
+
+void *
+mutt_hcache_fetch(void *db, const char *filename,
+		  size_t(*keylen) (const char *fn))
+{
+  struct header_cache *h = db;
+  char path[_POSIX_PATH_MAX];
+  int ksize;
+  char *data = NULL;
+
+  if (!h)
+    return NULL;
+
+  strncpy(path, h->folder, sizeof (path));
+  safe_strcat(path, sizeof (path), filename);
+
+  ksize = strlen(h->folder) + keylen(path + strlen(h->folder));
+
+  data = vlget(h->db, path, ksize, NULL);
+
+  if (! crc32_matches(data, h->crc))
+  {
+    if (data) { 
+      FREE(&data);
+    }
+    return NULL;
+  }
+
+  return data;
+}
+
+int
+mutt_hcache_store(void *db, const char *filename, HEADER * header,
+		  unsigned long uid_validity,
+		  size_t(*keylen) (const char *fn))
+{
+  struct header_cache *h = db;
+  char path[_POSIX_PATH_MAX];
+  int ret;
+  int ksize, dsize;
+  char *data = NULL;
+
+  if (!h)
+    return -1;
+
+  strncpy(path, h->folder, sizeof (path));
+  safe_strcat(path, sizeof (path), filename);
+
+  ksize = strlen(h->folder) + keylen(path + strlen(h->folder));
+
+  data  = mutt_hcache_dump(db, header, &dsize, uid_validity);
+
+  ret = vlput(h->db, path, ksize, data, dsize, VL_DOVER);
+
+  FREE(&data);
+
+  return ret;
+}
+
+int
+mutt_hcache_delete(void *db, const char *filename,
+		   size_t(*keylen) (const char *fn))
+{
+  struct header_cache *h = db;
+  char path[_POSIX_PATH_MAX];
+  int ksize;
+
+  if (!h)
+    return -1;
+
+  strncpy(path, h->folder, sizeof (path));
+  safe_strcat(path, sizeof (path), filename);
+
+  ksize = strlen(h->folder) + keylen(path + strlen(h->folder));
+
+  return vlout(h->db, path, ksize);
+}
+
+#elif HAVE_GDBM
 
 void *
 mutt_hcache_open(const char *path, const char *folder)
--- a/init.h
+++ b/init.h
@@ -1079,6 +1079,15 @@
   ** files when the header cache is in use.  This incurs one stat(2) per
   ** message every time the folder is opened.
   */
+#if HAVE_QDBM
+  { "header_cache_compress", DT_BOOL, R_NONE, OPTHCACHECOMPRESS, 0 },
+  /*
+  ** .pp
+  ** If enabled the header cache will be compressed. So only one fifth of the usual
+  ** diskspace is used, but the uncompression can result in a slower open of the
+  ** cached folder.
+  */
+#endif /* HAVE_QDBM */
   { "header_cache_pagesize", DT_STR, R_NONE, UL &HeaderCachePageSize, UL "16384" },
   /*
   ** .pp
--- a/mutt.h
+++ b/mutt.h
@@ -353,6 +353,9 @@
   OPTFORWQUOTE,
 #if USE_HCACHE
   OPTHCACHEVERIFY,
+#if HAVE_QDBM
+  OPTHCACHECOMPRESS,
+#endif /* HAVE_QDBM */
 #endif
   OPTHDRS,
   OPTHEADER,