freshlybakedca.ke
Git fork
1#ifndef MERGESORT_H
2#define MERGESORT_H
3
4/* Combine two sorted lists. Take from `list` on equality. */
5#define DEFINE_LIST_MERGE_INTERNAL(name, type) \
6static type *name##__merge(type *list, type *other, \
7 int (*compare_fn)(const type *, const type *))\
8{ \
9 type *result = list, *tail; \
10 int prefer_list = compare_fn(list, other) <= 0; \
11 \
12 if (!prefer_list) { \
13 result = other; \
14 SWAP(list, other); \
15 } \
16 for (;;) { \
17 do { \
18 tail = list; \
19 list = name##__get_next(list); \
20 if (!list) { \
21 name##__set_next(tail, other); \
22 return result; \
23 } \
24 } while (compare_fn(list, other) < prefer_list); \
25 name##__set_next(tail, other); \
26 prefer_list ^= 1; \
27 SWAP(list, other); \
28 } \
29}
30
31/*
32 * Perform an iterative mergesort using an array of sublists.
33 *
34 * n is the number of items.
35 * ranks[i] is undefined if n & 2^i == 0, and assumed empty.
36 * ranks[i] contains a sublist of length 2^i otherwise.
37 *
38 * The number of bits in a void pointer limits the number of objects
39 * that can be created, and thus the number of array elements necessary
40 * to be able to sort any valid list.
41 *
42 * Adding an item to this array is like incrementing a binary number;
43 * positional values for set bits correspond to sublist lengths.
44 */
45#define DEFINE_LIST_SORT_INTERNAL(scope, name, type) \
46scope void name(type **listp, \
47 int (*compare_fn)(const type *, const type *)) \
48{ \
49 type *list = *listp; \
50 type *ranks[bitsizeof(type *)]; \
51 size_t n = 0; \
52 \
53 if (!list) \
54 return; \
55 \
56 for (;;) { \
57 int i; \
58 size_t m; \
59 type *next = name##__get_next(list); \
60 if (next) \
61 name##__set_next(list, NULL); \
62 for (i = 0, m = n;; i++, m >>= 1) { \
63 if (m & 1) { \
64 list = name##__merge(ranks[i], list, \
65 compare_fn); \
66 } else if (next) { \
67 break; \
68 } else if (!m) { \
69 *listp = list; \
70 return; \
71 } \
72 } \
73 n++; \
74 ranks[i] = list; \
75 list = next; \
76 } \
77}
78
79#define DECLARE_LIST_SORT(scope, name, type) \
80scope void name(type **listp, \
81 int (*compare_fn)(const type *, const type *))
82
83#define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, \
84 on_get_next, on_set_next) \
85 \
86static inline type *name##__get_next(const type *elem) \
87{ \
88 on_get_next; \
89 return elem->next_member; \
90} \
91 \
92static inline void name##__set_next(type *elem, type *next) \
93{ \
94 on_set_next; \
95 elem->next_member = next; \
96} \
97 \
98DEFINE_LIST_MERGE_INTERNAL(name, type) \
99DEFINE_LIST_SORT_INTERNAL(scope, name, type) \
100DECLARE_LIST_SORT(scope, name, type)
101
102#define DEFINE_LIST_SORT(scope, name, type, next_member) \
103DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)
104
105#endif