projects/linux·blob master · refs

209 lines · 5.6 KiB

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
11struct min_heap_test_case {
12 const char *str;
13 bool min_heap;
14};
15
16static 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
27KUNIT_ARRAY_PARAM_DESC(min_heap, min_heap_cases, str);
28
29DEFINE_MIN_HEAP(int, min_heap_test);
30
31static bool less_than(const void *lhs, const void *rhs, void __always_unused *args)
32{
33 return *(int *)lhs < *(int *)rhs;
34}
35
36static bool greater_than(const void *lhs, const void *rhs, void __always_unused *args)
37{
38 return *(int *)lhs > *(int *)rhs;
39}
40
41static 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
61static 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
90static 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
121static 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
161static 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
193static 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
201static struct kunit_suite min_heap_test_suite = {
202 .name = "min_heap",
203 .test_cases = min_heap_test_cases,
204};
205
206kunit_test_suite(min_heap_test_suite);
207
208MODULE_DESCRIPTION("Test cases for the min max heap");
209MODULE_LICENSE("GPL");