231 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2#define pr_fmt(fmt) "min_heap_test: " fmt3 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 14DEFINE_MIN_HEAP(int, min_heap_test);15 16static __init bool less_than(const void *lhs, const void *rhs, void __always_unused *args)17{18 return *(int *)lhs < *(int *)rhs;19}20 21static __init bool greater_than(const void *lhs, const void *rhs, void __always_unused *args)22{23 return *(int *)lhs > *(int *)rhs;24}25 26static __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 34static __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 64static __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 95static __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 127static __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 168static __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 202static 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}221module_init(test_min_heap_init);222 223static void __exit test_min_heap_exit(void)224{225 /* do nothing */226}227module_exit(test_min_heap_exit);228 229MODULE_DESCRIPTION("Test cases for the min max heap");230MODULE_LICENSE("GPL");231