mergesort.c

   1 #include "cache.h"
   2 #include "mergesort.h"
   3
   4 struct mergesort_sublist {
   5         void *ptr;
   6         unsigned long len;
   7 };
   8
   9 static void *get_nth_next(void *list, unsigned long n,
  10                           void *(*get_next_fn)(const void *))
  11 {
  12         while (n-- && list)
  13                 list = get_next_fn(list);
  14         return list;
  15 }
  16
  17 static void *pop_item(struct mergesort_sublist *l,
  18                       void *(*get_next_fn)(const void *))
  19 {
  20         void *p = l->ptr;
  21         l->ptr = get_next_fn(l->ptr);
  22         l->len = l->ptr ? (l->len - 1) : 0;
  23         return p;
  24 }
  25
  26 void *llist_mergesort(void *list,
  27                       void *(*get_next_fn)(const void *),
  28                       void (*set_next_fn)(void *, void *),
  29                       int (*compare_fn)(const void *, const void *))
  30 {
  31         unsigned long l;
  32
  33         if (!list)
  34                 return NULL;
  35         for (l = 1; ; l *= 2) {
  36                 void *curr;
  37                 struct mergesort_sublist p, q;
  38
  39                 p.ptr = list;
  40                 q.ptr = get_nth_next(p.ptr, l, get_next_fn);
  41                 if (!q.ptr)
  42                         break;
  43                 p.len = q.len = l;
  44
  45                 if (compare_fn(p.ptr, q.ptr) > 0)
  46                         list = curr = pop_item(&q, get_next_fn);
  47                 else
  48                         list = curr = pop_item(&p, get_next_fn);
  49
  50                 while (p.ptr) {
  51                         while (p.len || q.len) {
  52                                 void *prev = curr;
  53
  54                                 if (!p.len)
  55                                         curr = pop_item(&q, get_next_fn);
  56                                 else if (!q.len)
  57                                         curr = pop_item(&p, get_next_fn);
  58                                 else if (compare_fn(p.ptr, q.ptr) > 0)
  59                                         curr = pop_item(&q, get_next_fn);
  60                                 else
  61                                         curr = pop_item(&p, get_next_fn);
  62                                 set_next_fn(prev, curr);
  63                         }
  64                         p.ptr = q.ptr;
  65                         p.len = l;
  66                         q.ptr = get_nth_next(p.ptr, l, get_next_fn);
  67                         q.len = q.ptr ? l : 0;
  68
  69                 }
  70                 set_next_fn(curr, NULL);
  71         }
  72         return list;
  73 }