test_min_heap.c 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194
  1. // SPDX-License-Identifier: GPL-2.0-only
  2. #define pr_fmt(fmt) "min_heap_test: " fmt
  3. /*
  4. * Test cases for the min max heap.
  5. */
  6. #include <linux/log2.h>
  7. #include <linux/min_heap.h>
  8. #include <linux/module.h>
  9. #include <linux/printk.h>
  10. #include <linux/random.h>
  11. static __init bool less_than(const void *lhs, const void *rhs)
  12. {
  13. return *(int *)lhs < *(int *)rhs;
  14. }
  15. static __init bool greater_than(const void *lhs, const void *rhs)
  16. {
  17. return *(int *)lhs > *(int *)rhs;
  18. }
  19. static __init void swap_ints(void *lhs, void *rhs)
  20. {
  21. int temp = *(int *)lhs;
  22. *(int *)lhs = *(int *)rhs;
  23. *(int *)rhs = temp;
  24. }
  25. static __init int pop_verify_heap(bool min_heap,
  26. struct min_heap *heap,
  27. const struct min_heap_callbacks *funcs)
  28. {
  29. int *values = heap->data;
  30. int err = 0;
  31. int last;
  32. last = values[0];
  33. min_heap_pop(heap, funcs);
  34. while (heap->nr > 0) {
  35. if (min_heap) {
  36. if (last > values[0]) {
  37. pr_err("error: expected %d <= %d\n", last,
  38. values[0]);
  39. err++;
  40. }
  41. } else {
  42. if (last < values[0]) {
  43. pr_err("error: expected %d >= %d\n", last,
  44. values[0]);
  45. err++;
  46. }
  47. }
  48. last = values[0];
  49. min_heap_pop(heap, funcs);
  50. }
  51. return err;
  52. }
  53. static __init int test_heapify_all(bool min_heap)
  54. {
  55. int values[] = { 3, 1, 2, 4, 0x8000000, 0x7FFFFFF, 0,
  56. -3, -1, -2, -4, 0x8000000, 0x7FFFFFF };
  57. struct min_heap heap = {
  58. .data = values,
  59. .nr = ARRAY_SIZE(values),
  60. .size = ARRAY_SIZE(values),
  61. };
  62. struct min_heap_callbacks funcs = {
  63. .elem_size = sizeof(int),
  64. .less = min_heap ? less_than : greater_than,
  65. .swp = swap_ints,
  66. };
  67. int i, err;
  68. /* Test with known set of values. */
  69. min_heapify_all(&heap, &funcs);
  70. err = pop_verify_heap(min_heap, &heap, &funcs);
  71. /* Test with randomly generated values. */
  72. heap.nr = ARRAY_SIZE(values);
  73. for (i = 0; i < heap.nr; i++)
  74. values[i] = get_random_int();
  75. min_heapify_all(&heap, &funcs);
  76. err += pop_verify_heap(min_heap, &heap, &funcs);
  77. return err;
  78. }
  79. static __init int test_heap_push(bool min_heap)
  80. {
  81. const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0,
  82. -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF };
  83. int values[ARRAY_SIZE(data)];
  84. struct min_heap heap = {
  85. .data = values,
  86. .nr = 0,
  87. .size = ARRAY_SIZE(values),
  88. };
  89. struct min_heap_callbacks funcs = {
  90. .elem_size = sizeof(int),
  91. .less = min_heap ? less_than : greater_than,
  92. .swp = swap_ints,
  93. };
  94. int i, temp, err;
  95. /* Test with known set of values copied from data. */
  96. for (i = 0; i < ARRAY_SIZE(data); i++)
  97. min_heap_push(&heap, &data[i], &funcs);
  98. err = pop_verify_heap(min_heap, &heap, &funcs);
  99. /* Test with randomly generated values. */
  100. while (heap.nr < heap.size) {
  101. temp = get_random_int();
  102. min_heap_push(&heap, &temp, &funcs);
  103. }
  104. err += pop_verify_heap(min_heap, &heap, &funcs);
  105. return err;
  106. }
  107. static __init int test_heap_pop_push(bool min_heap)
  108. {
  109. const int data[] = { 3, 1, 2, 4, 0x80000000, 0x7FFFFFFF, 0,
  110. -3, -1, -2, -4, 0x80000000, 0x7FFFFFFF };
  111. int values[ARRAY_SIZE(data)];
  112. struct min_heap heap = {
  113. .data = values,
  114. .nr = 0,
  115. .size = ARRAY_SIZE(values),
  116. };
  117. struct min_heap_callbacks funcs = {
  118. .elem_size = sizeof(int),
  119. .less = min_heap ? less_than : greater_than,
  120. .swp = swap_ints,
  121. };
  122. int i, temp, err;
  123. /* Fill values with data to pop and replace. */
  124. temp = min_heap ? 0x80000000 : 0x7FFFFFFF;
  125. for (i = 0; i < ARRAY_SIZE(data); i++)
  126. min_heap_push(&heap, &temp, &funcs);
  127. /* Test with known set of values copied from data. */
  128. for (i = 0; i < ARRAY_SIZE(data); i++)
  129. min_heap_pop_push(&heap, &data[i], &funcs);
  130. err = pop_verify_heap(min_heap, &heap, &funcs);
  131. heap.nr = 0;
  132. for (i = 0; i < ARRAY_SIZE(data); i++)
  133. min_heap_push(&heap, &temp, &funcs);
  134. /* Test with randomly generated values. */
  135. for (i = 0; i < ARRAY_SIZE(data); i++) {
  136. temp = get_random_int();
  137. min_heap_pop_push(&heap, &temp, &funcs);
  138. }
  139. err += pop_verify_heap(min_heap, &heap, &funcs);
  140. return err;
  141. }
  142. static int __init test_min_heap_init(void)
  143. {
  144. int err = 0;
  145. err += test_heapify_all(true);
  146. err += test_heapify_all(false);
  147. err += test_heap_push(true);
  148. err += test_heap_push(false);
  149. err += test_heap_pop_push(true);
  150. err += test_heap_pop_push(false);
  151. if (err) {
  152. pr_err("test failed with %d errors\n", err);
  153. return -EINVAL;
  154. }
  155. pr_info("test passed\n");
  156. return 0;
  157. }
  158. module_init(test_min_heap_init);
  159. static void __exit test_min_heap_exit(void)
  160. {
  161. /* do nothing */
  162. }
  163. module_exit(test_min_heap_exit);
  164. MODULE_LICENSE("GPL");