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
);