list_sort.c 7.2 KB

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