1 // SPDX-License-Identifier: GPL-2.0-only 2 #define pr_fmt(fmt) "min_heap_test: " fmt 3 4 /* 5 * Test cases for the min max heap. 6 */ 7 8 #include <linux/log2.h> 9 #include <linux/min_heap.h> 10 #include <linux/module.h> 11 #include <linux/printk.h> 12 #include <linux/random.h> 13 14 DEFINE_MIN_HEAP(int, min_heap_test); 15 16 static __init bool less_than(const void *lhs, const void *rhs, void __always_unused *args) 17 { 18 return *(int *)lhs < *(int *)rhs; 19 } 20 21 static __init bool greater_than(const void *lhs, const void *rhs, void __always_unused *args) 22 { 23 return *(int *)lhs > *(int *)rhs; 24 } 25 26 static __init int pop_verify_heap(bool min_heap, 27 struct min_heap_test *heap, 28 const struct min_heap_callbacks *funcs) 29 { 30 int *values = heap->data; 31 int err = 0; 32 int last; 33 34 last = values[0]; 35 min_heap_pop(heap, funcs, NULL); 36 while (heap->nr > 0) { 37 if (min_heap) { 38 if (last > values[0]) { 39 pr_err("error: expected %d <= %d\n", last, 40 values[0]); 41 err++; 42 } 43 } else { 44 if (last < values[0]) { 45 pr_err("error: expected %d >= %d\n", last, 46 values[0]); 47 err++; 48 } 49 } 50 last = values[0]; 51 min_heap_pop(heap, funcs, NULL); 52 } 53 return err; 54 } 55 56 static __init int test_heapify_all(bool min_heap) 57 { 58 int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0, 59 -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; 60 struct min_heap_test heap = { 61 .data = values, 62 .nr = ARRAY_SIZE(values), 63 .size = ARRAY_SIZE(values), 64 }; 65 struct min_heap_callbacks funcs = { 66 .less = min_heap ? less_than : greater_than, 67 .swp = NULL, 68 }; 69 int i, err; 70 71 /* Test with known set of values. */ 72 min_heapify_all(&heap, &funcs, NULL); 73 err = pop_verify_heap(min_heap, &heap, &funcs); 74 75 76 /* Test with randomly generated values. */ 77 heap.nr = ARRAY_SIZE(values); 78 for (i = 0; i < heap.nr; i++) 79 values[i] = get_random_u32(); 80 81 min_heapify_all(&heap, &funcs, NULL); 82 err += pop_verify_heap(min_heap, &heap, &funcs); 83 84 return err; 85 } 86 87 static __init int test_heap_push(bool min_heap) 88 { 89 const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, 90 -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; 91 int values[ARRAY_SIZE(data)]; 92 struct min_heap_test heap = { 93 .data = values, 94 .nr = 0, 95 .size = ARRAY_SIZE(values), 96 }; 97 struct min_heap_callbacks funcs = { 98 .less = min_heap ? less_than : greater_than, 99 .swp = NULL, 100 }; 101 int i, temp, err; 102 103 /* Test with known set of values copied from data. */ 104 for (i = 0; i < ARRAY_SIZE(data); i++) 105 min_heap_push(&heap, &data[i], &funcs, NULL); 106 107 err = pop_verify_heap(min_heap, &heap, &funcs); 108 109 /* Test with randomly generated values. */ 110 while (heap.nr < heap.size) { 111 temp = get_random_u32(); 112 min_heap_push(&heap, &temp, &funcs, NULL); 113 } 114 err += pop_verify_heap(min_heap, &heap, &funcs); 115 116 return err; 117 } 118 119 static __init int test_heap_pop_push(bool min_heap) 120 { 121 const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, 122 -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; 123 int values[ARRAY_SIZE(data)]; 124 struct min_heap_test heap = { 125 .data = values, 126 .nr = 0, 127 .size = ARRAY_SIZE(values), 128 }; 129 struct min_heap_callbacks funcs = { 130 .less = min_heap ? less_than : greater_than, 131 .swp = NULL, 132 }; 133 int i, temp, err; 134 135 /* Fill values with data to pop and replace. */ 136 temp = min_heap ? 0x80000000 : 0x7FFFFFFF; 137 for (i = 0; i < ARRAY_SIZE(data); i++) 138 min_heap_push(&heap, &temp, &funcs, NULL); 139 140 /* Test with known set of values copied from data. */ 141 for (i = 0; i < ARRAY_SIZE(data); i++) 142 min_heap_pop_push(&heap, &data[i], &funcs, NULL); 143 144 err = pop_verify_heap(min_heap, &heap, &funcs); 145 146 heap.nr = 0; 147 for (i = 0; i < ARRAY_SIZE(data); i++) 148 min_heap_push(&heap, &temp, &funcs, NULL); 149 150 /* Test with randomly generated values. */ 151 for (i = 0; i < ARRAY_SIZE(data); i++) { 152 temp = get_random_u32(); 153 min_heap_pop_push(&heap, &temp, &funcs, NULL); 154 } 155 err += pop_verify_heap(min_heap, &heap, &funcs); 156 157 return err; 158 } 159 160 static __init int test_heap_del(bool min_heap) 161 { 162 int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0, 163 -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; 164 struct min_heap_test heap; 165 166 min_heap_init(&heap, values, ARRAY_SIZE(values)); 167 heap.nr = ARRAY_SIZE(values); 168 struct min_heap_callbacks funcs = { 169 .less = min_heap ? less_than : greater_than, 170 .swp = NULL, 171 }; 172 int i, err; 173 174 /* Test with known set of values. */ 175 min_heapify_all(&heap, &funcs, NULL); 176 for (i = 0; i < ARRAY_SIZE(values) / 2; i++) 177 min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); 178 err = pop_verify_heap(min_heap, &heap, &funcs); 179 180 181 /* Test with randomly generated values. */ 182 heap.nr = ARRAY_SIZE(values); 183 for (i = 0; i < heap.nr; i++) 184 values[i] = get_random_u32(); 185 min_heapify_all(&heap, &funcs, NULL); 186 187 for (i = 0; i < ARRAY_SIZE(values) / 2; i++) 188 min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL); 189 err += pop_verify_heap(min_heap, &heap, &funcs); 190 191 return err; 192 } 193 194 static int __init test_min_heap_init(void) 195 { 196 int err = 0; 197 198 err += test_heapify_all(true); 199 err += test_heapify_all(false); 200 err += test_heap_push(true); 201 err += test_heap_push(false); 202 err += test_heap_pop_push(true); 203 err += test_heap_pop_push(false); 204 err += test_heap_del(true); 205 err += test_heap_del(false); 206 if (err) { 207 pr_err("test failed with %d errors\n", err); 208 return -EINVAL; 209 } 210 pr_info("test passed\n"); 211 return 0; 212 } 213 module_init(test_min_heap_init); 214 215 static void __exit test_min_heap_exit(void) 216 { 217 /* do nothing */ 218 } 219 module_exit(test_min_heap_exit); 220 221 MODULE_DESCRIPTION("Test cases for the min max heap"); 222 MODULE_LICENSE("GPL"); 223