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