From afda9d0ed6428b3e54d6acf010e77f5f49184fae Mon Sep 17 00:00:00 2001
From: Petr Danecek <pd3@sanger.ac.uk>
Date: Mon, 15 Mar 2010 14:03:51 +0000
Subject: [PATCH] Fixed the order of sequences in the header

---
 sam_header.c | 24 +++++++++++++++++++++++-
 1 file changed, 23 insertions(+), 1 deletion(-)

diff --git a/sam_header.c b/sam_header.c
index 238c5cb..036ea88 100644
--- a/sam_header.c
+++ b/sam_header.c
@@ -10,6 +10,7 @@ KHASH_MAP_INIT_STR(str, const char *)
 
 struct _HeaderList
 {
+    struct _HeaderList *last;   // Hack: Used and maintained only by list_append_to_end. Maintained in the root node only.
     struct _HeaderList *next;
     void *data;
 };
@@ -58,6 +59,8 @@ static void debug(const char *format, ...)
     va_end(ap);
 }
 
+#if 0
+// Replaced by list_append_to_end
 static list_t *list_prepend(list_t *root, void *data)
 {
     list_t *l = malloc(sizeof(list_t));
@@ -65,6 +68,24 @@ static list_t *list_prepend(list_t *root, void *data)
     l->data = data;
     return l;
 }
+#endif
+
+// Relies on the root->last being correct. Do not use with the other list_*
+//  routines unless they are fixed to modify root->last as well.
+static list_t *list_append_to_end(list_t *root, void *data)
+{
+    list_t *l = malloc(sizeof(list_t));
+    l->last = l;
+    l->next = NULL;
+    l->data = data;
+
+    if ( !root )
+        return l;
+
+    root->last->next = l;
+    root->last = l;
+    return root;
+}
 
 static list_t *list_append(list_t *root, void *data)
 {
@@ -551,7 +572,8 @@ void *sam_header_parse2(const char *headerText)
     {
         hline = sam_header_line_parse(buf);
         if ( hline && sam_header_line_validate(hline) )
-            hlines = list_prepend(hlines, hline);
+            // With too many (~250,000) reference sequences the header parsing was too slow with list_append.
+            hlines = list_append_to_end(hlines, hline);
         else
         {
 			if (hline) sam_header_line_free(hline);
-- 
2.39.2