Subversion Repositories Kolibri OS

Rev

Rev 1412 | Rev 6934 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed

Rev 1412 Rev 5270
Line -... Line 1...
-
 
1
#define pr_fmt(fmt) "list_sort_test: " fmt
-
 
2
 
-
 
3
#include 
1
#include 
4
#include 
2
#include 
5
#include 
3
#include 
6
#include 
-
 
7
#include 
4
#include 
8
 
Line -... Line 9...
-
 
9
#define MAX_LIST_LENGTH_BITS 20
-
 
10
 
-
 
11
/*
-
 
12
 * Returns a list organized in an intermediate format suited
-
 
13
 * to chaining of merge() calls: null-terminated, no reserved or
-
 
14
 * sentinel head node, "prev" links not maintained.
-
 
15
 */
-
 
16
static struct list_head *merge(void *priv,
-
 
17
				int (*cmp)(void *priv, struct list_head *a,
-
 
18
					struct list_head *b),
-
 
19
				struct list_head *a, struct list_head *b)
-
 
20
{
-
 
21
	struct list_head head, *tail = &head;
-
 
22
 
-
 
23
	while (a && b) {
-
 
24
		/* if equal, take 'a' -- important for sort stability */
-
 
25
		if ((*cmp)(priv, a, b) <= 0) {
-
 
26
			tail->next = a;
-
 
27
			a = a->next;
-
 
28
		} else {
-
 
29
			tail->next = b;
-
 
30
			b = b->next;
-
 
31
		}
-
 
32
		tail = tail->next;
-
 
33
	}
-
 
34
	tail->next = a?:b;
-
 
35
	return head.next;
-
 
36
}
-
 
37
 
-
 
38
/*
-
 
39
 * Combine final list merge with restoration of standard doubly-linked
-
 
40
 * list structure.  This approach duplicates code from merge(), but
-
 
41
 * runs faster than the tidier alternatives of either a separate final
-
 
42
 * prev-link restoration pass, or maintaining the prev links
-
 
43
 * throughout.
-
 
44
 */
-
 
45
static void merge_and_restore_back_links(void *priv,
-
 
46
				int (*cmp)(void *priv, struct list_head *a,
-
 
47
					struct list_head *b),
-
 
48
				struct list_head *head,
-
 
49
				struct list_head *a, struct list_head *b)
-
 
50
{
-
 
51
	struct list_head *tail = head;
-
 
52
	u8 count = 0;
-
 
53
 
-
 
54
	while (a && b) {
-
 
55
		/* if equal, take 'a' -- important for sort stability */
-
 
56
		if ((*cmp)(priv, a, b) <= 0) {
-
 
57
			tail->next = a;
-
 
58
			a->prev = tail;
-
 
59
			a = a->next;
-
 
60
		} else {
-
 
61
			tail->next = b;
-
 
62
			b->prev = tail;
-
 
63
			b = b->next;
-
 
64
		}
-
 
65
		tail = tail->next;
-
 
66
	}
-
 
67
	tail->next = a ? : b;
-
 
68
 
-
 
69
	do {
-
 
70
		/*
-
 
71
		 * In worst cases this loop may run many iterations.
-
 
72
		 * Continue callbacks to the client even though no
-
 
73
		 * element comparison is needed, so the client's cmp()
-
 
74
		 * routine can invoke cond_resched() periodically.
-
 
75
		 */
-
 
76
		if (unlikely(!(++count)))
-
 
77
			(*cmp)(priv, tail->next, tail->next);
-
 
78
 
-
 
79
		tail->next->prev = tail;
-
 
80
		tail = tail->next;
-
 
81
	} while (tail->next);
-
 
82
 
-
 
83
	tail->next = head;
-
 
84
	head->prev = tail;
-
 
85
}
-
 
86
 
5
 
87
/**
6
/**
88
 * list_sort - sort a list
7
 * list_sort - sort a list.
89
 * @priv: private data, opaque to list_sort(), passed to @cmp
8
 * @priv: private data, passed to @cmp
90
 * @head: the list to sort
9
 * @head: the list to sort
91
 * @cmp: the elements comparison function
10
 * @cmp: the elements comparison function
92
 *
11
 *
93
 * This function implements "merge sort", which has O(nlog(n))
12
 * This function has been implemented by Mark J Roberts . It
-
 
13
 * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
94
 * complexity.
14
 * in ascending order.
95
 *
15
 *
96
 * The comparison function @cmp must return a negative value if @a
16
 * The comparison function @cmp is supposed to return a negative value if @a is
97
 * should sort before @b, and a positive value if @a should sort after
-
 
98
 * @b. If @a and @b are equivalent, and their original relative
17
 * less than @b, and a positive value if @a is greater than @b. If @a and @b
99
 * ordering is to be preserved, @cmp must return 0.
18
 * are equivalent, then it does not matter what this function returns.
100
 */
