1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
// SPDX-License-Identifier: GPL-2.0-only
/*
* Test cases for the min max heap.
*/
#include <kunit/test.h>
#include <linux/min_heap.h>
#include <linux/module.h>
#include <linux/random.h>
struct min_heap_test_case {
const char *str;
bool min_heap;
};
static struct min_heap_test_case min_heap_cases[] = {
{
.str = "min",
.min_heap = true,
},
{
.str = "max",
.min_heap = false,
},
};
KUNIT_ARRAY_PARAM_DESC(min_heap, min_heap_cases, str);
DEFINE_MIN_HEAP(int, min_heap_test);
static bool less_than(const void *lhs, const void *rhs, void __always_unused *args)
{
return *(int *)lhs < *(int *)rhs;
}
static bool greater_than(const void *lhs, const void *rhs, void __always_unused *args)
{
return *(int *)lhs > *(int *)rhs;
}
static void pop_verify_heap(struct kunit *test,
bool min_heap,
struct min_heap_test *heap,
const struct min_heap_callbacks *funcs)
{
int *values = heap->data;
int last;
last = values[0];
min_heap_pop_inline(heap, funcs, NULL);
while (heap->nr > 0) {
if (min_heap)
KUNIT_EXPECT_LE(test, last, values[0]);
else
KUNIT_EXPECT_GE(test, last, values[0]);
last = values[0];
min_heap_pop_inline(heap, funcs, NULL);
}
}
static void test_heapify_all(struct kunit *test)
{
const struct min_heap_test_case *params = test->param_value;
int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0,
-3, -1, -2, -4, 0x8000000, 0x7FFFFFF };
struct min_heap_test heap = {
.data = values,
.nr = ARRAY_SIZE(values),
.size = ARRAY_SIZE(values),
};
struct min_heap_callbacks funcs = {
.less = params->min_heap ? less_than : greater_than,
.swp = NULL,
};
int i;
/* Test with known set of values. */
min_heapify_all_inline(&heap, &funcs, NULL);
pop_verify_heap(test, params->min_heap, &heap, &funcs);
/* Test with randomly generated values. */
heap.nr = ARRAY_SIZE(values);
for (i = 0; i < heap.nr; i++)
values[i] = get_random_u32();
min_heapify_all_inline(&heap, &funcs, NULL);
pop_verify_heap(test, params->min_heap, &heap, &funcs);
}
static void test_heap_push(struct kunit *test)
{
const struct min_heap_test_case *params = test->param_value;
const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0,
-3, -1, -2, -4, 0x80000000, 0x7FFFFFFF };
int values[ARRAY_SIZE(data)];
struct min_heap_test heap = {
.data = values,
.nr = 0,
.size = ARRAY_SIZE(values),
};
struct min_heap_callbacks funcs = {
.less = params->min_heap ? less_than : greater_than,
.swp = NULL,
};
int i, temp;
/* Test with known set of values copied from data. */
for (i = 0; i < ARRAY_SIZE(data); i++)
min_heap_push_inline(&heap, &data[i], &funcs, NULL);
pop_verify_heap(test, params->min_heap, &heap, &funcs);
/* Test with randomly generated values. */
while (heap.nr < heap.size) {
temp = get_random_u32();
min_heap_push_inline(&heap, &temp, &funcs, NULL);
}
pop_verify_heap(test, params->min_heap, &heap, &funcs);
}
static void test_heap_pop_push(struct kunit *test)
{
const struct min_heap_test_case *params = test->param_value;
const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0,
-3, -1, -2, -4, 0x80000000, 0x7FFFFFFF };
int values[ARRAY_SIZE(data)];
struct min_heap_test heap = {
.data = values,
.nr = 0,
.size = ARRAY_SIZE(values),
};
struct min_heap_callbacks funcs = {
.less = params->min_heap ? less_than : greater_than,
.swp = NULL,
};
int i, temp;
/* Fill values with data to pop and replace. */
temp = params->min_heap ? 0x80000000 : 0x7FFFFFFF;
for (i = 0; i < ARRAY_SIZE(data); i++)
min_heap_push_inline(&heap, &temp, &funcs, NULL);
/* Test with known set of values copied from data. */
for (i = 0; i < ARRAY_SIZE(data); i++)
min_heap_pop_push_inline(&heap, &data[i], &funcs, NULL);
pop_verify_heap(test, params->min_heap, &heap, &funcs);
heap.nr = 0;
for (i = 0; i < ARRAY_SIZE(data); i++)
min_heap_push_inline(&heap, &temp, &funcs, NULL);
/* Test with randomly generated values. */
for (i = 0; i < ARRAY_SIZE(data); i++) {
temp = get_random_u32();
min_heap_pop_push_inline(&heap, &temp, &funcs, NULL);
}
pop_verify_heap(test, params->min_heap, &heap, &funcs);
}
static void test_heap_del(struct kunit *test)
{
const struct min_heap_test_case *params = test->param_value;
int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0,
-3, -1, -2, -4, 0x8000000, 0x7FFFFFF };
struct min_heap_test heap;
min_heap_init_inline(&heap, values, ARRAY_SIZE(values));
heap.nr = ARRAY_SIZE(values);
struct min_heap_callbacks funcs = {
.less = params->min_heap ? less_than : greater_than,
.swp = NULL,
};
int i;
/* Test with known set of values. */
min_heapify_all_inline(&heap, &funcs, NULL);
for (i = 0; i < ARRAY_SIZE(values) / 2; i++)
min_heap_del_inline(&heap, get_random_u32() % heap.nr, &funcs, NULL);
pop_verify_heap(test, params->min_heap, &heap, &funcs);
/* Test with randomly generated values. */
heap.nr = ARRAY_SIZE(values);
for (i = 0; i < heap.nr; i++)
values[i] = get_random_u32();
min_heapify_all_inline(&heap, &funcs, NULL);
for (i = 0; i < ARRAY_SIZE(values) / 2; i++)
min_heap_del_inline(&heap, get_random_u32() % heap.nr, &funcs, NULL);
pop_verify_heap(test, params->min_heap, &heap, &funcs);
}
static struct kunit_case min_heap_test_cases[] = {
KUNIT_CASE_PARAM(test_heapify_all, min_heap_gen_params),
KUNIT_CASE_PARAM(test_heap_push, min_heap_gen_params),
KUNIT_CASE_PARAM(test_heap_pop_push, min_heap_gen_params),
KUNIT_CASE_PARAM(test_heap_del, min_heap_gen_params),
{},
};
static struct kunit_suite min_heap_test_suite = {
.name = "min_heap",
.test_cases = min_heap_test_cases,
};
kunit_test_suite(min_heap_test_suite);
MODULE_DESCRIPTION("Test cases for the min max heap");
MODULE_LICENSE("GPL");
|
