Skip to content
Newer
Older
100644 74 lines (63 sloc) 1.48 KB
0db71e0 add mergesort() for linked lists
René Scharfe authored
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
7365c95 @gitster mergesort: rename it to llist_mergesort()
gitster authored
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 *))
0db71e0 add mergesort() for linked lists
René Scharfe authored
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 }
Something went wrong with that request. Please try again.