summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorLibravatar Junio C Hamano <gitster@pobox.com>2012-04-23 12:52:54 -0700
committerLibravatar Junio C Hamano <gitster@pobox.com>2012-04-23 12:52:55 -0700
commitba8e6326f16748d67fbeda65ffde4729760c64f0 (patch)
treecfd553f836c093db7d9f495127d972c688a398b0
parentMerge branch 'jh/apply-free-patch' (diff)
parentmergesort: rename it to llist_mergesort() (diff)
downloadtgif-ba8e6326f16748d67fbeda65ffde4729760c64f0.tar.xz
Merge branch 'rs/commit-list-sort-in-batch'
Setting up a revision traversal with many starting points was inefficient as these were placed in a date-order priority queue one-by-one. By René Scharfe (3) and Junio C Hamano (1) * rs/commit-list-sort-in-batch: mergesort: rename it to llist_mergesort() revision: insert unsorted, then sort in prepare_revision_walk() commit: use mergesort() in commit_list_sort_by_date() add mergesort() for linked lists
-rw-r--r--.gitignore1
-rw-r--r--Makefile3
-rw-r--r--commit.c44
-rw-r--r--commit.h1
-rw-r--r--mergesort.c73
-rw-r--r--mergesort.h17
-rw-r--r--revision.c4
-rw-r--r--test-mergesort.c52
8 files changed, 188 insertions, 7 deletions
diff --git a/.gitignore b/.gitignore
index 5a0782fe81..83a5c9df1b 100644
--- a/.gitignore
+++ b/.gitignore
@@ -181,6 +181,7 @@
/test-index-version
/test-line-buffer
/test-match-trees
+/test-mergesort
/test-mktemp
/test-parse-options
/test-path-utils
diff --git a/Makefile b/Makefile
index 172e924a29..f1caae8a82 100644
--- a/Makefile
+++ b/Makefile
@@ -481,6 +481,7 @@ TEST_PROGRAMS_NEED_X += test-genrandom
TEST_PROGRAMS_NEED_X += test-index-version
TEST_PROGRAMS_NEED_X += test-line-buffer
TEST_PROGRAMS_NEED_X += test-match-trees
+TEST_PROGRAMS_NEED_X += test-mergesort
TEST_PROGRAMS_NEED_X += test-mktemp
TEST_PROGRAMS_NEED_X += test-parse-options
TEST_PROGRAMS_NEED_X += test-path-utils
@@ -591,6 +592,7 @@ LIB_H += log-tree.h
LIB_H += mailmap.h
LIB_H += merge-file.h
LIB_H += merge-recursive.h
+LIB_H += mergesort.h
LIB_H += notes.h
LIB_H += notes-cache.h
LIB_H += notes-merge.h
@@ -695,6 +697,7 @@ LIB_OBJS += mailmap.o
LIB_OBJS += match-trees.o
LIB_OBJS += merge-file.o
LIB_OBJS += merge-recursive.o
+LIB_OBJS += mergesort.o
LIB_OBJS += name-hash.o
LIB_OBJS += notes.o
LIB_OBJS += notes-cache.o
diff --git a/commit.c b/commit.c
index 4b39c19123..b80a45281c 100644
--- a/commit.c
+++ b/commit.c
@@ -7,6 +7,7 @@
#include "revision.h"
#include "notes.h"
#include "gpg-interface.h"
+#include "mergesort.h"
int save_commit_buffer = 1;
@@ -360,6 +361,21 @@ struct commit_list *commit_list_insert(struct commit *item, struct commit_list *
return new_list;
}
+void commit_list_reverse(struct commit_list **list_p)
+{
+ struct commit_list *prev = NULL, *curr = *list_p, *next;
+
+ if (!list_p)
+ return;
+ while (curr) {
+ next = curr->next;
+ curr->next = prev;
+ prev = curr;
+ curr = next;
+ }
+ *list_p = prev;
+}
+
unsigned commit_list_count(const struct commit_list *l)
{
unsigned c = 0;
@@ -390,15 +406,31 @@ struct commit_list * commit_list_insert_by_date(struct commit *item, struct comm
return commit_list_insert(item, pp);
}
+static int commit_list_compare_by_date(const void *a, const void *b)
+{
+ unsigned long a_date = ((const struct commit_list *)a)->item->date;
+ unsigned long b_date = ((const struct commit_list *)b)->item->date;
+ if (a_date < b_date)
+ return 1;
+ if (a_date > b_date)
+ return -1;
+ return 0;
+}
+
+static void *commit_list_get_next(const void *a)
+{
+ return ((const struct commit_list *)a)->next;
+}
+
+static void commit_list_set_next(void *a, void *next)
+{
+ ((struct commit_list *)a)->next = next;
+}
void commit_list_sort_by_date(struct commit_list **list)
{
- struct commit_list *ret = NULL;
- while (*list) {
- commit_list_insert_by_date((*list)->item, &ret);
- *list = (*list)->next;
- }
- *list = ret;
+ *list = llist_mergesort(*list, commit_list_get_next, commit_list_set_next,
+ commit_list_compare_by_date);
}
struct commit *pop_most_recent_commit(struct commit_list **list,
diff --git a/commit.h b/commit.h
index 154c0e34ff..f8d250d6f6 100644
--- a/commit.h
+++ b/commit.h
@@ -57,6 +57,7 @@ unsigned commit_list_count(const struct commit_list *l);
struct commit_list *commit_list_insert_by_date(struct commit *item,
struct commit_list **list);
void commit_list_sort_by_date(struct commit_list **list);
+void commit_list_reverse(struct commit_list **list_p);
void free_commit_list(struct commit_list *list);
diff --git a/mergesort.c b/mergesort.c
new file mode 100644
index 0000000000..e5fdf2ee4a
--- /dev/null
+++ b/mergesort.c
@@ -0,0 +1,73 @@
+#include "cache.h"
+#include "mergesort.h"
+
+struct mergesort_sublist {
+ void *ptr;
+ unsigned long len;
+};
+
+static void *get_nth_next(void *list, unsigned long n,
+ void *(*get_next_fn)(const void *))
+{
+ while (n-- && list)
+ list = get_next_fn(list);
+ return list;
+}
+
+static void *pop_item(struct mergesort_sublist *l,
+ void *(*get_next_fn)(const void *))
+{
+ void *p = l->ptr;
+ l->ptr = get_next_fn(l->ptr);
+ l->len = l->ptr ? (l->len - 1) : 0;
+ return p;
+}
+
+void *llist_mergesort(void *list,
+ void *(*get_next_fn)(const void *),
+ void (*set_next_fn)(void *, void *),
+ int (*compare_fn)(const void *, const void *))
+{
+ unsigned long l;
+
+ if (!list)
+ return NULL;
+ for (l = 1; ; l *= 2) {
+ void *curr;
+ struct mergesort_sublist p, q;
+
+ p.ptr = list;
+ q.ptr = get_nth_next(p.ptr, l, get_next_fn);
+ if (!q.ptr)
+ break;
+ p.len = q.len = l;
+
+ if (compare_fn(p.ptr, q.ptr) > 0)
+ list = curr = pop_item(&q, get_next_fn);
+ else
+ list = curr = pop_item(&p, get_next_fn);
+
+ while (p.ptr) {
+ while (p.len || q.len) {
+ void *prev = curr;
+
+ if (!p.len)
+ curr = pop_item(&q, get_next_fn);
+ else if (!q.len)
+ curr = pop_item(&p, get_next_fn);
+ else if (compare_fn(p.ptr, q.ptr) > 0)
+ curr = pop_item(&q, get_next_fn);
+ else
+ curr = pop_item(&p, get_next_fn);
+ set_next_fn(prev, curr);
+ }
+ p.ptr = q.ptr;
+ p.len = l;
+ q.ptr = get_nth_next(p.ptr, l, get_next_fn);
+ q.len = q.ptr ? l : 0;
+
+ }
+ set_next_fn(curr, NULL);
+ }
+ return list;
+}
diff --git a/mergesort.h b/mergesort.h
new file mode 100644
index 0000000000..644cff1f96
--- /dev/null
+++ b/mergesort.h
@@ -0,0 +1,17 @@
+#ifndef MERGESORT_H
+#define MERGESORT_H
+
+/*
+ * Sort linked list in place.
+ * - get_next_fn() returns the next element given an element of a linked list.
+ * - set_next_fn() takes two elements A and B, and makes B the "next" element
+ * of A on the list.
+ * - compare_fn() takes two elements A and B, and returns negative, 0, positive
+ * as the same sign as "subtracting" B from A.
+ */
+void *llist_mergesort(void *list,
+ void *(*get_next_fn)(const void *),
+ void (*set_next_fn)(void *, void *),
+ int (*compare_fn)(const void *, const void *));
+
+#endif
diff --git a/revision.c b/revision.c
index b3554ed11b..92095f5fcb 100644
--- a/revision.c
+++ b/revision.c
@@ -2076,11 +2076,13 @@ int prepare_revision_walk(struct rev_info *revs)
if (commit) {
if (!(commit->object.flags & SEEN)) {
commit->object.flags |= SEEN;
- commit_list_insert_by_date(commit, &revs->commits);
+ commit_list_insert(commit, &revs->commits);
}
}
e++;
}
+ commit_list_reverse(&revs->commits);
+ commit_list_sort_by_date(&revs->commits);
if (!revs->leak_pending)
free(list);
diff --git a/test-mergesort.c b/test-mergesort.c
new file mode 100644
index 0000000000..3f388b4ce0
--- /dev/null
+++ b/test-mergesort.c
@@ -0,0 +1,52 @@
+#include "cache.h"
+#include "mergesort.h"
+
+struct line {
+ char *text;
+ struct line *next;
+};
+
+static void *get_next(const void *a)
+{
+ return ((const struct line *)a)->next;
+}
+
+static void set_next(void *a, void *b)
+{
+ ((struct line *)a)->next = b;
+}
+
+static int compare_strings(const void *a, const void *b)
+{
+ const struct line *x = a, *y = b;
+ return strcmp(x->text, y->text);
+}
+
+int main(int argc, const char **argv)
+{
+ struct line *line, *p = NULL, *lines = NULL;
+ struct strbuf sb = STRBUF_INIT;
+
+ for (;;) {
+ if (strbuf_getwholeline(&sb, stdin, '\n'))
+ break;
+ line = xmalloc(sizeof(struct line));
+ line->text = strbuf_detach(&sb, NULL);
+ if (p) {
+ line->next = p->next;
+ p->next = line;
+ } else {
+ line->next = NULL;
+ lines = line;
+ }
+ p = line;
+ }
+
+ lines = llist_mergesort(lines, get_next, set_next, compare_strings);
+
+ while (lines) {
+ printf("%s", lines->text);
+ lines = lines->next;
+ }
+ return 0;
+}