list_sort.c 7.1 KB

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