Merge branch 'jk/index-pack-correct-depth-fix'
[git/jnareb-git.git] / mergesort.c
blobe5fdf2ee4ad9d42b069cfc8647b39ee271166087
1 #include "cache.h"
2 #include "mergesort.h"
4 struct mergesort_sublist {
5 void *ptr;
6 unsigned long len;
7 };
9 static void *get_nth_next(void *list, unsigned long n,
10 void *(*get_next_fn)(const void *))
12 while (n-- && list)
13 list = get_next_fn(list);
14 return list;
17 static void *pop_item(struct mergesort_sublist *l,
18 void *(*get_next_fn)(const void *))
20 void *p = l->ptr;
21 l->ptr = get_next_fn(l->ptr);
22 l->len = l->ptr ? (l->len - 1) : 0;
23 return p;
26 void *llist_mergesort(void *list,
27 void *(*get_next_fn)(const void *),
28 void (*set_next_fn)(void *, void *),
29 int (*compare_fn)(const void *, const void *))
31 unsigned long l;
33 if (!list)
34 return NULL;
35 for (l = 1; ; l *= 2) {
36 void *curr;
37 struct mergesort_sublist p, q;
39 p.ptr = list;
40 q.ptr = get_nth_next(p.ptr, l, get_next_fn);
41 if (!q.ptr)
42 break;
43 p.len = q.len = l;
45 if (compare_fn(p.ptr, q.ptr) > 0)
46 list = curr = pop_item(&q, get_next_fn);
47 else
48 list = curr = pop_item(&p, get_next_fn);
50 while (p.ptr) {
51 while (p.len || q.len) {
52 void *prev = curr;
54 if (!p.len)
55 curr = pop_item(&q, get_next_fn);
56 else if (!q.len)
57 curr = pop_item(&p, get_next_fn);
58 else if (compare_fn(p.ptr, q.ptr) > 0)
59 curr = pop_item(&q, get_next_fn);
60 else
61 curr = pop_item(&p, get_next_fn);
62 set_next_fn(prev, curr);
64 p.ptr = q.ptr;
65 p.len = l;
66 q.ptr = get_nth_next(p.ptr, l, get_next_fn);
67 q.len = q.ptr ? l : 0;
70 set_next_fn(curr, NULL);
72 return list;