19
 */
101
void list_sort(void *priv, struct list_head *head,
20
void list_sort(void *priv, struct list_head *head,
102
	       int (*cmp)(void *priv, struct list_head *a,
21
	       int (*cmp)(void *priv, struct list_head *a,
103
			  struct list_head *b))
22
			  struct list_head *b))
104
{
23
{
105
	struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
-
 
106
						-- last slot is a sentinel */
24
	struct list_head *p, *q, *e, *list, *tail, *oldhead;
107
	int lev;  /* index into part[] */
-
 
108
	int max_lev = 0;
-
 
109
	struct list_head *list;
Line 25... Line 110...
25
	int insize, nmerges, psize, qsize, i;
110
 
26
 
111
	if (list_empty(head))
Line -... Line 112...
-
 
112
		return;
-
 
113
 
-
 
114
	memset(part, 0, sizeof(part));
27
	if (list_empty(head))
115
 
28
		return;
-
 
29
 
-
 
30
	list = head->next;
-
 
31
	list_del(head);
-
 
32
	insize = 1;
-
 
33
	for (;;) {
-
 
34
		p = oldhead = list;
116
	head->prev->next = NULL;
35
		list = tail = NULL;
117
	list = head->next;
36
		nmerges = 0;
-
 
37
 
-
 
38
		while (p) {
-
 
39
			nmerges++;
118
 
40
			q = p;
119
	while (list) {
41
			psize = 0;
120
		struct list_head *cur = list;
42
			for (i = 0; i < insize; i++) {
-
 
43
				psize++;
-
 
44
				q = q->next == oldhead ? NULL : q->next;
-
 
45
				if (!q)
121
		list = list->next;
46
					break;
-
 
47
			}
-
 
48
 
-
 
49
			qsize = insize;
-
 
50
			while (psize > 0 || (qsize > 0 && q)) {
-
 
51
				if (!psize) {
-
 
52
					e = q;
-
 
53
					q = q->next;
-
 
54
					qsize--;
122
		cur->next = NULL;
55
					if (q == oldhead)
-
 
56
						q = NULL;
-
 
57
				} else if (!qsize || !q) {
-
 
58
					e = p;
-
 
59
					p = p->next;
-
 
60
					psize--;
123
 
61
					if (p == oldhead)
-
 
62
						p = NULL;
-
 
63
				} else if (cmp(priv, p, q) <= 0) {
-
 
64
					e = p;
-
 
65
					p = p->next;
-
 
66
					psize--;
-
 
67
					if (p == oldhead)
-
 
68
						p = NULL;
-
 
69
				} else {
-
 
70
					e = q;
-
 
71
					q = q->next;
124
		for (lev = 0; part[lev]; lev++) {
72
					qsize--;
125
			cur = merge(priv, cmp, part[lev], cur);
73
					if (q == oldhead)
126
			part[lev] = NULL;
74
						q = NULL;
127
		}
75
				}
-
 
76
				if (tail)
-
 
77
					tail->next = e;
128
		if (lev > max_lev) {
78
				else
129
			if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
79
					list = e;
130
				printk_once(KERN_DEBUG "list too long for efficiency\n");
80
				e->prev = tail;
131
				lev--;
81
				tail = e;
132
				}
82
			}
-
 
83
			p = q;
-
 
84
		}
133
			max_lev = lev;
85
 
-
 
86
		tail->next = list;
-
 
87
		list->prev = tail;
-
 
88
 
-
 
89
		if (nmerges <= 1)
-
 
90
			break;
134
			}
Line 91... Line -...
91
 
-
 
92
		insize *= 2;
135
		part[lev] = cur;
93
	}
136
		}
94
 
137
 
95
	head->next = list;
-
 
Line -... Line 138...
-
 
138
	for (lev = 0; lev < max_lev; lev++)
-
 
139
		if (part[lev])
96
	head->prev = list->prev;
140
			list = merge(priv, cmp, part[lev], list);