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

diff --git a/.gitignore b/.gitignore
index 5a0782fe815a299a3a79ea15269aa6e0a7738a56..83a5c9df1b2c21e21be9375ac01be94c8dcf941a 100644 (file)
--- 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 172e924a29521886dc4d365302ee12ed73c357d5..f1caae8a827e7381df8226b36485409dfca71642 100644 (file)
--- 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 4b39c19123c7fa8584a67d5fd91e11f89e5816e4..b80a45281ccf4234b685954651db4249201e60db 100644 (file)
--- 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 154c0e34ff7d2dbaddcfb66b74d26697ffba6381..f8d250d6f64cacf463d7fd9525759978f008bcca 100644 (file)
--- 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 (file)
index 0000000..e5fdf2e
--- /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 (file)
index 0000000..644cff1
--- /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 b3554ed11b5c1a987c1d22b7851c91641bbf7f56..92095f5fcbb4454b3d605d2cdd6c9a1567498562 100644 (file)
--- 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 (file)
index 0000000..3f388b4
--- /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;
+}