list_sort.c

   1 /*
   2  * Copyright 2001, 2002, 2003 David Mansfield and Cobite, Inc.
   3  * See COPYING file for license information
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8 #include "list_sort.h"
   9
  10 void list_sort(struct list_head * list, int (*node_compare)(struct list_head *, struct list_head *))
  11 {
  12     struct list_head *p, *q, *t;
  13     struct list_head tmp;
  14     int merges = 0;
  15     int k = 1;
  16     int psize, qsize;
  17
  18     if (list_empty(list))
  19         return;
  20
  21     do
  22     {
  23         INIT_LIST_HEAD(&tmp);
  24         p = list->next;
  25         merges = 0;
  26         psize = qsize = 0;
  27
  28         while (p != list)
  29         {
  30             merges++;
  31             q = p;
  32
  33             while (q != list && psize < k)
  34             {
  35                 q = q->next;
  36                 psize++;
  37             }
  38
  39             qsize = k;
  40
  41             while (psize || (qsize && q != list))
  42             {
  43                 if (psize && (qsize == 0 || q == list || node_compare(p, q) <= 0))
  44                 {
  45                     t = p;
  46                     p = p->next;
  47                     psize--;
  48                 }
  49                 else if (qsize == 0)
  50                 {
  51                     printf("whoaa. qsize is zero\n");
  52                     exit (1);
  53                 }
  54                 else
  55                 {
  56                     t = q;
  57                     q = q->next;
  58                     qsize--;
  59                 }
  60
  61                 list_del(t);
  62
  63                 list_add(t, tmp.prev);
  64             }
  65
  66             p = q;
  67         }
  68
  69         if (!list_empty(list))
  70         {
  71             printf("whoaa. initial list not empty\n");
  72             exit (1);
  73         }
  74
  75         list_splice(&tmp, list);
  76         k *= 2;
  77
  78         //printf("done w sort pass %d %d\n", k, merges);
  79     }
  80     while (merges > 1);
  81 }
  82