t7201.24: Add refspec to keep --track working
[git] / mergesort.c
1 #include "cache.h"
2 #include "mergesort.h"
3
4 struct mergesort_sublist {
5         void *ptr;
6         unsigned long len;
7 };
8
9 static void *get_nth_next(void *list, unsigned long n,
10                           void *(*get_next_fn)(const void *))
11 {
12         while (n-- && list)
13                 list = get_next_fn(list);
14         return list;
15 }
16
17 static void *pop_item(struct mergesort_sublist *l,
18                       void *(*get_next_fn)(const void *))
19 {
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;
24 }
25
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 *))
30 {
31         unsigned long l;
32
33         if (!list)
34                 return NULL;
35         for (l = 1; ; l *= 2) {
36                 void *curr;
37                 struct mergesort_sublist p, q;
38
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;
44
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);
49
50                 while (p.ptr) {
51                         while (p.len || q.len) {
52                                 void *prev = curr;
53
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);
63                         }
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;
68
69                 }
70                 set_next_fn(curr, NULL);
71         }
72         return list;
73 }