blob: 19d11e0bb958a874fe7f560f25c75e392cd47aea [file] [log] [blame]
 #include #include #include #include #include /** * 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 . 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);