list_sort.c 6.7 KB
Newer Older
1 2 3

#define pr_fmt(fmt) "list_sort_test: " fmt

4 5 6 7 8 9
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/list_sort.h>
#include <linux/slab.h>
#include <linux/list.h>

D
Don Mullis 已提交
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
#define MAX_LIST_LENGTH_BITS 20

/*
 * Returns a list organized in an intermediate format suited
 * to chaining of merge() calls: null-terminated, no reserved or
 * sentinel head node, "prev" links not maintained.
 */
static struct list_head *merge(void *priv,
				int (*cmp)(void *priv, struct list_head *a,
					struct list_head *b),
				struct list_head *a, struct list_head *b)
{
	struct list_head head, *tail = &head;

	while (a && b) {
		/* if equal, take 'a' -- important for sort stability */
		if ((*cmp)(priv, a, b) <= 0) {
			tail->next = a;
			a = a->next;
		} else {
			tail->next = b;
			b = b->next;
		}
		tail = tail->next;
	}
	tail->next = a?:b;
	return head.next;
}

/*
 * Combine final list merge with restoration of standard doubly-linked
 * list structure.  This approach duplicates code from merge(), but
 * runs faster than the tidier alternatives of either a separate final
 * prev-link restoration pass, or maintaining the prev links
 * throughout.
 */
static void merge_and_restore_back_links(void *priv,
				int (*cmp)(void *priv, struct list_head *a,
					struct list_head *b),
				struct list_head *head,
				struct list_head *a, struct list_head *b)
{
	struct list_head *tail = head;
53
	u8 count = 0;
D
Don Mullis 已提交
54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

	while (a && b) {
		/* if equal, take 'a' -- important for sort stability */
		if ((*cmp)(priv, a, b) <= 0) {
			tail->next = a;
			a->prev = tail;
			a = a->next;
		} else {
			tail->next = b;
			b->prev = tail;
			b = b->next;
		}
		tail = tail->next;
	}
	tail->next = a ? : b;

	do {
		/*
		 * In worst cases this loop may run many iterations.
		 * Continue callbacks to the client even though no
		 * element comparison is needed, so the client's cmp()
		 * routine can invoke cond_resched() periodically.
		 */
77 78
		if (unlikely(!(++count)))
			(*cmp)(priv, tail->next, tail->next);
D
Don Mullis 已提交
79 80 81 82 83 84 85 86 87

		tail->next->prev = tail;
		tail = tail->next;
	} while (tail->next);

	tail->next = head;
	head->prev = tail;
}

88
/**
89 90
 * list_sort - sort a list
 * @priv: private data, opaque to list_sort(), passed to @cmp
91 92 93
 * @head: the list to sort
 * @cmp: the elements comparison function
 *
94 95
 * This function implements "merge sort", which has O(nlog(n))
 * complexity.
96
 *
97 98 99 100
 * The comparison function @cmp must return a negative value if @a
 * should sort before @b, and a positive value if @a should sort after
 * @b. If @a and @b are equivalent, and their original relative
 * ordering is to be preserved, @cmp must return 0.
101 102
 */
void list_sort(void *priv, struct list_head *head,
D
Don Mullis 已提交
103 104
		int (*cmp)(void *priv, struct list_head *a,
			struct list_head *b))
105
{
D
Don Mullis 已提交
106 107 108 109 110
	struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
						-- last slot is a sentinel */
	int lev;  /* index into part[] */
	int max_lev = 0;
	struct list_head *list;
111 112 113 114

	if (list_empty(head))
		return;

D
Don Mullis 已提交
115 116 117
	memset(part, 0, sizeof(part));

	head->prev->next = NULL;
118 119
	list = head->next;

D
Don Mullis 已提交
120 121 122 123 124 125 126 127 128 129 130
	while (list) {
		struct list_head *cur = list;
		list = list->next;
		cur->next = NULL;

		for (lev = 0; part[lev]; lev++) {
			cur = merge(priv, cmp, part[lev], cur);
			part[lev] = NULL;
		}
		if (lev > max_lev) {
			if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
131
				printk_once(KERN_DEBUG "list too long for efficiency\n");
D
Don Mullis 已提交
132
				lev--;
133
			}
D
Don Mullis 已提交
134
			max_lev = lev;
135
		}
D
Don Mullis 已提交
136 137
		part[lev] = cur;
	}
138

D
Don Mullis 已提交
139 140 141
	for (lev = 0; lev < max_lev; lev++)
		if (part[lev])
			list = merge(priv, cmp, part[lev], list);
142

D
Don Mullis 已提交
143 144 145
	merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
}
EXPORT_SYMBOL(list_sort);
146

147
#ifdef CONFIG_TEST_LIST_SORT
148 149 150

#include <linux/random.h>

