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