degrade-cvs_direct-failure.p
[cvsps/4msysgit.git] / list_sort.c
blob6c6f54c7bf9856c026afbafb3909d4e3e2b19740
1 /*
2 * Copyright 2001, 2002, 2003 David Mansfield and Cobite, Inc.
3 * See COPYING file for license information
4 */
6 #include <stdio.h>
7 #include <stdlib.h>
8 #include "list_sort.h"
10 void list_sort(struct list_head * list, int (*node_compare)(struct list_head *, struct list_head *))
12 struct list_head *p, *q, *t;
13 struct list_head tmp;
14 int merges = 0;
15 int k = 1;
16 int psize, qsize;
18 if (list_empty(list))
19 return;
23 INIT_LIST_HEAD(&tmp);
24 p = list->next;
25 merges = 0;
26 psize = qsize = 0;
28 while (p != list)
30 merges++;
31 q = p;
33 while (q != list && psize < k)
35 q = q->next;
36 psize++;
39 qsize = k;
41 while (psize || (qsize && q != list))
43 if (psize && (qsize == 0 || q == list || node_compare(p, q) <= 0))
45 t = p;
46 p = p->next;
47 psize--;
49 else if (qsize == 0)
51 printf("whoaa. qsize is zero\n");
52 exit (1);
54 else
56 t = q;
57 q = q->next;
58 qsize--;
61 list_del(t);
63 list_add(t, tmp.prev);
66 p = q;
69 if (!list_empty(list))
71 printf("whoaa. initial list not empty\n");
72 exit (1);
75 list_splice(&tmp, list);
76 k *= 2;
78 //printf("done w sort pass %d %d\n", k, merges);
80 while (merges > 1);