mergesort.c

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