2
0

priority_queue_test.c 7.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260
  1. /*
  2. * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
  3. *
  4. * Licensed under the Apache License 2.0 (the "License"). You may not use
  5. * this file except in compliance with the License. You can obtain a copy
  6. * in the file LICENSE in the source distribution or at
  7. * https://www.openssl.org/source/license.html
  8. */
  9. #include <stdio.h>
  10. #include <string.h>
  11. #include <openssl/opensslconf.h>
  12. #include <internal/priority_queue.h>
  13. #include <openssl/err.h>
  14. #include <openssl/crypto.h>
  15. #include "internal/nelem.h"
  16. #include "testutil.h"
  17. #define MAX_SAMPLES 500000
  18. DEFINE_PRIORITY_QUEUE_OF(size_t);
  19. static size_t num_rec_freed;
  20. static int size_t_compare(const size_t *a, const size_t *b)
  21. {
  22. if (*a < *b)
  23. return -1;
  24. if (*a > *b)
  25. return 1;
  26. return 0;
  27. }
  28. static int qsort_size_t_compare(const void *a, const void *b)
  29. {
  30. return size_t_compare((size_t *)a, (size_t *)b);
  31. }
  32. static int qsort_size_t_compare_rev(const void *a, const void *b)
  33. {
  34. return size_t_compare((size_t *)b, (size_t *)a);
  35. }
  36. static void free_checker(ossl_unused size_t *p)
  37. {
  38. num_rec_freed++;
  39. }
  40. static int test_size_t_priority_queue_int(int reserve, int order, int count,
  41. int remove, int random, int popfree)
  42. {
  43. PRIORITY_QUEUE_OF(size_t) *pq = NULL;
  44. static size_t values[MAX_SAMPLES], sorted[MAX_SAMPLES], ref[MAX_SAMPLES];
  45. size_t n;
  46. int i, res = 0;
  47. static const char *orders[3] = { "unordered", "ascending", "descending" };
  48. TEST_info("testing count %d, %s, %s, values %s, remove %d, %sfree",
  49. count, orders[order], reserve ? "reserve" : "grow",
  50. random ? "random" : "deterministic", remove,
  51. popfree ? "pop " : "");
  52. if (!TEST_size_t_le(count, MAX_SAMPLES))
  53. return 0;
  54. memset(values, 0, sizeof(values));
  55. memset(sorted, 0, sizeof(sorted));
  56. memset(ref, 0, sizeof(ref));
  57. for (i = 0; i < count; i++)
  58. values[i] = random ? test_random() : (size_t)(count - i);
  59. memcpy(sorted, values, sizeof(*sorted) * count);
  60. qsort(sorted, count, sizeof(*sorted), &qsort_size_t_compare);
  61. if (order == 1)
  62. memcpy(values, sorted, sizeof(*values) * count);
  63. else if (order == 2)
  64. qsort(values, count, sizeof(*values), &qsort_size_t_compare_rev);
  65. if (!TEST_ptr(pq = ossl_pqueue_size_t_new(&size_t_compare))
  66. || !TEST_size_t_eq(ossl_pqueue_size_t_num(pq), 0))
  67. goto err;
  68. if (reserve && !TEST_true(ossl_pqueue_size_t_reserve(pq, count)))
  69. goto err;
  70. for (i = 0; i < count; i++)
  71. if (!TEST_true(ossl_pqueue_size_t_push(pq, values + i, ref + i)))
  72. goto err;
  73. if (!TEST_size_t_eq(*ossl_pqueue_size_t_peek(pq), *sorted)
  74. || !TEST_size_t_eq(ossl_pqueue_size_t_num(pq), count))
  75. goto err;
  76. if (remove) {
  77. while (remove-- > 0) {
  78. i = test_random() % count;
  79. if (values[i] != SIZE_MAX) {
  80. if (!TEST_ptr_eq(ossl_pqueue_size_t_remove(pq, ref[i]),
  81. values + i))
  82. goto err;
  83. values[i] = SIZE_MAX;
  84. }
  85. }
  86. memcpy(sorted, values, sizeof(*sorted) * count);
  87. qsort(sorted, count, sizeof(*sorted), &qsort_size_t_compare);
  88. }
  89. for (i = 0; ossl_pqueue_size_t_peek(pq) != NULL; i++)
  90. if (!TEST_size_t_eq(*ossl_pqueue_size_t_peek(pq), sorted[i])
  91. || !TEST_size_t_eq(*ossl_pqueue_size_t_pop(pq), sorted[i]))
  92. goto err;
  93. if (popfree) {
  94. num_rec_freed = 0;
  95. n = ossl_pqueue_size_t_num(pq);
  96. ossl_pqueue_size_t_pop_free(pq, &free_checker);
  97. pq = NULL;
  98. if (!TEST_size_t_eq(num_rec_freed, n))
  99. goto err;
  100. }
  101. res = 1;
  102. err:
  103. ossl_pqueue_size_t_free(pq);
  104. return res;
  105. }
  106. static const int test_size_t_priority_counts[] = {
  107. 10, 11, 6, 5, 3, 1, 2, 7500
  108. };
  109. static int test_size_t_priority_queue(int n)
  110. {
  111. int reserve, order, count, remove, random, popfree;
  112. count = n % OSSL_NELEM(test_size_t_priority_counts);
  113. n /= OSSL_NELEM(test_size_t_priority_counts);
  114. order = n % 3;
  115. n /= 3;
  116. random = n % 2;
  117. n /= 2;
  118. reserve = n % 2;
  119. n /= 2;
  120. remove = n % 6;
  121. n /= 6;
  122. popfree = n % 2;
  123. count = test_size_t_priority_counts[count];
  124. return test_size_t_priority_queue_int(reserve, order, count, remove,
  125. random, popfree);
  126. }
  127. static int test_large_priority_queue(void)
  128. {
  129. return test_size_t_priority_queue_int(0, 0, MAX_SAMPLES, MAX_SAMPLES / 100,
  130. 1, 1);
  131. }
  132. typedef struct info_st {
  133. uint64_t seq_num, sub_seq;
  134. size_t idx;
  135. } INFO;
  136. DEFINE_PRIORITY_QUEUE_OF(INFO);
  137. static int cmp(const INFO *a, const INFO *b)
  138. {
  139. if (a->seq_num < b->seq_num)
  140. return -1;
  141. if (a->seq_num > b->seq_num)
  142. return 1;
  143. if (a->sub_seq < b->sub_seq)
  144. return -1;
  145. if (a->sub_seq > b->sub_seq)
  146. return 1;
  147. return 0;
  148. }
  149. static int test_22644(void)
  150. {
  151. size_t i;
  152. INFO infos[32];
  153. int res = 0;
  154. PRIORITY_QUEUE_OF(INFO) *pq = ossl_pqueue_INFO_new(cmp);
  155. memset(infos, 0, sizeof(infos));
  156. for (i = 0; i < 32; ++i)
  157. infos[i].sub_seq = i;
  158. infos[0].seq_num = 70650219160667140;
  159. if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[0], &infos[0].idx))
  160. || !TEST_size_t_eq(infos[0].idx, 7)
  161. || !TEST_ptr(ossl_pqueue_INFO_remove(pq, infos[0].idx)))
  162. goto err;
  163. infos[1].seq_num = 289360691352306692;
  164. if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[1], &infos[1].idx))
  165. || !TEST_size_t_eq(infos[1].idx, 7)
  166. || !TEST_ptr(ossl_pqueue_INFO_remove(pq, infos[1].idx)))
  167. goto err;
  168. infos[2].seq_num = 289360691352306692;
  169. if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[2], &infos[2].idx))
  170. || !TEST_size_t_eq(infos[2].idx, 7))
  171. goto err;
  172. infos[3].seq_num = 289360691352306692;
  173. if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[3], &infos[3].idx))
  174. || !TEST_size_t_eq(infos[3].idx, 6))
  175. goto err;
  176. infos[4].seq_num = 289360691352306692;
  177. if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[4], &infos[4].idx))
  178. || !TEST_size_t_eq(infos[4].idx, 5))
  179. goto err;
  180. infos[5].seq_num = 289360691352306692;
  181. if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[5], &infos[5].idx))
  182. || !TEST_size_t_eq(infos[5].idx, 4))
  183. goto err;
  184. infos[6].seq_num = 289360691352306692;
  185. if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[6], &infos[6].idx))
  186. || !TEST_size_t_eq(infos[6].idx, 3))
  187. goto err;
  188. infos[7].seq_num = 289360691352306692;
  189. if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[7], &infos[7].idx))
  190. || !TEST_size_t_eq(infos[7].idx, 2))
  191. goto err;
  192. infos[8].seq_num = 289360691352306692;
  193. if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[8], &infos[8].idx))
  194. || !TEST_size_t_eq(infos[8].idx, 1))
  195. goto err;
  196. if (!TEST_ptr(ossl_pqueue_INFO_pop(pq))
  197. || !TEST_ptr(ossl_pqueue_INFO_pop(pq))) /* crash if bug present */
  198. goto err;
  199. res = 1;
  200. err:
  201. ossl_pqueue_INFO_free(pq);
  202. return res;
  203. }
  204. int setup_tests(void)
  205. {
  206. ADD_ALL_TESTS(test_size_t_priority_queue,
  207. OSSL_NELEM(test_size_t_priority_counts) /* count */
  208. * 3 /* order */
  209. * 2 /* random */
  210. * 2 /* reserve */
  211. * 6 /* remove */
  212. * 2); /* pop & free */
  213. ADD_TEST(test_large_priority_queue);
  214. ADD_TEST(test_22644);
  215. return 1;
  216. }