the-tree/lib/test_min_heap.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 #define pr_fmt(fmt) "min_heap_test: " fmt
0003
0004 /*
0005  * Test cases for the min max heap.
0006  */
0007
0008 #include <linux/log2.h>
0009 #include <linux/min_heap.h>
0010 #include <linux/module.h>
0011 #include <linux/printk.h>
0012 #include <linux/random.h>
0013
0014 static __init bool less_than(const void *lhs, const void *rhs)
0015 {
0016     return *(int *)lhs < *(int *)rhs;
0017 }
0018
0019 static __init bool greater_than(const void *lhs, const void *rhs)
0020 {
0021     return *(int *)lhs > *(int *)rhs;
0022 }
0023
0024 static __init void swap_ints(void *lhs, void *rhs)
0025 {
0026     int temp = *(int *)lhs;
0027
0028     *(int *)lhs = *(int *)rhs;
0029     *(int *)rhs = temp;
0030 }
0031
0032 static __init int pop_verify_heap(bool min_heap,
0033                 struct min_heap *heap,
0034                 const struct min_heap_callbacks *funcs)
0035 {
0036     int *values = heap->data;
0037     int err = 0;
0038     int last;
0039
0040     last = values[0];
0041     min_heap_pop(heap, funcs);
0042     while (heap->nr > 0) {
0043         if (min_heap) {
0044             if (last > values[0]) {
0045                 pr_err("error: expected %d <= %d\n", last,
0046                     values[0]);
0047                 err++;
0048             }
0049         } else {
0050             if (last < values[0]) {
0051                 pr_err("error: expected %d >= %d\n", last,
0052                     values[0]);
0053                 err++;
0054             }
0055         }
0056         last = values[0];
0057         min_heap_pop(heap, funcs);
0058     }
0059     return err;
0060 }
0061
0062 static __init int test_heapify_all(bool min_heap)
0063 {
0064     int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0,
0065              -3, -1, -2, -4, 0x8000000, 0x7FFFFFF };
0066     struct min_heap heap = {
0067         .data = values,
0068         .nr = ARRAY_SIZE(values),
0069         .size =  ARRAY_SIZE(values),
0070     };
0071     struct min_heap_callbacks funcs = {
0072         .elem_size = sizeof(int),
0073         .less = min_heap ? less_than : greater_than,
0074         .swp = swap_ints,
0075     };
0076     int i, err;
0077
0078     /* Test with known set of values. */
0079     min_heapify_all(&heap, &funcs);
0080     err = pop_verify_heap(min_heap, &heap, &funcs);
0081
0082
0083     /* Test with randomly generated values. */
0084     heap.nr = ARRAY_SIZE(values);
0085     for (i = 0; i < heap.nr; i++)
0086         values[i] = get_random_int();
0087
0088     min_heapify_all(&heap, &funcs);
0089     err += pop_verify_heap(min_heap, &heap, &funcs);
0090
0091     return err;
0092 }
0093
0094 static __init int test_heap_push(bool min_heap)
0095 {
0096     const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0,
0097                  -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF };
0098     int values[ARRAY_SIZE(data)];
0099     struct min_heap heap = {
0100         .data = values,
0101         .nr = 0,
0102         .size =  ARRAY_SIZE(values),
0103     };
0104     struct min_heap_callbacks funcs = {
0105         .elem_size = sizeof(int),
0106         .less = min_heap ? less_than : greater_than,
0107         .swp = swap_ints,
0108     };
0109     int i, temp, err;
0110
0111     /* Test with known set of values copied from data. */
0112     for (i = 0; i < ARRAY_SIZE(data); i++)
0113         min_heap_push(&heap, &data[i], &funcs);
0114
0115     err = pop_verify_heap(min_heap, &heap, &funcs);
0116
0117     /* Test with randomly generated values. */
0118     while (heap.nr < heap.size) {
0119         temp = get_random_int();
0120         min_heap_push(&heap, &temp, &funcs);
0121     }
0122     err += pop_verify_heap(min_heap, &heap, &funcs);
0123
0124     return err;
0125 }
0126
0127 static __init int test_heap_pop_push(bool min_heap)
0128 {
0129     const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0,
0130                  -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF };
0131     int values[ARRAY_SIZE(data)];
0132     struct min_heap heap = {
0133         .data = values,
0134         .nr = 0,
0135         .size =  ARRAY_SIZE(values),
0136     };
0137     struct min_heap_callbacks funcs = {
0138         .elem_size = sizeof(int),
0139         .less = min_heap ? less_than : greater_than,
0140         .swp = swap_ints,
0141     };
0142     int i, temp, err;
0143
0144     /* Fill values with data to pop and replace. */
0145     temp = min_heap ? 0x80000000 : 0x7FFFFFFF;
0146     for (i = 0; i < ARRAY_SIZE(data); i++)
0147         min_heap_push(&heap, &temp, &funcs);
0148
0149     /* Test with known set of values copied from data. */
0150     for (i = 0; i < ARRAY_SIZE(data); i++)
0151         min_heap_pop_push(&heap, &data[i], &funcs);
0152
0153     err = pop_verify_heap(min_heap, &heap, &funcs);
0154
0155     heap.nr = 0;
0156     for (i = 0; i < ARRAY_SIZE(data); i++)
0157         min_heap_push(&heap, &temp, &funcs);
0158
0159     /* Test with randomly generated values. */
0160     for (i = 0; i < ARRAY_SIZE(data); i++) {
0161         temp = get_random_int();
0162         min_heap_pop_push(&heap, &temp, &funcs);
0163     }
0164     err += pop_verify_heap(min_heap, &heap, &funcs);
0165
0166     return err;
0167 }
0168
0169 static int __init test_min_heap_init(void)
0170 {
0171     int err = 0;
0172
0173     err += test_heapify_all(true);
0174     err += test_heapify_all(false);
0175     err += test_heap_push(true);
0176     err += test_heap_push(false);
0177     err += test_heap_pop_push(true);
0178     err += test_heap_pop_push(false);
0179     if (err) {
0180         pr_err("test failed with %d errors\n", err);
0181         return -EINVAL;
0182     }
0183     pr_info("test passed\n");
0184     return 0;
0185 }
0186 module_init(test_min_heap_init);
0187
0188 static void __exit test_min_heap_exit(void)
0189 {
0190     /* do nothing */
0191 }
0192 module_exit(test_min_heap_exit);
0193
0194 MODULE_LICENSE("GPL");