[PATCH 04/15] lib/thread: sort child messages by date

[David Bremner <david@tethera.net>]

This will not should anything currently, as the child messages are
already added in date order. In the future we will add some messages
in a second pass out of order and the sorting will be useful.
---
 lib/message.cc        | 41 +++++++++++++++++++++++++++++++++++++++++
 lib/notmuch-private.h |  3 +++
 lib/thread.cc         |  9 +++++++++
 3 files changed, 53 insertions(+)

diff --git a/lib/message.cc b/lib/message.cc
index 153e4bed..107dcf35 100644
--- a/lib/message.cc
+++ b/lib/message.cc
@@ -588,6 +588,47 @@ _notmuch_message_add_reply (notmuch_message_t *message,
     _notmuch_message_list_add_message (message->replies, reply);
 }
 
+static int
+_cmpmsg (const void *pa, const void *pb)
+{
+    notmuch_message_t **a = (notmuch_message_t **) pa;
+    notmuch_message_t **b = (notmuch_message_t **) pb;
+    time_t time_a = notmuch_message_get_date (*a);
+    time_t time_b = notmuch_message_get_date (*b);
+
+    return (int) difftime (time_a, time_b);
+}
+
+void
+_notmuch_message_sort_subtree (notmuch_message_t *root)
+{
+    size_t child_count = 0;
+    size_t child_capacity = 16;
+    notmuch_message_t **children = talloc_zero_array (root, notmuch_message_t *, child_capacity);
+
+    for (notmuch_messages_t *messages = _notmuch_messages_create (root->replies);
+	 notmuch_messages_valid (messages);
+	 notmuch_messages_move_to_next (messages)) {
+	notmuch_message_t *child = notmuch_messages_get (messages);
+	if (child_count >= child_capacity) {
+	    child_capacity *= 2;
+	    children = talloc_realloc (root, children, notmuch_message_t *, child_capacity);
+	}
+	children[child_count++] = child;
+	_notmuch_message_sort_subtree (child);
+    }
+
+    notmuch_message_list_t *new_replies = _notmuch_message_list_create (root);
+
+    qsort (children, child_count, sizeof (notmuch_message_t *), _cmpmsg);
+    for (size_t i=0; i<child_count; i++){
+	_notmuch_message_list_add_message (new_replies, children[i]);
+    }
+    talloc_free (root->replies);
+    root->replies = new_replies;
+    talloc_free (children);
+}
+
 notmuch_messages_t *
 notmuch_message_get_replies (notmuch_message_t *message)
 {
diff --git a/lib/notmuch-private.h b/lib/notmuch-private.h
index 499d73d4..10bb7040 100644
--- a/lib/notmuch-private.h
+++ b/lib/notmuch-private.h
@@ -539,6 +539,9 @@ _notmuch_message_remove_unprefixed_terms (notmuch_message_t *message);
 const char *
 _notmuch_message_get_thread_id_only(notmuch_message_t *message);
 
+void
+_notmuch_message_sort_subtree (notmuch_message_t *message);
+
 /* sha1.c */
 
 char *
diff --git a/lib/thread.cc b/lib/thread.cc
index e961c76b..db592a3a 100644
--- a/lib/thread.cc
+++ b/lib/thread.cc
@@ -429,6 +429,15 @@ _resolve_thread_relationships (notmuch_thread_t *thread)
 	    _notmuch_message_list_add_message (thread->toplevel_list, message);
     }
 
+    for (notmuch_messages_t *messages = _notmuch_messages_create (thread->toplevel_list);
+	 notmuch_messages_valid (messages);
+	 notmuch_messages_move_to_next (messages))
+    {
+	notmuch_message_t *message = notmuch_messages_get (messages);
+	_notmuch_message_sort_subtree (message);
+    }
+
+
     /* XXX: After scanning through the entire list looking for parents
      * via "In-Reply-To", we should do a second pass that looks at the
      * list of messages IDs in the "References" header instead. (And
-- 
2.18.0