summaryrefslogtreecommitdiff log msg author committer range
path: root/mergesort.h
blob: 7c36f08bd5f9668521ff993986b757b9766ec1c0 (plain)
 ```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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 ``` ``````#ifndef MERGESORT_H #define MERGESORT_H   /* Combine two sorted lists. Take from `list` on equality. */ #define DEFINE_LIST_MERGE_INTERNAL(name, type) \ static type *name##__merge(type *list, type *other, \ int (*compare_fn)(const type *, const type *))\ { \ type *result = list, *tail; \ int prefer_list = compare_fn(list, other) <= 0; \ \ if (!prefer_list) { \ result = other; \ SWAP(list, other); \ } \ for (;;) { \ do { \ tail = list; \ list = name##__get_next(list); \ if (!list) { \ name##__set_next(tail, other); \ return result; \ } \ } while (compare_fn(list, other) < prefer_list); \ name##__set_next(tail, other); \ prefer_list ^= 1; \ SWAP(list, other); \ } \ }   /* * 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. */ #define DEFINE_LIST_SORT_INTERNAL(scope, name, type) \ scope void name(type **listp, \ int (*compare_fn)(const type *, const type *)) \ { \ type *list = *listp; \ type *ranks[bitsizeof(type *)]; \ size_t n = 0; \ \ if (!list) \ return; \ \ for (;;) { \ int i; \ size_t m; \ type *next = name##__get_next(list); \ if (next) \ name##__set_next(list, NULL); \ for (i = 0, m = n;; i++, m >>= 1) { \ if (m & 1) { \ list = name##__merge(ranks[i], list, \ compare_fn); \ } else if (next) { \ break; \ } else if (!m) { \ *listp = list; \ return; \ } \ } \ n++; \ ranks[i] = list; \ list = next; \ } \ }   #define DECLARE_LIST_SORT(scope, name, type) \ scope void name(type **listp, \ int (*compare_fn)(const type *, const type *))   #define DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, \ on_get_next, on_set_next) \ \ static inline type *name##__get_next(const type *elem) \ { \ on_get_next; \ return elem->next_member; \ } \ \ static inline void name##__set_next(type *elem, type *next) \ { \ on_set_next; \ elem->next_member = next; \ } \ \ DEFINE_LIST_MERGE_INTERNAL(name, type) \ DEFINE_LIST_SORT_INTERNAL(scope, name, type) \ DECLARE_LIST_SORT(scope, name, type)   #define DEFINE_LIST_SORT(scope, name, type, next_member) \ DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)   #endif  ``````