src/test/test-prioq.c

   1 /* SPDX-License-Identifier: LGPL-2.1+ */
   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 "util.h"
  10
  11 #define SET_SIZE 1024*4
  12
  13 static int unsigned_compare(const void *a, const void *b) {
  14         const unsigned *x = a, *y = b;
  15
  16         if (*x < *y)
  17                 return -1;
  18
  19         if (*x > *y)
  20                 return 1;
  21
  22         return 0;
  23 }
  24
  25 static void test_unsigned(void) {
  26         unsigned buffer[SET_SIZE], i;
  27         Prioq *q;
  28
  29         srand(0);
  30
  31         q = prioq_new(trivial_compare_func);
  32         assert_se(q);
  33
  34         for (i = 0; i < ELEMENTSOF(buffer); i++) {
  35                 unsigned u;
  36
  37                 u = (unsigned) rand();
  38                 buffer[i] = u;
  39                 assert_se(prioq_put(q, UINT_TO_PTR(u), NULL) >= 0);
  40         }
  41
  42         qsort(buffer, ELEMENTSOF(buffer), sizeof(buffer[0]), unsigned_compare);
  43
  44         for (i = 0; i < ELEMENTSOF(buffer); i++) {
  45                 unsigned u;
  46
  47                 assert_se(prioq_size(q) == ELEMENTSOF(buffer) - i);
  48
  49                 u = PTR_TO_UINT(prioq_pop(q));
  50                 assert_se(buffer[i] == u);
  51         }
  52
  53         assert_se(prioq_isempty(q));
  54         prioq_free(q);
  55 }
  56
  57 struct test {
  58         unsigned value;
  59         unsigned idx;
  60 };
  61
  62 static int test_compare(const void *a, const void *b) {
  63         const struct test *x = a, *y = b;
  64
  65         if (x->value < y->value)
  66                 return -1;
  67
  68         if (x->value > y->value)
  69                 return 1;
  70
  71         return 0;
  72 }
  73
  74 static void test_hash(const void *a, struct siphash *state) {
  75         const struct test *x = a;
  76
  77         siphash24_compress(&x->value, sizeof(x->value), state);
  78 }
  79
  80 static const struct hash_ops test_hash_ops = {
  81         .hash = test_hash,
  82         .compare = test_compare
  83 };
  84
  85 static void test_struct(void) {
  86         Prioq *q;
  87         Set *s;
  88         unsigned previous = 0, i;
  89         int r;
  90
  91         srand(0);
  92
  93         q = prioq_new(test_compare);
  94         assert_se(q);
  95
  96         s = set_new(&test_hash_ops);
  97         assert_se(s);
  98
  99         for (i = 0; i < SET_SIZE; i++) {
 100                 struct test *t;
 101
 102                 t = new0(struct test, 1);
 103                 assert_se(t);
 104                 t->value = (unsigned) rand();
 105
 106                 r = prioq_put(q, t, &t->idx);
 107                 assert_se(r >= 0);
 108
 109                 if (i % 4 == 0) {
 110                         r = set_consume(s, t);
 111                         assert_se(r >= 0);
 112                 }
 113         }
 114
 115         for (;;) {
 116                 struct test *t;
 117
 118                 t = set_steal_first(s);
 119                 if (!t)
 120                         break;
 121
 122                 r = prioq_remove(q, t, &t->idx);
 123                 assert_se(r > 0);
 124
 125                 free(t);
 126         }
 127
 128         for (i = 0; i < SET_SIZE * 3 / 4; i++) {
 129                 struct test *t;
 130
 131                 assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i);
 132
 133                 t = prioq_pop(q);
 134                 assert_se(t);
 135
 136                 assert_se(previous <= t->value);
 137                 previous = t->value;
 138                 free(t);
 139         }
 140
 141         assert_se(prioq_isempty(q));
 142         prioq_free(q);
 143
 144         assert_se(set_isempty(s));
 145         set_free(s);
 146 }
 147
 148 int main(int argc, char* argv[]) {
 149
 150         test_unsigned();
 151         test_struct();
 152
 153         return 0;
 154 }