diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | Makefile | 3 | ||||
| -rw-r--r-- | mergesort.c | 73 | ||||
| -rw-r--r-- | mergesort.h | 9 | ||||
| -rw-r--r-- | test-mergesort.c | 52 |
5 files changed, 138 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore index 3b7680ea1..1787c8185 100644 --- a/.gitignore +++ b/.gitignore @@ -180,6 +180,7 @@ /test-index-version /test-line-buffer /test-match-trees +/test-mergesort /test-mktemp /test-obj-pool /test-parse-options @@ -465,6 +465,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-obj-pool TEST_PROGRAMS_NEED_X += test-parse-options @@ -578,6 +579,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 @@ -681,6 +683,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/mergesort.c b/mergesort.c new file mode 100644 index 000000000..d084c602d --- /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 *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 000000000..d6e5f4a73 --- /dev/null +++ b/mergesort.h @@ -0,0 +1,9 @@ +#ifndef MERGESORT_H +#define MERGESORT_H + +void *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/test-mergesort.c b/test-mergesort.c new file mode 100644 index 000000000..1dd82fd67 --- /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 = mergesort(lines, get_next, set_next, compare_strings); + + while (lines) { + printf("%s", lines->text); + lines = lines->next; + } + return 0; +} |