src/test/test-prioq.c

   1 /* SPDX-License-Identifier: LGPL-2.1-or-later */
   2
   3 #include <stdlib.h>
   4
   5 #include "alloc-util.h"
   6 #include "prioq.h"
   7 #include "set.h"
   8 #include "siphash24.h"
   9 #include "sort-util.h"
  10 #include "tests.h"
  11
  12 #define SET_SIZE 1024*4
  13
  14 static int unsigned_compare(const unsigned *a, const unsigned *b) {
  15         return CMP(*a, *b);
  16 }
  17
  18 TEST(unsigned) {
  19         _cleanup_(prioq_freep) Prioq *q = NULL;
  20         unsigned buffer[SET_SIZE], u, n;
  21
  22         srand(0);
  23
  24         assert_se(q = prioq_new(trivial_compare_func));
  25
  26         FOREACH_ELEMENT(i, buffer) {
  27                 u = (unsigned) rand();
  28                 *i = u;
  29                 assert_se(prioq_put(q, UINT_TO_PTR(u), NULL) >= 0);
  30
  31                 n = prioq_size(q);
  32                 assert_se(prioq_remove(q, UINT_TO_PTR(u), &n) == 0);
  33         }
  34
  35         typesafe_qsort(buffer, ELEMENTSOF(buffer), unsigned_compare);
  36
  37         for (unsigned i = 0; i < ELEMENTSOF(buffer); i++) {
  38                 assert_se(prioq_size(q) == ELEMENTSOF(buffer) - i);
  39
  40                 u = PTR_TO_UINT(prioq_pop(q));
  41                 assert_se(buffer[i] == u);
  42         }
  43
  44         assert_se(prioq_isempty(q));
  45 }
  46
  47 struct test {
  48         unsigned value;
  49         unsigned idx;
  50 };
  51
  52 static int test_compare(const struct test *x, const struct test *y) {
  53         return CMP(x->value, y->value);
  54 }
  55
  56 static void test_hash(const struct test *x, struct siphash *state) {
  57         siphash24_compress_typesafe(x->value, state);
  58 }
  59
  60 DEFINE_PRIVATE_HASH_OPS(test_hash_ops, struct test, test_hash, test_compare);
  61
  62 TEST(struct) {
  63         _cleanup_(prioq_freep) Prioq *q = NULL;
  64         _cleanup_set_free_ Set *s = NULL;
  65         unsigned previous = 0, i;
  66         struct test *t;
  67
  68         srand(0);
  69
  70         assert_se(q = prioq_new((compare_func_t) test_compare));
  71         assert_se(s = set_new(&test_hash_ops));
  72
  73         ASSERT_NULL(prioq_peek(q));
  74         ASSERT_NULL(prioq_peek_by_index(q, 0));
  75         ASSERT_NULL(prioq_peek_by_index(q, 1));
  76         ASSERT_NULL(prioq_peek_by_index(q, UINT_MAX));
  77
  78         for (i = 0; i < SET_SIZE; i++) {
  79                 assert_se(t = new0(struct test, 1));
  80                 t->value = (unsigned) rand();
  81
  82                 assert_se(prioq_put(q, t, &t->idx) >= 0);
  83
  84                 if (i % 4 == 0)
  85                         assert_se(set_consume(s, t) >= 0);
  86         }
  87
  88         for (i = 0; i < SET_SIZE; i++)
  89                 assert_se(prioq_peek_by_index(q, i));
  90         ASSERT_NULL(prioq_peek_by_index(q, SET_SIZE));
  91
  92         unsigned count = 0;
  93         PRIOQ_FOREACH_ITEM(q, t) {
  94                 assert_se(t);
  95                 count++;
  96         }
  97         assert_se(count == SET_SIZE);
  98
  99         while ((t = set_steal_first(s))) {
 100                 assert_se(prioq_remove(q, t, &t->idx) == 1);
 101                 assert_se(prioq_remove(q, t, &t->idx) == 0);
 102                 assert_se(prioq_remove(q, t, NULL) == 0);
 103
 104                 free(t);
 105         }
 106
 107         for (i = 0; i < SET_SIZE * 3 / 4; i++) {
 108                 assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i);
 109
 110                 assert_se(t = prioq_pop(q));
 111                 assert_se(prioq_remove(q, t, &t->idx) == 0);
 112                 assert_se(prioq_remove(q, t, NULL) == 0);
 113                 assert_se(previous <= t->value);
 114
 115                 previous = t->value;
 116                 free(t);
 117         }
 118
 119         assert_se(prioq_isempty(q));
 120         assert_se(set_isempty(s));
 121 }
 122
 123 DEFINE_TEST_MAIN(LOG_INFO);