aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.gitignore1
-rw-r--r--Makefile3
-rw-r--r--mergesort.c73
-rw-r--r--mergesort.h9
-rw-r--r--test-mergesort.c52
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
diff --git a/Makefile b/Makefile
index a78240930..330a7d5ae 100644
--- a/Makefile
+++ b/Makefile
@@ -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;
+}