test/priority_queue_test.c

   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
  10 #include <stdio.h>
  11 #include <string.h>
  12
  13 #include <openssl/opensslconf.h>
  14 #include <internal/priority_queue.h>
  15 #include <openssl/err.h>
  16 #include <openssl/crypto.h>
  17
  18 #include "internal/nelem.h"
  19 #include "testutil.h"
  20
  21 #define MAX_SAMPLES 500000
  22
  23 DEFINE_PRIORITY_QUEUE_OF(size_t);
  24
  25 static size_t num_rec_freed;
  26
  27 static int size_t_compare(const size_t *a, const size_t *b)
  28 {
  29     if (*a < *b)
  30         return -1;
  31     if (*a > *b)
  32         return 1;
  33     return 0;
  34 }
  35
  36 static int qsort_size_t_compare(const void *a, const void *b)
  37 {
  38     return size_t_compare((size_t *)a, (size_t *)b);
  39 }
  40
  41 static int qsort_size_t_compare_rev(const void *a, const void *b)
  42 {
  43     return size_t_compare((size_t *)b, (size_t *)a);
  44 }
  45
  46 static void free_checker(ossl_unused size_t *p)
  47 {
  48     num_rec_freed++;
  49 }
  50
  51 static int test_size_t_priority_queue_int(int reserve, int order, int count,
  52                                           int remove, int random, int popfree)
  53 {
  54     PRIORITY_QUEUE_OF(size_t) *pq = NULL;
  55     static size_t values[MAX_SAMPLES], sorted[MAX_SAMPLES], ref[MAX_SAMPLES];
  56     size_t n;
  57     int i, res = 0;
  58     static const char *orders[3] = { "unordered", "ascending", "descending" };
  59
  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 " : "");
  64
  65     if (!TEST_size_t_le(count, MAX_SAMPLES))
  66         return 0;
  67
  68     memset(values, 0, sizeof(values));
  69     memset(sorted, 0, sizeof(sorted));
  70     memset(ref, 0, sizeof(ref));
  71
  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);
  76
  77     if (order == 1)
  78         memcpy(values, sorted, sizeof(*values) * count);
  79     else if (order == 2)
  80         qsort(values, count, sizeof(*values), &qsort_size_t_compare_rev);
  81
  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))
  84         goto err;
  85
  86     if (reserve && !TEST_true(ossl_pqueue_size_t_reserve(pq, count)))
  87         goto err;
  88
  89     for (i = 0; i < count; i++)
  90         if (!TEST_true(ossl_pqueue_size_t_push(pq, values + i, ref + i)))
  91             goto err;
  92
  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))
  95         goto err;
  96
  97     if (remove) {
  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]),
 102                                  values + i))
 103                     goto err;
 104                 values[i] = SIZE_MAX;
 105             }
 106         }
 107         memcpy(sorted, values, sizeof(*sorted) * count);
 108         qsort(sorted, count, sizeof(*sorted), &qsort_size_t_compare);
 109     }
 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]))
 113                 goto err;
 114
 115     if (popfree) {
 116         num_rec_freed = 0;
 117         n = ossl_pqueue_size_t_num(pq);
 118         ossl_pqueue_size_t_pop_free(pq, &free_checker);
 119         pq = NULL;
 120         if (!TEST_size_t_eq(num_rec_freed, n))
 121             goto err;
 122     }
 123     res = 1;
 124  err:
 125     ossl_pqueue_size_t_free(pq);
 126     return res;
 127 }
 128
 129 static const int test_size_t_priority_counts[] = {
 130     10, 11, 6, 5, 3, 1, 2, 7500
 131 };
 132
 133 static int test_size_t_priority_queue(int n)
 134 {
 135     int reserve, order, count, remove, random, popfree;
 136
 137     count = n % OSSL_NELEM(test_size_t_priority_counts);
 138     n /= OSSL_NELEM(test_size_t_priority_counts);
 139     order = n % 3;
 140     n /= 3;
 141     random = n % 2;
 142     n /= 2;
 143     reserve = n % 2;
 144     n /= 2;
 145     remove = n % 6;
 146     n /= 6;
 147     popfree = n % 2;
 148
 149     count = test_size_t_priority_counts[count];
 150     return test_size_t_priority_queue_int(reserve, order, count, remove,
 151                                           random, popfree);
 152 }
 153
 154 static int test_large_priority_queue(void)
 155 {
 156     return test_size_t_priority_queue_int(0, 0, MAX_SAMPLES, MAX_SAMPLES / 100,
 157                                           1, 1);
 158 }
 159
 160 typedef struct info_st {
 161     uint64_t seq_num, sub_seq;
 162     size_t   idx;
 163 } INFO;
 164
 165 DEFINE_PRIORITY_QUEUE_OF(INFO);
 166
 167 static int cmp(const INFO *a, const INFO *b)
 168 {
 169     if (a->seq_num < b->seq_num)
 170         return -1;
 171     if (a->seq_num > b->seq_num)
 172         return 1;
 173     if (a->sub_seq < b->sub_seq)
 174         return -1;
 175     if (a->sub_seq > b->sub_seq)
 176         return 1;
 177     return 0;
 178 }
 179
 180 static int test_22644(void)
 181 {
 182     size_t i;
 183     INFO infos[32];
 184     int res = 0;
 185     PRIORITY_QUEUE_OF(INFO) *pq = ossl_pqueue_INFO_new(cmp);
 186
 187     memset(infos, 0, sizeof(infos));
 188     for (i = 0; i < 32; ++i)
 189         infos[i].sub_seq = i;
 190
 191     infos[0].seq_num = 70650219160667140;
 192     if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[0], &infos[0].idx))
 193             || !TEST_size_t_eq(infos[0].idx, 7)
 194             || !TEST_ptr(ossl_pqueue_INFO_remove(pq, infos[0].idx)))
 195         goto err;
 196
 197     infos[1].seq_num = 289360691352306692;
 198     if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[1], &infos[1].idx))
 199             || !TEST_size_t_eq(infos[1].idx, 7)
 200             || !TEST_ptr(ossl_pqueue_INFO_remove(pq, infos[1].idx)))
 201         goto err;
 202
 203     infos[2].seq_num = 289360691352306692;
 204     if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[2], &infos[2].idx))
 205             || !TEST_size_t_eq(infos[2].idx, 7))
 206         goto err;
 207
 208     infos[3].seq_num = 289360691352306692;
 209     if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[3], &infos[3].idx))
 210             || !TEST_size_t_eq(infos[3].idx, 6))
 211         goto err;
 212
 213     infos[4].seq_num = 289360691352306692;
 214     if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[4], &infos[4].idx))
 215             || !TEST_size_t_eq(infos[4].idx, 5))
 216         goto err;
 217
 218     infos[5].seq_num = 289360691352306692;
 219     if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[5], &infos[5].idx))
 220             || !TEST_size_t_eq(infos[5].idx, 4))
 221         goto err;
 222
 223     infos[6].seq_num = 289360691352306692;
 224     if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[6], &infos[6].idx))
 225             || !TEST_size_t_eq(infos[6].idx, 3))
 226         goto err;
 227
 228     infos[7].seq_num = 289360691352306692;
 229     if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[7], &infos[7].idx))
 230             || !TEST_size_t_eq(infos[7].idx, 2))
 231         goto err;
 232
 233     infos[8].seq_num = 289360691352306692;
 234     if (!TEST_true(ossl_pqueue_INFO_push(pq, &infos[8], &infos[8].idx))
 235             || !TEST_size_t_eq(infos[8].idx, 1))
 236         goto err;
 237
 238     if (!TEST_ptr(ossl_pqueue_INFO_pop(pq))
 239             || !TEST_ptr(ossl_pqueue_INFO_pop(pq)))     /* crash if bug present */
 240         goto err;
 241     res = 1;
 242
 243  err:
 244     ossl_pqueue_INFO_free(pq);
 245     return res;
 246 }
 247
 248 int setup_tests(void)
 249 {
 250     ADD_ALL_TESTS(test_size_t_priority_queue,
 251                   OSSL_NELEM(test_size_t_priority_counts)   /* count */
 252                   * 3                                       /* order */
 253                   * 2                                       /* random */
 254                   * 2                                       /* reserve */
 255                   * 6                                       /* remove */
 256                   * 2);                                     /* pop & free */
 257     ADD_TEST(test_large_priority_queue);
 258     ADD_TEST(test_22644);
 259     return 1;
 260 }