0,0 → 1,101 |
#include <linux/kernel.h> |
#include <linux/module.h> |
#include <linux/list_sort.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 <mjr@znex.org>. 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); |