[linux.git] / lib / list_sort.c

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/list_sort.h>
#include <linux/slab.h>
#include <linux/list.h>

/**
 * list_sort - sort a list.
 * @priv: private data, passed to @cmp
 * @head: the list to sort
 * @cmp: the elements comparison function
 *
 * This function has been implemented by Mark J Roberts <[email protected]>. It
 * implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
 * in ascending order.
 *
 * The comparison function @cmp is supposed to return a negative value if @a is
 * less than @b, and a positive value if @a is greater than @b. If @a and @b
 * are equivalent, then it does not matter what this function returns.
 */
void list_sort(void *priv, struct list_head *head,
	       int (*cmp)(void *priv, struct list_head *a,
			  struct list_head *b))
{
	struct list_head *p, *q, *e, *list, *tail, *oldhead;
	int insize, nmerges, psize, qsize, i;

	if (list_empty(head))
		return;

	list = head->next;
	list_del(head);
	insize = 1;
	for (;;) {
		p = oldhead = list;
		list = tail = NULL;
		nmerges = 0;

		while (p) {
			nmerges++;
			q = p;
			psize = 0;
			for (i = 0; i < insize; i++) {
				psize++;
				q = q->next == oldhead ? NULL : q->next;
				if (!q)
					break;
			}

			qsize = insize;
			while (psize > 0 || (qsize > 0 && q)) {
				if (!psize) {
					e = q;
					q = q->next;
					qsize--;
					if (q == oldhead)
						q = NULL;
				} else if (!qsize || !q) {
					e = p;
					p = p->next;
					psize--;
					if (p == oldhead)
						p = NULL;
				} else if (cmp(priv, p, q) <= 0) {
					e = p;
					p = p->next;
					psize--;
					if (p == oldhead)
						p = NULL;
				} else {
					e = q;
					q = q->next;
					qsize--;
					if (q == oldhead)
						q = NULL;
				}
				if (tail)
					tail->next = e;
				else
					list = e;
				e->prev = tail;
				tail = e;
			}
			p = q;
		}

		tail->next = list;
		list->prev = tail;

		if (nmerges <= 1)
			break;

		insize *= 2;
	}

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

EXPORT_SYMBOL(list_sort);
Commit	Line	Data
2c761270 DC	1	#include <linux/kernel.h>
	2	#include <linux/module.h>
	3	#include <linux/list_sort.h>
	4	#include <linux/slab.h>
	5	#include <linux/list.h>
	6
	7	/**
	8	* list_sort - sort a list.
	9	* @priv: private data, passed to @cmp
	10	* @head: the list to sort
	11	* @cmp: the elements comparison function
	12	*
	13	* This function has been implemented by Mark J Roberts <[email protected]>. It
	14	* implements "merge sort" which has O(nlog(n)) complexity. The list is sorted
	15	* in ascending order.
	16	*
	17	* The comparison function @cmp is supposed to return a negative value if @a is
	18	* less than @b, and a positive value if @a is greater than @b. If @a and @b
	19	* are equivalent, then it does not matter what this function returns.
	20	*/
	21	void list_sort(void priv, struct list_head head,
	22	int (cmp)(void priv, struct list_head *a,
	23	struct list_head *b))
	24	{
	25	struct list_head p, q, e, list, tail, oldhead;
	26	int insize, nmerges, psize, qsize, i;
	27
	28	if (list_empty(head))
	29	return;
	30
	31	list = head->next;
	32	list_del(head);
	33	insize = 1;
	34	for (;;) {
	35	p = oldhead = list;
	36	list = tail = NULL;
	37	nmerges = 0;
	38
	39	while (p) {
	40	nmerges++;
	41	q = p;
	42	psize = 0;
	43	for (i = 0; i < insize; i++) {
	44	psize++;
	45	q = q->next == oldhead ? NULL : q->next;
	46	if (!q)
	47	break;
	48	}
	49
	50	qsize = insize;
	51	while (psize > 0 \|\| (qsize > 0 && q)) {
	52	if (!psize) {
	53	e = q;
	54	q = q->next;
	55	qsize--;
	56	if (q == oldhead)
	57	q = NULL;
	58	} else if (!qsize \|\| !q) {
	59	e = p;
	60	p = p->next;
	61	psize--;
	62	if (p == oldhead)
	63	p = NULL;
	64	} else if (cmp(priv, p, q) <= 0) {
65	e = p;
66	p = p->next;
67	psize--;
68	if (p == oldhead)
69	p = NULL;
70	} else {
71	e = q;
72	q = q->next;
73	qsize--;
74	if (q == oldhead)
75	q = NULL;
76	}
77	if (tail)
78	tail->next = e;
79	else
80	list = e;
81	e->prev = tail;
82	tail = e;
83	}
84	p = q;
85	}
86
87	tail->next = list;
88	list->prev = tail;
89
90	if (nmerges <= 1)
91	break;
92
93	insize *= 2;
94	}
95
96	head->next = list;
97	head->prev = list->prev;
98	list->prev->next = head;
99	list->prev = head;
100	}
101
102	EXPORT_SYMBOL(list_sort);