lib/test_min_heap.c

   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 DEFINE_MIN_HEAP(int, min_heap_test);
  15
  16 static __init bool less_than(const void *lhs, const void *rhs, void __always_unused *args)
  17 {
  18         return *(int *)lhs < *(int *)rhs;
  19 }
  20
  21 static __init bool greater_than(const void *lhs, const void *rhs, void __always_unused *args)
  22 {
  23         return *(int *)lhs > *(int *)rhs;
  24 }
  25
  26 static __init void swap_ints(void *lhs, void *rhs, void __always_unused *args)
  27 {
  28         int temp = *(int *)lhs;
  29
  30         *(int *)lhs = *(int *)rhs;
  31         *(int *)rhs = temp;
  32 }
  33
  34 static __init int pop_verify_heap(bool min_heap,
  35                                 struct min_heap_test *heap,
  36                                 const struct min_heap_callbacks *funcs)
  37 {
  38         int *values = heap->data;
  39         int err = 0;
  40         int last;
  41
  42         last = values[0];
  43         min_heap_pop(heap, funcs, NULL);
  44         while (heap->nr > 0) {
  45                 if (min_heap) {
  46                         if (last > values[0]) {
  47                                 pr_err("error: expected %d <= %d\n", last,
  48                                         values[0]);
  49                                 err++;
  50                         }
  51                 } else {
  52                         if (last < values[0]) {
  53                                 pr_err("error: expected %d >= %d\n", last,
  54                                         values[0]);
  55                                 err++;
  56                         }
  57                 }
  58                 last = values[0];
  59                 min_heap_pop(heap, funcs, NULL);
  60         }
  61         return err;
  62 }
  63
  64 static __init int test_heapify_all(bool min_heap)
  65 {
  66         int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0,
  67                          -3, -1, -2, -4, 0x8000000, 0x7FFFFFF };
  68         struct min_heap_test heap = {
  69                 .data = values,
  70                 .nr = ARRAY_SIZE(values),
  71                 .size =  ARRAY_SIZE(values),
  72         };
  73         struct min_heap_callbacks funcs = {
  74                 .less = min_heap ? less_than : greater_than,
  75                 .swp = swap_ints,
  76         };
  77         int i, err;
  78
  79         /* Test with known set of values. */
  80         min_heapify_all(&heap, &funcs, NULL);
  81         err = pop_verify_heap(min_heap, &heap, &funcs);
  82
  83
  84         /* Test with randomly generated values. */
  85         heap.nr = ARRAY_SIZE(values);
  86         for (i = 0; i < heap.nr; i++)
  87                 values[i] = get_random_u32();
  88
  89         min_heapify_all(&heap, &funcs, NULL);
  90         err += pop_verify_heap(min_heap, &heap, &funcs);
  91
  92         return err;
  93 }
  94
  95 static __init int test_heap_push(bool min_heap)
  96 {
  97         const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0,
  98                              -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF };
  99         int values[ARRAY_SIZE(data)];
 100         struct min_heap_test heap = {
 101                 .data = values,
 102                 .nr = 0,
 103                 .size =  ARRAY_SIZE(values),
 104         };
 105         struct min_heap_callbacks funcs = {
 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, NULL);
 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_u32();
 120                 min_heap_push(&heap, &temp, &funcs, NULL);
 121         }
 122         err += pop_verify_heap(min_heap, &heap, &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_test heap = {
 133                 .data = values,
 134                 .nr = 0,
 135                 .size =  ARRAY_SIZE(values),
 136         };
 137         struct min_heap_callbacks funcs = {
 138                 .less = min_heap ? less_than : greater_than,
 139                 .swp = swap_ints,
 140         };
 141         int i, temp, err;
 142
 143         /* Fill values with data to pop and replace. */
 144         temp = min_heap ? 0x80000000 : 0x7FFFFFFF;
 145         for (i = 0; i < ARRAY_SIZE(data); i++)
 146                 min_heap_push(&heap, &temp, &funcs, NULL);
 147
 148         /* Test with known set of values copied from data. */
 149         for (i = 0; i < ARRAY_SIZE(data); i++)
 150                 min_heap_pop_push(&heap, &data[i], &funcs, NULL);
 151
 152         err = pop_verify_heap(min_heap, &heap, &funcs);
 153
 154         heap.nr = 0;
 155         for (i = 0; i < ARRAY_SIZE(data); i++)
 156                 min_heap_push(&heap, &temp, &funcs, NULL);
 157
 158         /* Test with randomly generated values. */
 159         for (i = 0; i < ARRAY_SIZE(data); i++) {
 160                 temp = get_random_u32();
 161                 min_heap_pop_push(&heap, &temp, &funcs, NULL);
 162         }
 163         err += pop_verify_heap(min_heap, &heap, &funcs);
 164
 165         return err;
 166 }
 167
 168 static __init int test_heap_del(bool min_heap)
 169 {
 170         int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0,
 171                          -3, -1, -2, -4, 0x8000000, 0x7FFFFFF };
 172         struct min_heap_test heap;
 173
 174         min_heap_init(&heap, values, ARRAY_SIZE(values));
 175         heap.nr = ARRAY_SIZE(values);
 176         struct min_heap_callbacks funcs = {
 177                 .less = min_heap ? less_than : greater_than,
 178                 .swp = swap_ints,
 179         };
 180         int i, err;
 181
 182         /* Test with known set of values. */
 183         min_heapify_all(&heap, &funcs, NULL);
 184         for (i = 0; i < ARRAY_SIZE(values) / 2; i++)
 185                 min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL);
 186         err = pop_verify_heap(min_heap, &heap, &funcs);
 187
 188
 189         /* Test with randomly generated values. */
 190         heap.nr = ARRAY_SIZE(values);
 191         for (i = 0; i < heap.nr; i++)
 192                 values[i] = get_random_u32();
 193         min_heapify_all(&heap, &funcs, NULL);
 194
 195         for (i = 0; i < ARRAY_SIZE(values) / 2; i++)
 196                 min_heap_del(&heap, get_random_u32() % heap.nr, &funcs, NULL);
 197         err += pop_verify_heap(min_heap, &heap, &funcs);
 198
 199         return err;
 200 }
 201
 202 static int __init test_min_heap_init(void)
 203 {
 204         int err = 0;
 205
 206         err += test_heapify_all(true);
 207         err += test_heapify_all(false);
 208         err += test_heap_push(true);
 209         err += test_heap_push(false);
 210         err += test_heap_pop_push(true);
 211         err += test_heap_pop_push(false);
 212         err += test_heap_del(true);
 213         err += test_heap_del(false);
 214         if (err) {
 215                 pr_err("test failed with %d errors\n", err);
 216                 return -EINVAL;
 217         }
 218         pr_info("test passed\n");
 219         return 0;
 220 }
 221 module_init(test_min_heap_init);
 222
 223 static void __exit test_min_heap_exit(void)
 224 {
 225         /* do nothing */
 226 }
 227 module_exit(test_min_heap_exit);
 228
 229 MODULE_DESCRIPTION("Test cases for the min max heap");
 230 MODULE_LICENSE("GPL");