list_sort.c

Go to the documentation of this file.

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

#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;

    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.
         */
        (*cmp)(priv, tail->next, tail->next);

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

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

void list_sort(void *priv, struct list_head *head,
        int (*cmp)(void *priv, struct list_head *a,
            struct list_head *b))
{
    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;

    if (list_empty(head))
        return;

    memset(part, 0, sizeof(part));

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

    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)) {
                printk_once(KERN_DEBUG "list passed to"
                    " list_sort() too long for"
                    " efficiency\n");
                lev--;
            }
            max_lev = lev;
        }
        part[lev] = cur;
    }

    for (lev = 0; lev < max_lev; lev++)
        if (part[lev])
            list = merge(priv, cmp, part[lev], list);

    merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
}
EXPORT_SYMBOL(list_sort);

#ifdef CONFIG_TEST_LIST_SORT

#include <linux/random.h>

/*
 * 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

struct debug_el {
    unsigned int poison1;
    struct list_head list;
    unsigned int poison2;
    int value;
    unsigned serial;
};

/* 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)
{
    if (ela->serial >= TEST_LIST_LEN) {
        printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
                ela->serial);
        return -EINVAL;
    }
    if (elb->serial >= TEST_LIST_LEN) {
        printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
                elb->serial);
        return -EINVAL;
    }
    if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
        printk(KERN_ERR "list_sort_test: error: phantom element\n");
        return -EINVAL;
    }
    if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
        printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
                ela->poison1, ela->poison2);
        return -EINVAL;
    }
    if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
        printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
                elb->poison1, elb->poison2);
        return -EINVAL;
    }
    return 0;
}

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;
}

static int __init list_sort_test(void)
{
    int i, count = 1, err = -EINVAL;
    struct debug_el *el;
    struct list_head *cur, *tmp;
    LIST_HEAD(head);

    printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");

    elts = kmalloc(sizeof(void *) * TEST_LIST_LEN, GFP_KERNEL);
    if (!elts) {
        printk(KERN_ERR "list_sort_test: error: cannot allocate "
                "memory\n");
        goto exit;
    }

    for (i = 0; i < TEST_LIST_LEN; i++) {
        el = kmalloc(sizeof(*el), GFP_KERNEL);
        if (!el) {
            printk(KERN_ERR "list_sort_test: error: cannot "
                    "allocate memory\n");
            goto exit;
        }
         /* force some equivalencies */
        el->value = random32() % (TEST_LIST_LEN/3);
        el->serial = i;
        el->poison1 = TEST_POISON1;
        el->poison2 = TEST_POISON2;
        elts[i] = el;
        list_add_tail(&el->list, &head);
    }

    list_sort(NULL, &head, cmp);

    for (cur = head.next; cur->next != &head; cur = cur->next) {
        struct debug_el *el1;
        int cmp_result;

        if (cur->next->prev != cur) {
            printk(KERN_ERR "list_sort_test: error: list is "
                    "corrupted\n");
            goto exit;
        }

        cmp_result = cmp(NULL, cur, cur->next);
        if (cmp_result > 0) {
            printk(KERN_ERR "list_sort_test: error: list is not "
                    "sorted\n");
            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) {
            printk(KERN_ERR "list_sort_test: error: order of "
                    "equivalent elements not preserved\n");
            goto exit;
        }

        if (check(el, el1)) {
            printk(KERN_ERR "list_sort_test: error: element check "
                    "failed\n");
            goto exit;
        }
        count++;
    }

    if (count != TEST_LIST_LEN) {
        printk(KERN_ERR "list_sort_test: error: bad list length %d",
                count);
        goto exit;
    }

    err = 0;
exit:
    kfree(elts);
    list_for_each_safe(cur, tmp, &head) {
        list_del(cur);
        kfree(container_of(cur, struct debug_el, list));
    }
    return err;
}
module_init(list_sort_test);
#endif /* CONFIG_TEST_LIST_SORT */