mergesort.h

   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)                          \
   6 static 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)                    \
  46 scope 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)                    \
  80 scope 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                                                                 \
  86 static inline type *name##__get_next(const type *elem)          \
  87 {                                                               \
  88         on_get_next;                                            \
  89         return elem->next_member;                               \
  90 }                                                               \
  91                                                                 \
  92 static inline void name##__set_next(type *elem, type *next)     \
  93 {                                                               \
  94         on_set_next;                                            \
  95         elem->next_member = next;                               \
  96 }                                                               \
  97                                                                 \
  98 DEFINE_LIST_MERGE_INTERNAL(name, type)                          \
  99 DEFINE_LIST_SORT_INTERNAL(scope, name, type)                    \
 100 DECLARE_LIST_SORT(scope, name, type)
 101
 102 #define DEFINE_LIST_SORT(scope, name, type, next_member) \
 103 DEFINE_LIST_SORT_DEBUG(scope, name, type, next_member, (void)0, (void)0)
 104
 105 #endif