1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include "cache.h"
#include "mergesort.h"
/* Combine two sorted lists. Take from `list` on equality. */
static void *llist_merge(void *list, void *other,
void *(*get_next_fn)(const void *),
void (*set_next_fn)(void *, void *),
int (*compare_fn)(const void *, const void *))
{
void *result = list, *tail;
if (compare_fn(list, other) > 0) {
result = other;
goto other;
}
for (;;) {
do {
tail = list;
list = get_next_fn(list);
if (!list) {
set_next_fn(tail, other);
return result;
}
} while (compare_fn(list, other) <= 0);
set_next_fn(tail, other);
other:
do {
tail = other;
other = get_next_fn(other);
if (!other) {
set_next_fn(tail, list);
return result;
}
} while (compare_fn(list, other) > 0);
set_next_fn(tail, list);
}
}
/*
* Perform an iterative mergesort using an array of sublists.
*
* n is the number of items.
* ranks[i] is undefined if n & 2^i == 0, and assumed empty.
* ranks[i] contains a sublist of length 2^i otherwise.
*
* The number of bits in a void pointer limits the number of objects
* that can be created, and thus the number of array elements necessary
* to be able to sort any valid list.
*
* Adding an item to this array is like incrementing a binary number;
* positional values for set bits correspond to sublist lengths.
*/
void *llist_mergesort(void *list,
void *(*get_next_fn)(const void *),
void (*set_next_fn)(void *, void *),
int (*compare_fn)(const void *, const void *))
{
void *ranks[bitsizeof(void *)];
size_t n = 0;
int i;
while (list) {
void *next = get_next_fn(list);
if (next)
set_next_fn(list, NULL);
for (i = 0; n & ((size_t)1 << i); i++)
list = llist_merge(ranks[i], list, get_next_fn,
set_next_fn, compare_fn);
n++;
ranks[i] = list;
list = next;
}
for (i = 0; n; i++, n >>= 1) {
if (!(n & 1))
continue;
if (list)
list = llist_merge(ranks[i], list, get_next_fn,
set_next_fn, compare_fn);
else
list = ranks[i];
}
return list;
}
|
