Andrew's git - gitweb.git/blob

   1#include "cache.h"
   2#include "mergesort.h"
   3
   4struct mergesort_sublist {
   5        void *ptr;
   6        unsigned long len;
   7};
   8
   9static 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
  17static 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
  26void *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}