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