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