Mercurial > hg > octave-shane > gnulib-hg
changeset 9712:a49ca512452c
Speed up from O(n^2) to O(n).
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Mon, 18 Feb 2008 02:41:03 +0100 |
| parents | 4e8a8a9b5391 |
| children | 9bd638fc6986 |
| files | ChangeLog lib/git-merge-changelog.c modules/git-merge-changelog |
| diffstat | 3 files changed, 11 insertions(+), 1 deletions(-) [+] |
line wrap: on
line diff
--- 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.
--- 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