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