File: list_sort.c

package info (click to toggle)
cvsps 2.1-4
  • links: PTS
  • area: main
  • in suites: lenny
  • size: 352 kB
  • ctags: 402
  • sloc: ansic: 4,687; sh: 189; makefile: 77
file content (82 lines) | stat: -rw-r--r-- 1,280 bytes parent folder | download | duplicates (5)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
 * Copyright 2001, 2002, 2003 David Mansfield and Cobite, Inc.
 * See COPYING file for license information 
 */

#include <stdio.h>
#include <stdlib.h>
#include "list_sort.h"

void list_sort(struct list_head * list, int (*node_compare)(struct list_head *, struct list_head *))
{
    struct list_head *p, *q, *t;
    struct list_head tmp;
    int merges = 0;
    int k = 1;
    int psize, qsize; 

    if (list_empty(list))
	return;

    do
    {
	INIT_LIST_HEAD(&tmp);
	p = list->next;
	merges = 0;
	psize = qsize = 0;

	while (p != list)
	{
	    merges++;
	    q = p;

	    while (q != list && psize < k)
	    {
		q = q->next;
		psize++;
	    }
		
	    qsize = k;

	    while (psize || (qsize && q != list))
	    {
		if (psize && (qsize == 0 || q == list || node_compare(p, q) <= 0))
		{
		    t = p;
		    p = p->next;
		    psize--;
		}
		else if (qsize == 0)
		{
		    printf("whoaa. qsize is zero\n");
		    exit (1);
		}
		else
		{
		    t = q;
		    q = q->next;
		    qsize--;
		}
		
		list_del(t);
		
		list_add(t, tmp.prev);
	    }

	    p = q;
	}

	if (!list_empty(list))
	{
	    printf("whoaa. initial list not empty\n");
	    exit (1);
	}
	    
	list_splice(&tmp, list);
	k *= 2;

	//printf("done w sort pass %d %d\n", k, merges);
    }
    while (merges > 1);
}