From e2e9438843e60d660af18f9e2cdbfa49e976b61a Mon Sep 17 00:00:00 2001
From: Florian Weimer <fw@deneb.enyo.de>
Date: Thu, 27 Jan 2005 18:45:36 +0000
Subject: [PATCH] Read files in maildir folders in inode order; this seems to
 reduce seek overhead on Linux.  Enabled by default; to disable, run configure
 with --disable-inodesort.  (By way of Mario d'Itri.)

---
 configure.in |   8 ++++
 mh.c         | 106 ++++++++++++++++++++++++++++++++++++++++++++++++++-
 2 files changed, 112 insertions(+), 2 deletions(-)

diff --git a/configure.in b/configure.in
index 3d3f8bc70..791f1eaf6 100644
--- a/configure.in
+++ b/configure.in
@@ -715,6 +715,14 @@ if test $mutt_cv_fcntl = yes; then
         AC_DEFINE(USE_FCNTL,1, [ Define to use fcntl() to lock folders. ])
 fi
 
+mutt_cv_inodesort=yes
+AC_ARG_ENABLE(inodesort,  [   --disable-inodesort	Do NOT read files in maildir folders sorted by inode. ],
+       [if test $enableval = no ; then mutt_cv_inodesort=no; fi])
+
+if test $mutt_cv_inodesort = yes; then
+	AC_DEFINE(USE_INODESORT, 1, [ Define to sort files in a	maildir by inode number. ])
+fi
+
 mutt_cv_warnings=yes
 AC_ARG_ENABLE(warnings, [  --disable-warnings         Turn off compiler warnings (not recommended)],
 [if test $enableval = no; then
diff --git a/mh.c b/mh.c
index 17dbafc6a..aed3f8f75 100644
--- a/mh.c
+++ b/mh.c
@@ -30,6 +30,7 @@
 #include "sort.h"
 
 #include <sys/stat.h>
+#include <sys/types.h>
 #include <dirent.h>
 #include <limits.h>
 #include <unistd.h>
@@ -47,6 +48,9 @@ struct maildir
   HEADER *h;
   char *canon_fname;
   unsigned header_parsed:1;
+#ifdef USE_INODESORT
+  ino_t inode;
+#endif /* USE_INODESORT */
   struct maildir *next;
 };
 
@@ -626,7 +630,7 @@ static HEADER *maildir_parse_message (int magic, const char *fname,
 
 static int maildir_parse_entry (CONTEXT * ctx, struct maildir ***last,
 				const char *subdir, const char *fname,
-				int *count, int is_old)
+				int *count, int is_old, ino_t inode)
 {
   struct maildir *entry;
   HEADER *h = NULL;
@@ -666,6 +670,9 @@ static int maildir_parse_entry (CONTEXT * ctx, struct maildir ***last,
     entry = safe_calloc (sizeof (struct maildir), 1);
     entry->h = h;
     entry->header_parsed = (ctx->magic == M_MH);
+#ifdef USE_INODESORT
+    entry->inode = inode;
+#endif /* USE_INODESORT */
     **last = entry;
     *last = &entry->next;
 
@@ -723,7 +730,8 @@ static int maildir_parse_dir (CONTEXT * ctx, struct maildir ***last,
     dprint (2,
 	    (debugfile, "%s:%d: parsing %s\n", __FILE__, __LINE__,
 	     de->d_name));
-    maildir_parse_entry (ctx, last, subdir, de->d_name, count, is_old);
+    maildir_parse_entry (ctx, last, subdir, de->d_name, count, is_old, 
+			 de->d_ino);
   }
 
   closedir (dirp);
@@ -779,6 +787,96 @@ static int maildir_move_to_context (CONTEXT * ctx, struct maildir **md)
   return r;
 }
 
+#ifdef USE_INODESORT
+/*
+ * Merge two maildir lists according to the inode numbers.
+ */
+static struct maildir*  maildir_merge_inode (struct maildir *left,
+					     struct maildir *right)
+{
+  struct maildir* head;
+  struct maildir* tail;
+
+  if (left && right) 
+  {
+    if (left->inode < right->inode)
+    {
+      head = left;
+      left = left->next;
+    }
+    else 
+    {
+      head = right;
+      right = right->next;
+    }
+  } 
+  else 
+  {
+    if (left) 
+      return left;
+    else 
+      return right;
+  }
+    
+  tail = head;
+
+  while (left && right) 
+  {
+    if (left->inode < right->inode) 
+    {
+      tail->next = left;
+      left = left->next;
+    } 
+    else 
+    {
+      tail->next = right;
+      right = right->next;
+    }
+    tail = tail->next;
+  }
+
+  if (left) 
+  {
+    tail->next = left;
+  }
+  else
+  {
+    tail->next = right;
+  }
+
+  return head;
+}
+
+/*
+ * Sort maildir list according to inode.
+ */
+static struct maildir* maildir_sort_inode(struct maildir* list)
+{
+  struct maildir* left = list;
+  struct maildir* right = list;
+
+  if (!list || !list->next) 
+  {
+    return list;
+  }
+
+  list = list->next;
+  while (list && list->next) 
+  {
+    right = right->next;
+    list = list->next->next;
+  }
+
+  list = right;
+  right = right->next;
+  list->next = 0;
+
+  left = maildir_sort_inode(left);
+  right = maildir_sort_inode(right);
+  return maildir_merge_inode(left, right);
+}
+
+#endif /* USE_INODESORT */
 
 /* 
  * This function does the second parsing pass for a maildir-style
@@ -837,6 +935,10 @@ int mh_read_dir (CONTEXT * ctx, const char *subdir)
     mh_update_maildir (md, &mhs);
     mhs_free_sequences (&mhs);
   }
+#ifdef USE_INODESORT
+
+  md = maildir_sort_inode(md);
+#endif /* USE_INODESORT */
 
   if (ctx->magic == M_MAILDIR)
     maildir_delayed_parsing (ctx, md);
-- 
2.40.0