From 29b57c22fecb5bc0978937d6f557b7eff1897d56 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Mon, 18 Feb 2008 02:41:03 +0100 Subject: [PATCH] Speed up from O(n^2) to O(n). --- ChangeLog | 8 ++++++++ lib/git-merge-changelog.c | 3 ++- modules/git-merge-changelog | 1 + 3 files changed, 11 insertions(+), 1 deletion(-) diff --git a/ChangeLog b/ChangeLog index 5794b25bd..43c35a56f 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,13 @@ 2008-02-17 Bruno Haible + 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 + New option --split-merged-entry. * lib/git-merge-changelog.c (FSTRCMP_STRICTER_THRESHOLD): New macro. (find_paragraph_end, try_split_merged_entry): New functions. diff --git a/lib/git-merge-changelog.c b/lib/git-merge-changelog.c index 14893a477..022ac5c2d 100644 --- 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 @@ read_changelog_file (const char *filename, struct changelog_file *result) 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 index 6b3f9dcbe..70bc28194 100644 --- a/modules/git-merge-changelog +++ b/modules/git-merge-changelog @@ -14,6 +14,7 @@ list array-list linkedhash-list linked-list +rbtreehash-list xalloc xmalloca fstrcmp -- 2.11.0