Subversion Repositories Kolibri OS

Rev

Rev 6934 | Blame | Compare with Previous | Last modification | View Log | Download | RSS feed

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