src/test/test-prioq.c

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   2 /***
   3   This file is part of systemd.
   4
   5   Copyright 2013 Lennart Poettering
   6
   7   systemd is free software; you can redistribute it and/or modify it
   8   under the terms of the GNU Lesser General Public License as published by
   9   the Free Software Foundation; either version 2.1 of the License, or
  10   (at your option) any later version.
  11
  12   systemd is distributed in the hope that it will be useful, but
  13   WITHOUT ANY WARRANTY; without even the implied warranty of
  14   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  15   Lesser General Public License for more details.
  16
  17   You should have received a copy of the GNU Lesser General Public License
  18   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  19 ***/
  20
  21 #include <stdlib.h>
  22
  23 #include "alloc-util.h"
  24 #include "prioq.h"
  25 #include "set.h"
  26 #include "siphash24.h"
  27 #include "util.h"
  28
  29 #define SET_SIZE 1024*4
  30
  31 static int unsigned_compare(const void *a, const void *b) {
  32         const unsigned *x = a, *y = b;
  33
  34         if (*x < *y)
  35                 return -1;
  36
  37         if (*x > *y)
  38                 return 1;
  39
  40         return 0;
  41 }
  42
  43 static void test_unsigned(void) {
  44         unsigned buffer[SET_SIZE], i;
  45         Prioq *q;
  46
  47         srand(0);
  48
  49         q = prioq_new(trivial_compare_func);
  50         assert_se(q);
  51
  52         for (i = 0; i < ELEMENTSOF(buffer); i++) {
  53                 unsigned u;
  54
  55                 u = (unsigned) rand();
  56                 buffer[i] = u;
  57                 assert_se(prioq_put(q, UINT_TO_PTR(u), NULL) >= 0);
  58         }
  59
  60         qsort(buffer, ELEMENTSOF(buffer), sizeof(buffer[0]), unsigned_compare);
  61
  62         for (i = 0; i < ELEMENTSOF(buffer); i++) {
  63                 unsigned u;
  64
  65                 assert_se(prioq_size(q) == ELEMENTSOF(buffer) - i);
  66
  67                 u = PTR_TO_UINT(prioq_pop(q));
  68                 assert_se(buffer[i] == u);
  69         }
  70
  71         assert_se(prioq_isempty(q));
  72         prioq_free(q);
  73 }
  74
  75 struct test {
  76         unsigned value;
  77         unsigned idx;
  78 };
  79
  80 static int test_compare(const void *a, const void *b) {
  81         const struct test *x = a, *y = b;
  82
  83         if (x->value < y->value)
  84                 return -1;
  85
  86         if (x->value > y->value)
  87                 return 1;
  88
  89         return 0;
  90 }
  91
  92 static void test_hash(const void *a, struct siphash *state) {
  93         const struct test *x = a;
  94
  95         siphash24_compress(&x->value, sizeof(x->value), state);
  96 }
  97
  98 static const struct hash_ops test_hash_ops = {
  99         .hash = test_hash,
 100         .compare = test_compare
 101 };
 102
 103 static void test_struct(void) {
 104         Prioq *q;
 105         Set *s;
 106         unsigned previous = 0, i;
 107         int r;
 108
 109         srand(0);
 110
 111         q = prioq_new(test_compare);
 112         assert_se(q);
 113
 114         s = set_new(&test_hash_ops);
 115         assert_se(s);
 116
 117         for (i = 0; i < SET_SIZE; i++) {
 118                 struct test *t;
 119
 120                 t = new0(struct test, 1);
 121                 assert_se(t);
 122                 t->value = (unsigned) rand();
 123
 124                 r = prioq_put(q, t, &t->idx);
 125                 assert_se(r >= 0);
 126
 127                 if (i % 4 == 0) {
 128                         r = set_consume(s, t);
 129                         assert_se(r >= 0);
 130                 }
 131         }
 132
 133         for (;;) {
 134                 struct test *t;
 135
 136                 t = set_steal_first(s);
 137                 if (!t)
 138                         break;
 139
 140                 r = prioq_remove(q, t, &t->idx);
 141                 assert_se(r > 0);
 142
 143                 free(t);
 144         }
 145
 146         for (i = 0; i < SET_SIZE * 3 / 4; i++) {
 147                 struct test *t;
 148
 149                 assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i);
 150
 151                 t = prioq_pop(q);
 152                 assert_se(t);
 153
 154                 assert_se(previous <= t->value);
 155                 previous = t->value;
 156                 free(t);
 157         }
 158
 159         assert_se(prioq_isempty(q));
 160         prioq_free(q);
 161
 162         assert_se(set_isempty(s));
 163         set_free(s);
 164 }
 165
 166 int main(int argc, char* argv[]) {
 167
 168         test_unsigned();
 169         test_struct();
 170
 171         return 0;
 172 }