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
 14static __init bool less_than(const void *lhs, const void *rhs)
 15{
 16	return *(int *)lhs < *(int *)rhs;
 17}
 18
 19static __init bool greater_than(const void *lhs, const void *rhs)
 20{
 21	return *(int *)lhs > *(int *)rhs;
 22}
 23
 24static __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
 32static __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, 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, funcs);
 58	}
 59	return err;
 60}
 61
 62static __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, &funcs);
 80	err = pop_verify_heap(min_heap, &heap, &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_int();
 87
 88	min_heapify_all(&heap, &funcs);
 89	err += pop_verify_heap(min_heap, &heap, &funcs);
 90
 91	return err;
 92}
 93
 94static __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, &data[i], &funcs);
114
115	err = pop_verify_heap(min_heap, &heap, &funcs);
116
117	/* Test with randomly generated values. */
118	while (heap.nr < heap.size) {
119		temp = get_random_int();
120		min_heap_push(&heap, &temp, &funcs);
121	}
122	err += pop_verify_heap(min_heap, &heap, &funcs);
123
124	return err;
125}
126
127static __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, &temp, &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, &data[i], &funcs);
152
153	err = pop_verify_heap(min_heap, &heap, &funcs);
154
155	heap.nr = 0;
156	for (i = 0; i < ARRAY_SIZE(data); i++)
157		min_heap_push(&heap, &temp, &funcs);
158
159	/* Test with randomly generated values. */
160	for (i = 0; i < ARRAY_SIZE(data); i++) {
161		temp = get_random_int();
162		min_heap_pop_push(&heap, &temp, &funcs);
163	}
164	err += pop_verify_heap(min_heap, &heap, &funcs);
165
166	return err;
167}
168
169static int __init test_min_heap_init(void)
170{
171	int err = 0;
172
173	err += test_heapify_all(true);
174	err += test_heapify_all(false);
175	err += test_heap_push(true);
176	err += test_heap_push(false);
177	err += test_heap_pop_push(true);
178	err += test_heap_pop_push(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}
186module_init(test_min_heap_init);
187
188static void __exit test_min_heap_exit(void)
189{
190	/* do nothing */
191}
192module_exit(test_min_heap_exit);
193
194MODULE_LICENSE("GPL");