summaryrefslogtreecommitdiff
path: root/mergesort.c
diff options
context:
space:
mode:
authorRené Scharfe <rene.scharfe@lsrfire.ath.cx>2012-04-01 00:10:11 +0200
committerJunio C Hamano <gitster@pobox.com>2012-04-11 08:50:53 -0700
commit0db71e0fa94c1857f98890928098e8f4c8ac6f26 (patch)
tree0095038b4c0b0c9d643380f479cb17db1dcd14a6 /mergesort.c
parent828ea97de486c1693d6e4f2c7347acb50235a85d (diff)
downloadgit-0db71e0fa94c1857f98890928098e8f4c8ac6f26.tar.gz
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 <rene.scharfe@lsrfire.ath.cx> Signed-off-by: Junio C Hamano <gitster@pobox.com>
Diffstat (limited to 'mergesort.c')
-rw-r--r--mergesort.c73
1 files changed, 73 insertions, 0 deletions
diff --git a/mergesort.c b/mergesort.c
new file mode 100644
index 0000000000..d084c602d5
--- /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;
+}