diff options
author | Jonathan Maw <jonathan.maw@codethink.co.uk> | 2013-09-30 15:08:10 +0100 |
---|---|---|
committer | Jonathan Maw <jonathan.maw@codethink.co.uk> | 2013-09-30 15:08:10 +0100 |
commit | 43efcf42382e87de4aa423e5e1607958ad1717d0 (patch) | |
tree | 7e19a0765b0dd6885fbdf69d3a8d0159a1b42de8 /mergesort.c | |
parent | 45d74c4b0fe38218b4569a90da7102cf48d616c2 (diff) | |
parent | c7fd06b6411fb04eb4d9acd7f8822a288a50dc17 (diff) | |
download | git-43efcf42382e87de4aa423e5e1607958ad1717d0.tar.gz |
Merge branch 'baserock/jonathanmaw/S9007/upgrade-git' into baserock/morphbaserock/morph
Reviewed-by: Lars Wirzenius <lars.wirzenius@codethink.co.uk>
Reviewed-by: Daniel Silverstone <daniel.silverstone@codethink.co.uk>
Diffstat (limited to 'mergesort.c')
-rw-r--r-- | mergesort.c | 73 |
1 files changed, 73 insertions, 0 deletions
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; +} |