Root/lib/list_sort.c

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#define MAX_LIST_LENGTH_BITS 20
8
9/*
10 * Returns a list organized in an intermediate format suited
11 * to chaining of merge() calls: null-terminated, no reserved or
12 * sentinel head node, "prev" links not maintained.
13 */
14static struct list_head *merge(void *priv,
15                int (*cmp)(void *priv, struct list_head *a,
16                    struct list_head *b),
17                struct list_head *a, struct list_head *b)
18{
19    struct list_head head, *tail = &head;
20
21    while (a && b) {
22        /* if equal, take 'a' -- important for sort stability */
23        if ((*cmp)(priv, a, b) <= 0) {
24            tail->next = a;
25            a = a->next;
26        } else {
27            tail->next = b;
28            b = b->next;
29        }
30        tail = tail->next;
31    }
32    tail->next = a?:b;
33    return head.next;
34}
35
36/*
37 * Combine final list merge with restoration of standard doubly-linked
38 * list structure. This approach duplicates code from merge(), but
39 * runs faster than the tidier alternatives of either a separate final
40 * prev-link restoration pass, or maintaining the prev links
41 * throughout.
42 */
43static void merge_and_restore_back_links(void *priv,
44                int (*cmp)(void *priv, struct list_head *a,
45                    struct list_head *b),
46                struct list_head *head,
47                struct list_head *a, struct list_head *b)
48{
49    struct list_head *tail = head;
50
51    while (a && b) {
52        /* if equal, take 'a' -- important for sort stability */
53        if ((*cmp)(priv, a, b) <= 0) {
54            tail->next = a;
55            a->prev = tail;
56            a = a->next;
57        } else {
58            tail->next = b;
59            b->prev = tail;
60            b = b->next;
61        }
62        tail = tail->next;
63    }
64    tail->next = a ? : b;
65
66    do {
67        /*
68         * In worst cases this loop may run many iterations.
69         * Continue callbacks to the client even though no
70         * element comparison is needed, so the client's cmp()
71         * routine can invoke cond_resched() periodically.
72         */
73        (*cmp)(priv, tail->next, tail->next);
74
75        tail->next->prev = tail;
76        tail = tail->next;
77    } while (tail->next);
78
79    tail->next = head;
80    head->prev = tail;
81}
82
83/**
84 * list_sort - sort a list
85 * @priv: private data, opaque to list_sort(), passed to @cmp
86 * @head: the list to sort
87 * @cmp: the elements comparison function
88 *
89 * This function implements "merge sort", which has O(nlog(n))
90 * complexity.
91 *
92 * The comparison function @cmp must return a negative value if @a
93 * should sort before @b, and a positive value if @a should sort after
94 * @b. If @a and @b are equivalent, and their original relative
95 * ordering is to be preserved, @cmp must return 0.
96 */
97void list_sort(void *priv, struct list_head *head,
98        int (*cmp)(void *priv, struct list_head *a,
99            struct list_head *b))
100{
101    struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
102                        -- last slot is a sentinel */
103    int lev; /* index into part[] */
104    int max_lev = 0;
105    struct list_head *list;
106
107    if (list_empty(head))
108        return;
109
110    memset(part, 0, sizeof(part));
111
112    head->prev->next = NULL;
113    list = head->next;
114
115    while (list) {
116        struct list_head *cur = list;
117        list = list->next;
118        cur->next = NULL;
119
120        for (lev = 0; part[lev]; lev++) {
121            cur = merge(priv, cmp, part[lev], cur);
122            part[lev] = NULL;
123        }
124        if (lev > max_lev) {
125            if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
126                printk_once(KERN_DEBUG "list passed to"
127                    " list_sort() too long for"
128                    " efficiency\n");
129                lev--;
130            }
131            max_lev = lev;
132        }
133        part[lev] = cur;
134    }
135
136    for (lev = 0; lev < max_lev; lev++)
137        if (part[lev])
138            list = merge(priv, cmp, part[lev], list);
139
140    merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
141}
142EXPORT_SYMBOL(list_sort);
143
144#ifdef DEBUG_LIST_SORT
145struct debug_el {
146    struct list_head l_h;
147    int value;
148    unsigned serial;
149};
150
151static int cmp(void *priv, struct list_head *a, struct list_head *b)
152{
153    return container_of(a, struct debug_el, l_h)->value
154         - container_of(b, struct debug_el, l_h)->value;
155}
156
157/*
158 * The pattern of set bits in the list length determines which cases
159 * are hit in list_sort().
160 */
161#define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */
162
163static int __init list_sort_test(void)
164{
165    int i, r = 1, count;
166    struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL);
167    struct list_head *cur;
168
169    printk(KERN_WARNING "testing list_sort()\n");
170
171    cur = head;
172    for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) {
173        struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL);
174        BUG_ON(!el);
175         /* force some equivalencies */
176        el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3);
177        el->serial = i;
178
179        el->l_h.prev = cur;
180        cur->next = &el->l_h;
181        cur = cur->next;
182    }
183    head->prev = cur;
184
185    list_sort(NULL, head, cmp);
186
187    count = 1;
188    for (cur = head->next; cur->next != head; cur = cur->next) {
189        struct debug_el *el = container_of(cur, struct debug_el, l_h);
190        int cmp_result = cmp(NULL, cur, cur->next);
191        if (cur->next->prev != cur) {
192            printk(KERN_EMERG "list_sort() returned "
193                        "a corrupted list!\n");
194            return 1;
195        } else if (cmp_result > 0) {
196            printk(KERN_EMERG "list_sort() failed to sort!\n");
197            return 1;
198        } else if (cmp_result == 0 &&
199                el->serial >= container_of(cur->next,
200                    struct debug_el, l_h)->serial) {
201            printk(KERN_EMERG "list_sort() failed to preserve order"
202                         " of equivalent elements!\n");
203            return 1;
204        }
205        kfree(cur->prev);
206        count++;
207    }
208    kfree(cur);
209    if (count != LIST_SORT_TEST_LENGTH) {
210        printk(KERN_EMERG "list_sort() returned list of"
211                        "different length!\n");
212        return 1;
213    }
214    return 0;
215}
216module_init(list_sort_test);
217#endif
218

Archive Download this file



interactive