]>
git.ipfire.org Git - thirdparty/git.git/blob - mergesort.c
4 struct mergesort_sublist
{
9 static void *get_nth_next(void *list
, unsigned long n
,
10 void *(*get_next_fn
)(const void *))
13 list
= get_next_fn(list
);
17 static void *pop_item(struct mergesort_sublist
*l
,
18 void *(*get_next_fn
)(const void *))
21 l
->ptr
= get_next_fn(l
->ptr
);
22 l
->len
= l
->ptr
? (l
->len
- 1) : 0;
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 *))
35 for (l
= 1; ; l
*= 2) {
37 struct mergesort_sublist p
, q
;
40 q
.ptr
= get_nth_next(p
.ptr
, l
, get_next_fn
);
45 if (compare_fn(p
.ptr
, q
.ptr
) > 0)
46 list
= curr
= pop_item(&q
, get_next_fn
);
48 list
= curr
= pop_item(&p
, get_next_fn
);
51 while (p
.len
|| q
.len
) {
55 curr
= pop_item(&q
, get_next_fn
);
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
);
61 curr
= pop_item(&p
, get_next_fn
);
62 set_next_fn(prev
, curr
);
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
);