src/test/test-prioq.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2013 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include <stdlib.h>
  23
  24 #include "util.h"
  25 #include "set.h"
  26 #include "prioq.h"
  27 #include "siphash24.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 unsigned long test_hash(const void *a, const uint8_t hash_key[HASH_KEY_SIZE]) {
  93         const struct test *x = a;
  94         uint64_t u;
  95
  96         siphash24((uint8_t*) &u, &x->value, sizeof(x->value), hash_key);
  97
  98         return (unsigned long) u;
  99 }
 100
 101 static const struct hash_ops test_hash_ops = {
 102         .hash = test_hash,
 103         .compare = test_compare
 104 };
 105
 106 static void test_struct(void) {
 107         Prioq *q;
 108         Set *s;
 109         unsigned previous = 0, i;
 110         int r;
 111
 112         srand(0);
 113
 114         q = prioq_new(test_compare);
 115         assert_se(q);
 116
 117         s = set_new(&test_hash_ops);
 118         assert_se(s);
 119
 120         for (i = 0; i < SET_SIZE; i++) {
 121                 struct test *t;
 122
 123                 t = new0(struct test, 1);
 124                 assert_se(t);
 125                 t->value = (unsigned) rand();
 126
 127                 r = prioq_put(q, t, &t->idx);
 128                 assert_se(r >= 0);
 129
 130                 if (i % 4 == 0) {
 131                         r = set_consume(s, t);
 132                         assert_se(r >= 0);
 133                 }
 134         }
 135
 136         for (;;) {
 137                 struct test *t;
 138
 139                 t = set_steal_first(s);
 140                 if (!t)
 141                         break;
 142
 143                 r = prioq_remove(q, t, &t->idx);
 144                 assert_se(r > 0);
 145
 146                 free(t);
 147         }
 148
 149         for (i = 0; i < SET_SIZE * 3 / 4; i++) {
 150                 struct test *t;
 151
 152                 assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i);
 153
 154                 t = prioq_pop(q);
 155                 assert_se(t);
 156
 157                 assert_se(previous <= t->value);
 158                 previous = t->value;
 159                 free(t);
 160         }
 161
 162         assert_se(prioq_isempty(q));
 163         prioq_free(q);
 164
 165         assert_se(set_isempty(s));
 166         set_free(s);
 167 }
 168
 169 int main(int argc, char* argv[]) {
 170
 171         test_unsigned();
 172         test_struct();
 173
 174         return 0;
 175 }