# HG changeset patch
# User Bruno Haible <bruno@clisp.org>
# Date 1203298863 -3600
# Node ID a49ca512452c40f3eeb98b09797bd15a9291fe18
# Parent  4e8a8a9b53918928871c86dec2950772e9f70a61
Speed up from O(n^2) to O(n).

diff --git a/ChangeLog b/ChangeLog
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,11 @@
+2008-02-17  Bruno Haible  <bruno@clisp.org>
+
+	Speed up from O(n^2) to O(n) for long ChangeLog files.
+	* lib/git-merge-changelog.c: Include gl_rbtreehash_list.h.
+	(read_changelog_file): Change implementation of entries_reversed list
+	to rbtreehash.
+	* modules/git-merge-changelog (Depends-on): Add rbtreehash-list.
+
 2008-02-17  Bruno Haible  <bruno@clisp.org>
 
 	New option --split-merged-entry.
diff --git a/lib/git-merge-changelog.c b/lib/git-merge-changelog.c
--- a/lib/git-merge-changelog.c
+++ b/lib/git-merge-changelog.c
@@ -133,6 +133,7 @@
 #include "gl_list.h"
 #include "gl_array_list.h"
 #include "gl_linkedhash_list.h"
+#include "gl_rbtreehash_list.h"
 #include "gl_linked_list.h"
 #include "xalloc.h"
 #include "xmalloca.h"
@@ -248,7 +249,7 @@
     gl_list_create_empty (GL_LINKEDHASH_LIST, entry_equals, entry_hashcode,
 			  NULL, true);
   result->entries_reversed =
-    gl_list_create_empty (GL_LINKEDHASH_LIST, entry_equals, entry_hashcode,
+    gl_list_create_empty (GL_RBTREEHASH_LIST, entry_equals, entry_hashcode,
 			  NULL, true);
   /* A ChangeLog file consists of ChangeLog entries.  A ChangeLog entry starts
      at a line following a blank line and that starts with a non-whitespace
diff --git a/modules/git-merge-changelog b/modules/git-merge-changelog
--- a/modules/git-merge-changelog
+++ b/modules/git-merge-changelog
@@ -14,6 +14,7 @@
 array-list
 linkedhash-list
 linked-list
+rbtreehash-list
 xalloc
 xmalloca
 fstrcmp