From 0db71e0fa94c1857f98890928098e8f4c8ac6f26 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Ren=C3=A9=20Scharfe?= Date: Sun, 1 Apr 2012 00:10:11 +0200 Subject: add mergesort() for linked lists This adds a generic bottom-up mergesort implementation for singly linked lists. It was inspired by Simon Tatham's webpage on the topic[1], but not so much by his implementation -- for no good reason, really, just a case of NIH. [1] http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano --- test-mergesort.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 52 insertions(+) create mode 100644 test-mergesort.c (limited to 'test-mergesort.c') diff --git a/test-mergesort.c b/test-mergesort.c new file mode 100644 index 0000000000..1dd82fd67f --- /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; +} -- cgit v1.2.3 From 7365c95d2d67cbbb74c2040918d2ecde06231d93 Mon Sep 17 00:00:00 2001 From: Junio C Hamano Date: Tue, 17 Apr 2012 11:07:01 -0700 Subject: mergesort: rename it to llist_mergesort() Even though the function is generic enough, sort() inherits connotations from the standard function qsort() that sorts an array. Rename it to llist_mergesort() and describe the external interface in its header file. This incidentally avoids name clashes with mergesort() some platforms declare in, and contaminate user namespace with, their . Reported-by: Brian Gernhardt Signed-off-by: Junio C Hamano --- test-mergesort.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'test-mergesort.c') diff --git a/test-mergesort.c b/test-mergesort.c index 1dd82fd67f..3f388b4ce0 100644 --- a/test-mergesort.c +++ b/test-mergesort.c @@ -42,7 +42,7 @@ int main(int argc, const char **argv) p = line; } - lines = mergesort(lines, get_next, set_next, compare_strings); + lines = llist_mergesort(lines, get_next, set_next, compare_strings); while (lines) { printf("%s", lines->text); -- cgit v1.2.3