151 152 153 154 155 156 157 158 159
/*
 * The pattern of set bits in the list length determines which cases
 * are hit in list_sort().
 */
#define TEST_LIST_LEN (512+128+2) /* not including head */

#define TEST_POISON1 0xDEADBEEF
#define TEST_POISON2 0xA324354C

D
Don Mullis 已提交
160
struct debug_el {
161
	unsigned int poison1;
162
	struct list_head list;
163
	unsigned int poison2;
D
Don Mullis 已提交
164 165 166
	int value;
	unsigned serial;
};
167

168 169 170 171
/* Array, containing pointers to all elements in the test list */
static struct debug_el **elts __initdata;

static int __init check(struct debug_el *ela, struct debug_el *elb)
D
Don Mullis 已提交
172
{
173
	if (ela->serial >= TEST_LIST_LEN) {
174
		pr_err("error: incorrect serial %d\n", ela->serial);
175 176 177
		return -EINVAL;
	}
	if (elb->serial >= TEST_LIST_LEN) {
178
		pr_err("error: incorrect serial %d\n", elb->serial);
179 180 181
		return -EINVAL;
	}
	if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
182
		pr_err("error: phantom element\n");
183 184 185
		return -EINVAL;
	}
	if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
186 187
		pr_err("error: bad poison: %#x/%#x\n",
			ela->poison1, ela->poison2);
188 189 190
		return -EINVAL;
	}
	if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
191 192
		pr_err("error: bad poison: %#x/%#x\n",
			elb->poison1, elb->poison2);
193 194 195
		return -EINVAL;
	}
	return 0;
196 197
}

198 199 200 201 202 203 204 205 206 207
static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
{
	struct debug_el *ela, *elb;

	ela = container_of(a, struct debug_el, list);
	elb = container_of(b, struct debug_el, list);

	check(ela, elb);
	return ela->value - elb->value;
}
D
Don Mullis 已提交
208 209 210

static int __init list_sort_test(void)
{
211
	int i, count = 1, err = -ENOMEM;
212
	struct debug_el *el;
213
	struct list_head *cur;
214
	LIST_HEAD(head);
D
Don Mullis 已提交
215

216
	pr_debug("start testing list_sort()\n");
D
Don Mullis 已提交
217

218
	elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
219
	if (!elts) {
220
		pr_err("error: cannot allocate memory\n");
221
		return err;
222 223
	}

224
	for (i = 0; i < TEST_LIST_LEN; i++) {
225 226
		el = kmalloc(sizeof(*el), GFP_KERNEL);
		if (!el) {
227
			pr_err("error: cannot allocate memory\n");
228 229
			goto exit;
		}
D
Don Mullis 已提交
230
		 /* force some equivalencies */
231
		el->value = prandom_u32() % (TEST_LIST_LEN / 3);
D
Don Mullis 已提交
232
		el->serial = i;
233 234 235
		el->poison1 = TEST_POISON1;
		el->poison2 = TEST_POISON2;
		elts[i] = el;
236
		list_add_tail(&el->list, &head);
D
Don Mullis 已提交
237 238
	}

239 240
	list_sort(NULL, &head, cmp);

241
	err = -EINVAL;
242 243 244
	for (cur = head.next; cur->next != &head; cur = cur->next) {
		struct debug_el *el1;
		int cmp_result;
D
Don Mullis 已提交
245 246

		if (cur->next->prev != cur) {
247
			pr_err("error: list is corrupted\n");
248 249 250 251 252
			goto exit;
		}

		cmp_result = cmp(NULL, cur, cur->next);
		if (cmp_result > 0) {
253
			pr_err("error: list is not sorted\n");
254 255 256 257 258 259
			goto exit;
		}

		el = container_of(cur, struct debug_el, list);
		el1 = container_of(cur->next, struct debug_el, list);
		if (cmp_result == 0 && el->serial >= el1->serial) {
260 261
			pr_err("error: order of equivalent elements not "
				"preserved\n");
262
			goto exit;
D
Don Mullis 已提交
263
		}
264 265

		if (check(el, el1)) {
266
			pr_err("error: element check failed\n");
267 268
			goto exit;
		}
D
Don Mullis 已提交
269 270
		count++;
	}
271
	if (head.prev != cur) {
272
		pr_err("error: list is corrupted\n");
273 274 275
		goto exit;
	}

276

277
	if (count != TEST_LIST_LEN) {
278
		pr_err("error: bad list length %d", count);
279 280 281 282 283
		goto exit;
	}

	err = 0;
exit:
284 285
	for (i = 0; i < TEST_LIST_LEN; i++)
		kfree(elts[i]);
286
	kfree(elts);
287
	return err;
D
Don Mullis 已提交
288 289
}
module_init(list_sort_test);
290
#endif /* CONFIG_TEST_LIST_SORT */