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