Back to home page

LXR

 
 

    


0001 
0002 #define pr_fmt(fmt) "list_sort_test: " fmt
0003 
0004 #include <linux/kernel.h>
0005 #include <linux/bug.h>
0006 #include <linux/compiler.h>
0007 #include <linux/export.h>
0008 #include <linux/string.h>
0009 #include <linux/list_sort.h>
0010 #include <linux/list.h>
0011 
0012 #define MAX_LIST_LENGTH_BITS 20
0013 
0014 /*
0015  * Returns a list organized in an intermediate format suited
0016  * to chaining of merge() calls: null-terminated, no reserved or
0017  * sentinel head node, "prev" links not maintained.
0018  */
0019 static struct list_head *merge(void *priv,
0020                 int (*cmp)(void *priv, struct list_head *a,
0021                     struct list_head *b),
0022                 struct list_head *a, struct list_head *b)
0023 {
0024     struct list_head head, *tail = &head;
0025 
0026     while (a && b) {
0027         /* if equal, take 'a' -- important for sort stability */
0028         if ((*cmp)(priv, a, b) <= 0) {
0029             tail->next = a;
0030             a = a->next;
0031         } else {
0032             tail->next = b;
0033             b = b->next;
0034         }
0035         tail = tail->next;
0036     }
0037     tail->next = a?:b;
0038     return head.next;
0039 }
0040 
0041 /*
0042  * Combine final list merge with restoration of standard doubly-linked
0043  * list structure.  This approach duplicates code from merge(), but
0044  * runs faster than the tidier alternatives of either a separate final
0045  * prev-link restoration pass, or maintaining the prev links
0046  * throughout.
0047  */
0048 static void merge_and_restore_back_links(void *priv,
0049                 int (*cmp)(void *priv, struct list_head *a,
0050                     struct list_head *b),
0051                 struct list_head *head,
0052                 struct list_head *a, struct list_head *b)
0053 {
0054     struct list_head *tail = head;
0055     u8 count = 0;
0056 
0057     while (a && b) {
0058         /* if equal, take 'a' -- important for sort stability */
0059         if ((*cmp)(priv, a, b) <= 0) {
0060             tail->next = a;
0061             a->prev = tail;
0062             a = a->next;
0063         } else {
0064             tail->next = b;
0065             b->prev = tail;
0066             b = b->next;
0067         }
0068         tail = tail->next;
0069     }
0070     tail->next = a ? : b;
0071 
0072     do {
0073         /*
0074          * In worst cases this loop may run many iterations.
0075          * Continue callbacks to the client even though no
0076          * element comparison is needed, so the client's cmp()
0077          * routine can invoke cond_resched() periodically.
0078          */
0079         if (unlikely(!(++count)))
0080             (*cmp)(priv, tail->next, tail->next);
0081 
0082         tail->next->prev = tail;
0083         tail = tail->next;
0084     } while (tail->next);
0085 
0086     tail->next = head;
0087     head->prev = tail;
0088 }
0089 
0090 /**
0091  * list_sort - sort a list
0092  * @priv: private data, opaque to list_sort(), passed to @cmp
0093  * @head: the list to sort
0094  * @cmp: the elements comparison function
0095  *
0096  * This function implements "merge sort", which has O(nlog(n))
0097  * complexity.
0098  *
0099  * The comparison function @cmp must return a negative value if @a
0100  * should sort before @b, and a positive value if @a should sort after
0101  * @b. If @a and @b are equivalent, and their original relative
0102  * ordering is to be preserved, @cmp must return 0.
0103  */
0104 void list_sort(void *priv, struct list_head *head,
0105         int (*cmp)(void *priv, struct list_head *a,
0106             struct list_head *b))
0107 {
0108     struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
0109                         -- last slot is a sentinel */
0110     int lev;  /* index into part[] */
0111     int max_lev = 0;
0112     struct list_head *list;
0113 
0114     if (list_empty(head))
0115         return;
0116 
0117     memset(part, 0, sizeof(part));
0118 
0119     head->prev->next = NULL;
0120     list = head->next;
0121 
0122     while (list) {
0123         struct list_head *cur = list;
0124         list = list->next;
0125         cur->next = NULL;
0126 
0127         for (lev = 0; part[lev]; lev++) {
0128             cur = merge(priv, cmp, part[lev], cur);
0129             part[lev] = NULL;
0130         }
0131         if (lev > max_lev) {
0132             if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
0133                 printk_once(KERN_DEBUG "list too long for efficiency\n");
0134                 lev--;
0135             }
0136             max_lev = lev;
0137         }
0138         part[lev] = cur;
0139     }
0140 
0141     for (lev = 0; lev < max_lev; lev++)
0142         if (part[lev])
0143             list = merge(priv, cmp, part[lev], list);
0144 
0145     merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
0146 }
0147 EXPORT_SYMBOL(list_sort);
0148 
0149 #ifdef CONFIG_TEST_LIST_SORT
0150 
0151 #include <linux/slab.h>
0152 #include <linux/random.h>
0153 
0154 /*
0155  * The pattern of set bits in the list length determines which cases
0156  * are hit in list_sort().
0157  */
0158 #define TEST_LIST_LEN (512+128+2) /* not including head */
0159 
0160 #define TEST_POISON1 0xDEADBEEF
0161 #define TEST_POISON2 0xA324354C
0162 
0163 struct debug_el {
0164     unsigned int poison1;
0165     struct list_head list;
0166     unsigned int poison2;
0167     int value;
0168     unsigned serial;
0169 };
0170 
0171 /* Array, containing pointers to all elements in the test list */
0172 static struct debug_el **elts __initdata;
0173 
0174 static int __init check(struct debug_el *ela, struct debug_el *elb)
0175 {
0176     if (ela->serial >= TEST_LIST_LEN) {
0177         pr_err("error: incorrect serial %d\n", ela->serial);
0178         return -EINVAL;
0179     }
0180     if (elb->serial >= TEST_LIST_LEN) {
0181         pr_err("error: incorrect serial %d\n", elb->serial);
0182         return -EINVAL;
0183     }
0184     if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
0185         pr_err("error: phantom element\n");
0186         return -EINVAL;
0187     }
0188     if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
0189         pr_err("error: bad poison: %#x/%#x\n",
0190             ela->poison1, ela->poison2);
0191         return -EINVAL;
0192     }
0193     if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
0194         pr_err("error: bad poison: %#x/%#x\n",
0195             elb->poison1, elb->poison2);
0196         return -EINVAL;
0197     }
0198     return 0;
0199 }
0200 
0201 static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
0202 {
0203     struct debug_el *ela, *elb;
0204 
0205     ela = container_of(a, struct debug_el, list);
0206     elb = container_of(b, struct debug_el, list);
0207 
0208     check(ela, elb);
0209     return ela->value - elb->value;
0210 }
0211 
0212 static int __init list_sort_test(void)
0213 {
0214     int i, count = 1, err = -ENOMEM;
0215     struct debug_el *el;
0216     struct list_head *cur;
0217     LIST_HEAD(head);
0218 
0219     pr_debug("start testing list_sort()\n");
0220 
0221     elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
0222     if (!elts) {
0223         pr_err("error: cannot allocate memory\n");
0224         return err;
0225     }
0226 
0227     for (i = 0; i < TEST_LIST_LEN; i++) {
0228         el = kmalloc(sizeof(*el), GFP_KERNEL);
0229         if (!el) {
0230             pr_err("error: cannot allocate memory\n");
0231             goto exit;
0232         }
0233          /* force some equivalencies */
0234         el->value = prandom_u32() % (TEST_LIST_LEN / 3);
0235         el->serial = i;
0236         el->poison1 = TEST_POISON1;
0237         el->poison2 = TEST_POISON2;
0238         elts[i] = el;
0239         list_add_tail(&el->list, &head);
0240     }
0241 
0242     list_sort(NULL, &head, cmp);
0243 
0244     err = -EINVAL;
0245     for (cur = head.next; cur->next != &head; cur = cur->next) {
0246         struct debug_el *el1;
0247         int cmp_result;
0248 
0249         if (cur->next->prev != cur) {
0250             pr_err("error: list is corrupted\n");
0251             goto exit;
0252         }
0253 
0254         cmp_result = cmp(NULL, cur, cur->next);
0255         if (cmp_result > 0) {
0256             pr_err("error: list is not sorted\n");
0257             goto exit;
0258         }
0259 
0260         el = container_of(cur, struct debug_el, list);
0261         el1 = container_of(cur->next, struct debug_el, list);
0262         if (cmp_result == 0 && el->serial >= el1->serial) {
0263             pr_err("error: order of equivalent elements not "
0264                 "preserved\n");
0265             goto exit;
0266         }
0267 
0268         if (check(el, el1)) {
0269             pr_err("error: element check failed\n");
0270             goto exit;
0271         }
0272         count++;
0273     }
0274     if (head.prev != cur) {
0275         pr_err("error: list is corrupted\n");
0276         goto exit;
0277     }
0278 
0279 
0280     if (count != TEST_LIST_LEN) {
0281         pr_err("error: bad list length %d", count);
0282         goto exit;
0283     }
0284 
0285     err = 0;
0286 exit:
0287     for (i = 0; i < TEST_LIST_LEN; i++)
0288         kfree(elts[i]);
0289     kfree(elts);
0290     return err;
0291 }
0292 late_initcall(list_sort_test);
0293 #endif /* CONFIG_TEST_LIST_SORT */