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