From f0a4935827db5527d23da61805a1e73f0c660d39 Mon Sep 17 00:00:00 2001 From: Pauli Date: Mon, 15 Nov 2021 08:32:55 +1000 Subject: [PATCH] test: add priority queue unit test Reviewed-by: Tomas Mraz Reviewed-by: Matt Caswell (Merged from https://github.com/openssl/openssl/pull/18274) --- test/build.info | 10 ++ test/priority_queue_test.c | 171 ++++++++++++++++++++++++++ test/recipes/02-test_priority_queue.t | 19 +++ 3 files changed, 200 insertions(+) create mode 100644 test/priority_queue_test.c create mode 100644 test/recipes/02-test_priority_queue.t diff --git a/test/build.info b/test/build.info index 0f7420825e4..2721945197a 100644 --- a/test/build.info +++ b/test/build.info @@ -69,6 +69,10 @@ IF[{- !$disabled{tests} -}] PROGRAMS{noinst}=enginetest ENDIF + IF[{- !$disabled{quic} -}] + PROGRAMS{noinst}=priority_queue_test + ENDIF + SOURCE[confdump]=confdump.c INCLUDE[confdump]=../include ../apps/include DEPEND[confdump]=../libcrypto @@ -703,6 +707,12 @@ IF[{- !$disabled{tests} -}] INCLUDE[sparse_array_test]=../include ../apps/include DEPEND[sparse_array_test]=../libcrypto.a libtestutil.a + IF[{- !$disabled{quic} -}] + SOURCE[priority_queue_test]=priority_queue_test.c + INCLUDE[priority_queue_test]=../include ../apps/include + DEPEND[priority_queue_test]=../libssl.a ../libcrypto.a libtestutil.a + ENDIF + SOURCE[dhtest]=dhtest.c INCLUDE[dhtest]=../include ../apps/include DEPEND[dhtest]=../libcrypto.a libtestutil.a diff --git a/test/priority_queue_test.c b/test/priority_queue_test.c new file mode 100644 index 00000000000..7ff618a3988 --- /dev/null +++ b/test/priority_queue_test.c @@ -0,0 +1,171 @@ +/* + * Copyright 2022 The OpenSSL Project Authors. All Rights Reserved. + * + * Licensed under the Apache License 2.0 (the "License"). You may not use + * this file except in compliance with the License. You can obtain a copy + * in the file LICENSE in the source distribution or at + * https://www.openssl.org/source/license.html + */ + +#include +#include + +#include +#include +#include +#include + +#include "internal/nelem.h" +#include "testutil.h" + +#define MAX_SAMPLES 500000 + +DEFINE_PRIORITY_QUEUE_OF(size_t); + +static size_t num_rec_freed; + +static int size_t_compare(const size_t *a, const size_t *b) +{ + if (*a < *b) + return -1; + if (*a > *b) + return 1; + return 0; +} + +static int qsort_size_t_compare(const void *a, const void *b) +{ + return size_t_compare((size_t *)a, (size_t *)b); +} + +static int qsort_size_t_compare_rev(const void *a, const void *b) +{ + return size_t_compare((size_t *)b, (size_t *)a); +} + +static void free_checker(ossl_unused size_t *p) +{ + num_rec_freed++; +} + +static int test_size_t_priority_queue_int(int reserve, int order, int count, + int remove, int random, int popfree) +{ + PRIORITY_QUEUE_OF(size_t) *pq = NULL; + static size_t values[MAX_SAMPLES], sorted[MAX_SAMPLES], ref[MAX_SAMPLES]; + size_t n; + int i, res = 0; + static const char *orders[3] = { "unordered", "ascending", "descending" }; + + TEST_info("testing count %d, %s, %s, values %s, remove %d, %sfree", + count, orders[order], reserve ? "reserve" : "grow", + random ? "random" : "deterministic", remove, + popfree ? "pop " : ""); + + if (!TEST_size_t_le(count, MAX_SAMPLES)) + return 0; + + memset(values, 0, sizeof(values)); + memset(sorted, 0, sizeof(sorted)); + memset(ref, 0, sizeof(ref)); + + for (i = 0; i < count; i++) + values[i] = random ? test_random() : (size_t)(count - i); + memcpy(sorted, values, sizeof(*sorted) * count); + qsort(sorted, count, sizeof(*sorted), &qsort_size_t_compare); + + if (order == 1) + memcpy(values, sorted, sizeof(*values) * count); + else if (order == 2) + qsort(values, count, sizeof(*values), &qsort_size_t_compare_rev); + + if (!TEST_ptr(pq = ossl_pqueue_size_t_new(&size_t_compare)) + || !TEST_size_t_eq(ossl_pqueue_size_t_num(pq), 0)) + goto err; + + if (reserve && !TEST_true(ossl_pqueue_size_t_reserve(pq, count))) + goto err; + + for (i = 0; i < count; i++) + if (!TEST_true(ossl_pqueue_size_t_push(pq, values + i, ref + i))) + goto err; + + if (!TEST_size_t_eq(*ossl_pqueue_size_t_peek(pq), *sorted) + || !TEST_size_t_eq(ossl_pqueue_size_t_num(pq), count)) + goto err; + + if (remove) { + while (remove-- > 0) { + i = test_random() % count; + if (values[i] != SIZE_MAX) { + if (!TEST_ptr_eq(ossl_pqueue_size_t_remove(pq, ref[i]), + values + i)) + goto err; + values[i] = SIZE_MAX; + } + } + memcpy(sorted, values, sizeof(*sorted) * count); + qsort(sorted, count, sizeof(*sorted), &qsort_size_t_compare); + } + for (i = 0; ossl_pqueue_size_t_peek(pq) != NULL; i++) + if (!TEST_size_t_eq(*ossl_pqueue_size_t_peek(pq), sorted[i]) + || !TEST_size_t_eq(*ossl_pqueue_size_t_pop(pq), sorted[i])) + goto err; + + if (popfree) { + num_rec_freed = 0; + n = ossl_pqueue_size_t_num(pq); + ossl_pqueue_size_t_pop_free(pq, &free_checker); + pq = NULL; + if (!TEST_size_t_eq(num_rec_freed, n)) + goto err; + } + res = 1; + err: + ossl_pqueue_size_t_free(pq); + return res; +} + +static const int test_size_t_priority_counts[] = { + 10, 11, 6, 5, 3, 1, 2, 7500 +}; + +static int test_size_t_priority_queue(int n) +{ + int reserve, order, count, remove, random, popfree; + + count = n % OSSL_NELEM(test_size_t_priority_counts); + n /= OSSL_NELEM(test_size_t_priority_counts); + order = n % 3; + n /= 3; + random = n % 2; + n /= 2; + reserve = n % 2; + n /= 2; + remove = n % 6; + n /= 6; + popfree = n % 2; + + count = test_size_t_priority_counts[count]; + return test_size_t_priority_queue_int(reserve, order, count, remove, + random, popfree); +} + +static int test_large_priority_queue(void) +{ + return test_size_t_priority_queue_int(0, 0, MAX_SAMPLES, MAX_SAMPLES / 100, + 1, 1); +} + +int setup_tests(void) +{ + ADD_ALL_TESTS(test_size_t_priority_queue, + OSSL_NELEM(test_size_t_priority_counts) /* count */ + * 3 /* order */ + * 2 /* random */ + * 2 /* reserve */ + * 6 /* remove */ + * 2); /* pop & free */ + ADD_TEST(test_large_priority_queue); + return 1; +} diff --git a/test/recipes/02-test_priority_queue.t b/test/recipes/02-test_priority_queue.t new file mode 100644 index 00000000000..3caa0b37329 --- /dev/null +++ b/test/recipes/02-test_priority_queue.t @@ -0,0 +1,19 @@ +#! /usr/bin/env perl +# Copyright 2022 The OpenSSL Project Authors. All Rights Reserved. +# +# Licensed under the Apache License 2.0 (the "License"). You may not use +# this file except in compliance with the License. You can obtain a copy +# in the file LICENSE in the source distribution or at +# https://www.openssl.org/source/license.html + +use OpenSSL::Test; +use OpenSSL::Test::Utils; + +setup("test_priority_queue"); + +plan skip_all => "No priority queues tests without QUIC" + if disabled("quic"); + +plan tests => 1; + +ok(run(test(["priority_queue_test"]))); -- 2.47.2