list_sort.c 7.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297
  1. #ifndef __UBOOT__
  2. #include <linux/kernel.h>
  3. #include <linux/module.h>
  4. #include <linux/slab.h>
  5. #else
  6. #include <linux/compat.h>
  7. #include <common.h>
  8. #include <malloc.h>
  9. #endif
  10. #include <linux/list.h>
  11. #include <linux/list_sort.h>
  12. #define MAX_LIST_LENGTH_BITS 20
  13. /*
  14. * Returns a list organized in an intermediate format suited
  15. * to chaining of merge() calls: null-terminated, no reserved or
  16. * sentinel head node, "prev" links not maintained.
  17. */
  18. static struct list_head *merge(void *priv,
  19. int (*cmp)(void *priv, struct list_head *a,
  20. struct list_head *b),
  21. struct list_head *a, struct list_head *b)
  22. {
  23. struct list_head head, *tail = &head;
  24. while (a && b) {
  25. /* if equal, take 'a' -- important for sort stability */
  26. if ((*cmp)(priv, a, b) <= 0) {
  27. tail->next = a;
  28. a = a->next;
  29. } else {
  30. tail->next = b;
  31. b = b->next;
  32. }
  33. tail = tail->next;
  34. }
  35. tail->next = a?:b;
  36. return head.next;
  37. }
  38. /*
  39. * Combine final list merge with restoration of standard doubly-linked
  40. * list structure. This approach duplicates code from merge(), but
  41. * runs faster than the tidier alternatives of either a separate final
  42. * prev-link restoration pass, or maintaining the prev links
  43. * throughout.
  44. */
  45. static void merge_and_restore_back_links(void *priv,
  46. int (*cmp)(void *priv, struct list_head *a,
  47. struct list_head *b),
  48. struct list_head *head,
  49. struct list_head *a, struct list_head *b)
  50. {
  51. struct list_head *tail = head;
  52. while (a && b) {
  53. /* if equal, take 'a' -- important for sort stability */
  54. if ((*cmp)(priv, a, b) <= 0) {
  55. tail->next = a;
  56. a->prev = tail;
  57. a = a->next;
  58. } else {
  59. tail->next = b;
  60. b->prev = tail;
  61. b = b->next;
  62. }
  63. tail = tail->next;
  64. }
  65. tail->next = a ? : b;
  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. tail->next->prev = tail;
  75. tail = tail->next;
  76. } while (tail->next);
  77. tail->next = head;
  78. head->prev = tail;
  79. }
  80. /**
  81. * list_sort - sort a list
  82. * @priv: private data, opaque to list_sort(), passed to @cmp
  83. * @head: the list to sort
  84. * @cmp: the elements comparison function
  85. *
  86. * This function implements "merge sort", which has O(nlog(n))
  87. * complexity.
  88. *
  89. * The comparison function @cmp must return a negative value if @a
  90. * should sort before @b, and a positive value if @a should sort after
  91. * @b. If @a and @b are equivalent, and their original relative
  92. * ordering is to be preserved, @cmp must return 0.
  93. */
  94. void list_sort(void *priv, struct list_head *head,
  95. int (*cmp)(void *priv, struct list_head *a,
  96. struct list_head *b))
  97. {
  98. struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
  99. -- last slot is a sentinel */
  100. int lev; /* index into part[] */
  101. int max_lev = 0;
  102. struct list_head *list;
  103. if (list_empty(head))
  104. return;
  105. memset(part, 0, sizeof(part));
  106. head->prev->next = NULL;
  107. list = head->next;
  108. while (list) {
  109. struct list_head *cur = list;
  110. list = list->next;
  111. cur->next = NULL;
  112. for (lev = 0; part[lev]; lev++) {
  113. cur = merge(priv, cmp, part[lev], cur);
  114. part[lev] = NULL;
  115. }
  116. if (lev > max_lev) {
  117. if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
  118. printk_once(KERN_DEBUG "list passed to"
  119. " list_sort() too long for"
  120. " efficiency\n");
  121. lev--;
  122. }
  123. max_lev = lev;
  124. }
  125. part[lev] = cur;
  126. }
  127. for (lev = 0; lev < max_lev; lev++)
  128. if (part[lev])
  129. list = merge(priv, cmp, part[lev], list);
  130. merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
  131. }
  132. EXPORT_SYMBOL(list_sort);
  133. #ifdef CONFIG_TEST_LIST_SORT
  134. #include <linux/random.h>
  135. /*
  136. * The pattern of set bits in the list length determines which cases
  137. * are hit in list_sort().
  138. */
  139. #define TEST_LIST_LEN (512+128+2) /* not including head */
  140. #define TEST_POISON1 0xDEADBEEF
  141. #define TEST_POISON2 0xA324354C
  142. struct debug_el {
  143. unsigned int poison1;
  144. struct list_head list;
  145. unsigned int poison2;
  146. int value;
  147. unsigned serial;
  148. };
  149. /* Array, containing pointers to all elements in the test list */
  150. static struct debug_el **elts __initdata;
  151. static int __init check(struct debug_el *ela, struct debug_el *elb)
  152. {
  153. if (ela->serial >= TEST_LIST_LEN) {
  154. printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
  155. ela->serial);
  156. return -EINVAL;
  157. }
  158. if (elb->serial >= TEST_LIST_LEN) {
  159. printk(KERN_ERR "list_sort_test: error: incorrect serial %d\n",
  160. elb->serial);
  161. return -EINVAL;
  162. }
  163. if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
  164. printk(KERN_ERR "list_sort_test: error: phantom element\n");
  165. return -EINVAL;
  166. }
  167. if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
  168. printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
  169. ela->poison1, ela->poison2);
  170. return -EINVAL;
  171. }
  172. if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
  173. printk(KERN_ERR "list_sort_test: error: bad poison: %#x/%#x\n",
  174. elb->poison1, elb->poison2);
  175. return -EINVAL;
  176. }
  177. return 0;
  178. }
  179. static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
  180. {
  181. struct debug_el *ela, *elb;
  182. ela = container_of(a, struct debug_el, list);
  183. elb = container_of(b, struct debug_el, list);
  184. check(ela, elb);
  185. return ela->value - elb->value;
  186. }
  187. static int __init list_sort_test(void)
  188. {
  189. int i, count = 1, err = -EINVAL;
  190. struct debug_el *el;
  191. struct list_head *cur, *tmp;
  192. LIST_HEAD(head);
  193. printk(KERN_DEBUG "list_sort_test: start testing list_sort()\n");
  194. elts = kmalloc(sizeof(void *) * TEST_LIST_LEN, GFP_KERNEL);
  195. if (!elts) {
  196. printk(KERN_ERR "list_sort_test: error: cannot allocate "
  197. "memory\n");
  198. goto exit;
  199. }
  200. for (i = 0; i < TEST_LIST_LEN; i++) {
  201. el = kmalloc(sizeof(*el), GFP_KERNEL);
  202. if (!el) {
  203. printk(KERN_ERR "list_sort_test: error: cannot "
  204. "allocate memory\n");
  205. goto exit;
  206. }
  207. /* force some equivalencies */
  208. el->value = prandom_u32() % (TEST_LIST_LEN / 3);
  209. el->serial = i;
  210. el->poison1 = TEST_POISON1;
  211. el->poison2 = TEST_POISON2;
  212. elts[i] = el;
  213. list_add_tail(&el->list, &head);
  214. }
  215. list_sort(NULL, &head, cmp);
  216. for (cur = head.next; cur->next != &head; cur = cur->next) {
  217. struct debug_el *el1;
  218. int cmp_result;
  219. if (cur->next->prev != cur) {
  220. printk(KERN_ERR "list_sort_test: error: list is "
  221. "corrupted\n");
  222. goto exit;
  223. }
  224. cmp_result = cmp(NULL, cur, cur->next);
  225. if (cmp_result > 0) {
  226. printk(KERN_ERR "list_sort_test: error: list is not "
  227. "sorted\n");
  228. goto exit;
  229. }
  230. el = container_of(cur, struct debug_el, list);
  231. el1 = container_of(cur->next, struct debug_el, list);
  232. if (cmp_result == 0 && el->serial >= el1->serial) {
  233. printk(KERN_ERR "list_sort_test: error: order of "
  234. "equivalent elements not preserved\n");
  235. goto exit;
  236. }
  237. if (check(el, el1)) {
  238. printk(KERN_ERR "list_sort_test: error: element check "
  239. "failed\n");
  240. goto exit;
  241. }
  242. count++;
  243. }
  244. if (count != TEST_LIST_LEN) {
  245. printk(KERN_ERR "list_sort_test: error: bad list length %d",
  246. count);
  247. goto exit;
  248. }
  249. err = 0;
  250. exit:
  251. kfree(elts);
  252. list_for_each_safe(cur, tmp, &head) {
  253. list_del(cur);
  254. kfree(container_of(cur, struct debug_el, list));
  255. }
  256. return err;
  257. }
  258. module_init(list_sort_test);
  259. #endif /* CONFIG_TEST_LIST_SORT */