src/test/test-prioq.c

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