5 * Sort linked list in place.
6 * - get_next_fn() returns the next element given an element of a linked list.
7 * - set_next_fn() takes two elements A and B, and makes B the "next" element
9 * - compare_fn() takes two elements A and B, and returns negative, 0, positive
10 * as the same sign as "subtracting" B from A.
12 void *llist_mergesort(void *list
,
13 void *(*get_next_fn
)(const void *),
14 void (*set_next_fn
)(void *, void *),
15 int (*compare_fn
)(const void *, const void *));
17 /* Combine two sorted lists. Take from `list` on equality. */
18 #define DEFINE_LIST_MERGE_INTERNAL(name, type) \
19 static type *name##__merge(type *list, type *other, \
20 int (*compare_fn)(const type *, const type *))\
22 type *result = list, *tail; \
23 int prefer_list = compare_fn(list, other) <= 0; \
32 list = name##__get_next(list); \
34 name##__set_next(tail, other); \
37 } while (compare_fn(list, other) < prefer_list); \
38 name##__set_next(tail, other); \
45 * Perform an iterative mergesort using an array of sublists.
47 * n is the number of items.
48 * ranks[i] is undefined if n & 2^i == 0, and assumed empty.
49 * ranks[i] contains a sublist of length 2^i otherwise.
51 * The number of bits in a void pointer limits the number of objects
52 * that can be created, and thus the number of array elements necessary
53 * to be able to sort any valid list.
55 * Adding an item to this array is like incrementing a binary number;
56 * positional values for set bits correspond to sublist lengths.
58 #define DEFINE_LIST_SORT_INTERNAL(scope, name, type) \
59 scope void name(type **listp, \
60 int (*compare_fn)(const type *, const type *)) \
62 type *list = *listp; \
63 type *ranks[bitsizeof(type *)]; \
72 type *next = name##__get_next(list); \
74 name##__set_next(list, NULL); \
75 for (i = 0, m = n;; i++, m >>= 1) { \
77 list = name##__merge(ranks[i], list, \
92 #define DECLARE_LIST_SORT(scope, name, type) \
93 scope void name(type **listp, \
94 int (*compare_fn)(const type *, const type *))
96 #define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, \
97 on_get_next, on_set_next) \
99 static inline type *name##__get_next(const type *elem) \
102 return elem->next_member; \
105 static inline void name##__set_next(type *elem, type *next) \
108 elem->next_member = next; \
111 DEFINE_LIST_MERGE_INTERNAL(name, type) \
112 DEFINE_LIST_SORT_INTERNAL(scope, name, type) \
113 DECLARE_LIST_SORT(scope, name, type)
115 #define DEFINE_LIST_SORT(scope, name, type, next_member) \
116 DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)