Blame view
lib/list_sort.c
5.32 KB
2c761270d lib: Introduce ge... |
1 2 3 4 5 |
#include <linux/kernel.h> #include <linux/module.h> #include <linux/list_sort.h> #include <linux/slab.h> #include <linux/list.h> |
835cc0c84 lib: more scalabl... |
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 |
#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. */ |
f015ac3ed lib/list_sort: do... |
72 |
(*cmp)(priv, tail->next, tail->next); |
835cc0c84 lib: more scalabl... |
73 74 75 76 77 78 79 80 |
tail->next->prev = tail; tail = tail->next; } while (tail->next); tail->next = head; head->prev = tail; } |
2c761270d lib: Introduce ge... |
81 |
/** |
02b12b7a2 lib: revise list_... |
82 83 |
* list_sort - sort a list * @priv: private data, opaque to list_sort(), passed to @cmp |
2c761270d lib: Introduce ge... |
84 85 86 |
* @head: the list to sort * @cmp: the elements comparison function * |
02b12b7a2 lib: revise list_... |
87 88 |
* This function implements "merge sort", which has O(nlog(n)) * complexity. |
2c761270d lib: Introduce ge... |
89 |
* |
02b12b7a2 lib: revise list_... |
90 91 92 93 |
* The comparison function @cmp must return a negative value if @a * should sort before @b, and a positive value if @a should sort after * @b. If @a and @b are equivalent, and their original relative * ordering is to be preserved, @cmp must return 0. |
2c761270d lib: Introduce ge... |
94 95 |
*/ void list_sort(void *priv, struct list_head *head, |
835cc0c84 lib: more scalabl... |
96 97 |
int (*cmp)(void *priv, struct list_head *a, struct list_head *b)) |
2c761270d lib: Introduce ge... |
98 |
{ |
835cc0c84 lib: more scalabl... |
99 100 101 102 103 |
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; |
2c761270d lib: Introduce ge... |
104 105 106 |
if (list_empty(head)) return; |
835cc0c84 lib: more scalabl... |
107 108 109 |
memset(part, 0, sizeof(part)); head->prev->next = NULL; |
2c761270d lib: Introduce ge... |
110 |
list = head->next; |
2c761270d lib: Introduce ge... |
111 |
|
835cc0c84 lib: more scalabl... |
112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
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 "); lev--; |
2c761270d lib: Introduce ge... |
128 |
} |
835cc0c84 lib: more scalabl... |
129 |
max_lev = lev; |
2c761270d lib: Introduce ge... |
130 |
} |
835cc0c84 lib: more scalabl... |
131 132 |
part[lev] = cur; } |
2c761270d lib: Introduce ge... |
133 |
|
835cc0c84 lib: more scalabl... |
134 135 136 |
for (lev = 0; lev < max_lev; lev++) if (part[lev]) list = merge(priv, cmp, part[lev], list); |
2c761270d lib: Introduce ge... |
137 |
|
835cc0c84 lib: more scalabl... |
138 139 140 |
merge_and_restore_back_links(priv, cmp, head, part[max_lev], list); } EXPORT_SYMBOL(list_sort); |
2c761270d lib: Introduce ge... |
141 |
|
835cc0c84 lib: more scalabl... |
142 143 144 145 146 147 |
#ifdef DEBUG_LIST_SORT struct debug_el { struct list_head l_h; int value; unsigned serial; }; |
2c761270d lib: Introduce ge... |
148 |
|
835cc0c84 lib: more scalabl... |
149 150 151 152 |
static int cmp(void *priv, struct list_head *a, struct list_head *b) { return container_of(a, struct debug_el, l_h)->value - container_of(b, struct debug_el, l_h)->value; |
2c761270d lib: Introduce ge... |
153 |
} |
835cc0c84 lib: more scalabl... |
154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 |
/* * The pattern of set bits in the list length determines which cases * are hit in list_sort(). */ #define LIST_SORT_TEST_LENGTH (512+128+2) /* not including head */ static int __init list_sort_test(void) { int i, r = 1, count; struct list_head *head = kmalloc(sizeof(*head), GFP_KERNEL); struct list_head *cur; printk(KERN_WARNING "testing list_sort() "); cur = head; for (i = 0; i < LIST_SORT_TEST_LENGTH; i++) { struct debug_el *el = kmalloc(sizeof(*el), GFP_KERNEL); BUG_ON(!el); /* force some equivalencies */ el->value = (r = (r * 725861) % 6599) % (LIST_SORT_TEST_LENGTH/3); el->serial = i; el->l_h.prev = cur; cur->next = &el->l_h; cur = cur->next; } head->prev = cur; list_sort(NULL, head, cmp); count = 1; for (cur = head->next; cur->next != head; cur = cur->next) { struct debug_el *el = container_of(cur, struct debug_el, l_h); int cmp_result = cmp(NULL, cur, cur->next); if (cur->next->prev != cur) { printk(KERN_EMERG "list_sort() returned " "a corrupted list! "); return 1; } else if (cmp_result > 0) { printk(KERN_EMERG "list_sort() failed to sort! "); return 1; } else if (cmp_result == 0 && el->serial >= container_of(cur->next, struct debug_el, l_h)->serial) { printk(KERN_EMERG "list_sort() failed to preserve order" " of equivalent elements! "); return 1; } kfree(cur->prev); count++; } kfree(cur); if (count != LIST_SORT_TEST_LENGTH) { printk(KERN_EMERG "list_sort() returned list of" "different length! "); return 1; } return 0; } module_init(list_sort_test); #endif |