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, func: 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, func: 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: &heap, func: &funcs); |
80 | err = pop_verify_heap(min_heap, heap: &heap, funcs: &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_u32(); |
87 | |
88 | min_heapify_all(heap: &heap, func: &funcs); |
89 | err += pop_verify_heap(min_heap, heap: &heap, funcs: &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: &heap, element: &data[i], func: &funcs); |
114 | |
115 | err = pop_verify_heap(min_heap, heap: &heap, funcs: &funcs); |
116 | |
117 | /* Test with randomly generated values. */ |
118 | while (heap.nr < heap.size) { |
119 | temp = get_random_u32(); |
120 | min_heap_push(heap: &heap, element: &temp, func: &funcs); |
121 | } |
122 | err += pop_verify_heap(min_heap, heap: &heap, funcs: &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: &heap, element: &temp, func: &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: &heap, element: &data[i], func: &funcs); |
152 | |
153 | err = pop_verify_heap(min_heap, heap: &heap, funcs: &funcs); |
154 | |
155 | heap.nr = 0; |
156 | for (i = 0; i < ARRAY_SIZE(data); i++) |
157 | min_heap_push(heap: &heap, element: &temp, func: &funcs); |
158 | |
159 | /* Test with randomly generated values. */ |
160 | for (i = 0; i < ARRAY_SIZE(data); i++) { |
161 | temp = get_random_u32(); |
162 | min_heap_pop_push(heap: &heap, element: &temp, func: &funcs); |
163 | } |
164 | err += pop_verify_heap(min_heap, heap: &heap, funcs: &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(min_heap: true); |
174 | err += test_heapify_all(min_heap: false); |
175 | err += test_heap_push(min_heap: true); |
176 | err += test_heap_push(min_heap: false); |
177 | err += test_heap_pop_push(min_heap: true); |
178 | err += test_heap_pop_push(min_heap: 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 | |