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
list_sort(struct list_head * list,int (* node_compare)(struct list_head *,struct list_head *))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
83