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