2 * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved.
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
13 #include <openssl/opensslconf.h>
14 #include <internal/priority_queue.h>
15 #include <openssl/err.h>
16 #include <openssl/crypto.h>
18 #include "internal/nelem.h"
21 #define MAX_SAMPLES 500000
23 DEFINE_PRIORITY_QUEUE_OF(size_t);
25 static size_t num_rec_freed;
27 static int size_t_compare(const size_t *a, const size_t *b)
36 static int qsort_size_t_compare(const void *a, const void *b)
38 return size_t_compare((size_t *)a, (size_t *)b);
41 static int qsort_size_t_compare_rev(const void *a, const void *b)
43 return size_t_compare((size_t *)b, (size_t *)a);
46 static void free_checker(ossl_unused size_t *p)
51 static int test_size_t_priority_queue_int(int reserve, int order, int count,
52 int remove, int random, int popfree)
54 PRIORITY_QUEUE_OF(size_t) *pq = NULL;
55 static size_t values[MAX_SAMPLES], sorted[MAX_SAMPLES], ref[MAX_SAMPLES];
58 static const char *orders[3] = { "unordered", "ascending", "descending" };
60 TEST_info("testing count %d, %s, %s, values %s, remove %d, %sfree",
61 count, orders[order], reserve ? "reserve" : "grow",
62 random ? "random" : "deterministic", remove,
63 popfree ? "pop " : "");
65 if (!TEST_size_t_le(count, MAX_SAMPLES))
68 memset(values, 0, sizeof(values));
69 memset(sorted, 0, sizeof(sorted));
70 memset(ref, 0, sizeof(ref));
72 for (i = 0; i < count; i++)
73 values[i] = random ? test_random() : (size_t)(count - i);
74 memcpy(sorted, values, sizeof(*sorted) * count);
75 qsort(sorted, count, sizeof(*sorted), &qsort_size_t_compare);
78 memcpy(values, sorted, sizeof(*values) * count);
80 qsort(values, count, sizeof(*values), &qsort_size_t_compare_rev);
82 if (!TEST_ptr(pq = ossl_pqueue_size_t_new(&size_t_compare))
83 || !TEST_size_t_eq(ossl_pqueue_size_t_num(pq), 0))
86 if (reserve && !TEST_true(ossl_pqueue_size_t_reserve(pq, count)))
89 for (i = 0; i < count; i++)
90 if (!TEST_true(ossl_pqueue_size_t_push(pq, values + i, ref + i)))
93 if (!TEST_size_t_eq(*ossl_pqueue_size_t_peek(pq), *sorted)
94 || !TEST_size_t_eq(ossl_pqueue_size_t_num(pq), count))
98 while (remove-- > 0) {
99 i = test_random() % count;
100 if (values[i] != SIZE_MAX) {
101 if (!TEST_ptr_eq(ossl_pqueue_size_t_remove(pq, ref[i]),
104 values[i] = SIZE_MAX;
107 memcpy(sorted, values, sizeof(*sorted) * count);
108 qsort(sorted, count, sizeof(*sorted), &qsort_size_t_compare);
110 for (i = 0; ossl_pqueue_size_t_peek(pq) != NULL; i++)
111 if (!TEST_size_t_eq(*ossl_pqueue_size_t_peek(pq), sorted[i])
112 || !TEST_size_t_eq(*ossl_pqueue_size_t_pop(pq), sorted[i]))
117 n = ossl_pqueue_size_t_num(pq);
118 ossl_pqueue_size_t_pop_free(pq, &free_checker);
120 if (!TEST_size_t_eq(num_rec_freed, n))
125 ossl_pqueue_size_t_free(pq);
129 static const int test_size_t_priority_counts[] = {
130 10, 11, 6, 5, 3, 1, 2, 7500
133 static int test_size_t_priority_queue(int n)
135 int reserve, order, count, remove, random, popfree;
137 count = n % OSSL_NELEM(test_size_t_priority_counts);
138 n /= OSSL_NELEM(test_size_t_priority_counts);
149 count = test_size_t_priority_counts[count];
150 return test_size_t_priority_queue_int(reserve, order, count, remove,
154 static int test_large_priority_queue(void)
156 return test_size_t_priority_queue_int(0, 0, MAX_SAMPLES, MAX_SAMPLES / 100,
160 int setup_tests(void)
162 ADD_ALL_TESTS(test_size_t_priority_queue,
163 OSSL_NELEM(test_size_t_priority_counts) /* count */
168 * 2); /* pop & free */
169 ADD_TEST(test_large_priority_queue);