diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile | 3 | ||||
| -rw-r--r-- | commit.c | 44 | ||||
| -rw-r--r-- | commit.h | 1 | ||||
| -rw-r--r-- | mergesort.c | 73 | ||||
| -rw-r--r-- | mergesort.h | 17 | ||||
| -rw-r--r-- | revision.c | 4 | ||||
| -rw-r--r-- | test-mergesort.c | 52 |
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 @@ -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 @@ -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, @@ -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; +} |