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 static __init bool less_than(const void *lhs, const void *rhs) 15 { 16 return *(int *)lhs < *(int *)rhs; 17 } 18 19 static __init bool greater_than(const void *lhs, const void *rhs) 20 { 21 return *(int *)lhs > *(int *)rhs; 22 } 23 24 static __init void swap_ints(void *lhs, void *rhs) 25 { 26 int temp = *(int *)lhs; 27 28 *(int *)lhs = *(int *)rhs; 29 *(int *)rhs = temp; 30 } 31 32 static __init int pop_verify_heap(bool min_heap, 33 struct min_heap *heap, 34 const struct min_heap_callbacks *funcs) 35 { 36 int *values = heap->data; 37 int err = 0; 38 int last; 39 40 last = values[0]; 41 min_heap_pop(heap, funcs); 42 while (heap->nr > 0) { 43 if (min_heap) { 44 if (last > values[0]) { 45 pr_err("error: expected %d <= %d\n", last, 46 values[0]); 47 err++; 48 } 49 } else { 50 if (last < values[0]) { 51 pr_err("error: expected %d >= %d\n", last, 52 values[0]); 53 err++; 54 } 55 } 56 last = values[0]; 57 min_heap_pop(heap, funcs); 58 } 59 return err; 60 } 61 62 static __init int test_heapify_all(bool min_heap) 63 { 64 int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0, 65 -3, -1, -2, -4, 0x8000000, 0x7FFFFFF }; 66 struct min_heap heap = { 67 .data = values, 68 .nr = ARRAY_SIZE(values), 69 .size = ARRAY_SIZE(values), 70 }; 71 struct min_heap_callbacks funcs = { 72 .elem_size = sizeof(int), 73 .less = min_heap ? less_than : greater_than, 74 .swp = swap_ints, 75 }; 76 int i, err; 77 78 /* Test with known set of values. */ 79 min_heapify_all(&heap, &funcs); 80 err = pop_verify_heap(min_heap, &heap, &funcs); 81 82 83 /* Test with randomly generated values. */ 84 heap.nr = ARRAY_SIZE(values); 85 for (i = 0; i < heap.nr; i++) 86 values[i] = get_random_int(); 87 88 min_heapify_all(&heap, &funcs); 89 err += pop_verify_heap(min_heap, &heap, &funcs); 90 91 return err; 92 } 93 94 static __init int test_heap_push(bool min_heap) 95 { 96 const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0, 97 -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF }; 98 int values[ARRAY_SIZE(data)]; 99 struct min_heap heap = { 100 .data = values, 101 .nr = 0, 102 .size = ARRAY_SIZE(values), 103 }; 104 struct min_heap_callbacks funcs = { 105 .elem_size = sizeof(int), 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); 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_int(); 120 min_heap_push(&heap, &temp, &funcs); 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 heap = { 133 .data = values, 134 .nr = 0, 135 .size = ARRAY_SIZE(values), 136 }; 137 struct min_heap_callbacks funcs = { 138 .elem_size = sizeof(int), 139 .less = min_heap ? less_than : greater_than, 140 .swp = swap_ints, 141 }; 142 int i, temp, err; 143 144 /* Fill values with data to pop and replace. */ 145 temp = min_heap ? 0x80000000 : 0x7FFFFFFF; 146 for (i = 0; i < ARRAY_SIZE(data); i++) 147 min_heap_push(&heap, &temp, &funcs); 148 149 /* Test with known set of values copied from data. */ 150 for (i = 0; i < ARRAY_SIZE(data); i++) 151 min_heap_pop_push(&heap, &data[i], &funcs); 152 153 err = pop_verify_heap(min_heap, &heap, &funcs); 154 155 heap.nr = 0; 156 for (i = 0; i < ARRAY_SIZE(data); i++) 157 min_heap_push(&heap, &temp, &funcs); 158 159 /* Test with randomly generated values. */ 160 for (i = 0; i < ARRAY_SIZE(data); i++) { 161 temp = get_random_int(); 162 min_heap_pop_push(&heap, &temp, &funcs); 163 } 164 err += pop_verify_heap(min_heap, &heap, &funcs); 165 166 return err; 167 } 168 169 static int __init test_min_heap_init(void) 170 { 171 int err = 0; 172 173 err += test_heapify_all(true); 174 err += test_heapify_all(false); 175 err += test_heap_push(true); 176 err += test_heap_push(false); 177 err += test_heap_pop_push(true); 178 err += test_heap_pop_push(false); 179 if (err) { 180 pr_err("test failed with %d errors\n", err); 181 return -EINVAL; 182 } 183 pr_info("test passed\n"); 184 return 0; 185 } 186 module_init(test_min_heap_init); 187 188 static void __exit test_min_heap_exit(void) 189 { 190 /* do nothing */ 191 } 192 module_exit(test_min_heap_exit); 193 194 MODULE_LICENSE("GPL"); 195