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 static __init bool less_than(const void *lhs, const void *rhs)
  15 {
  16         return *(int *)lhs < *(int *)rhs;
  17 }
  18
  19 static __init bool greater_than(const void *lhs, const void *rhs)
  20 {
  21         return *(int *)lhs > *(int *)rhs;
  22 }
  23
  24 static __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
  32 static __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
  62 static __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
  94 static __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
 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 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
 169 static 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 }
 186 module_init(test_min_heap_init);
 187
 188 static void __exit test_min_heap_exit(void)
 189 {
 190         /* do nothing */
 191 }
 192 module_exit(test_min_heap_exit);
 193
 194 MODULE_LICENSE("GPL");