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 void test_struct(void) {
 102         Prioq *q;
 103         Set *s;
 104         unsigned previous = 0, i;
 105         int r;
 106
 107         srand(0);
 108
 109         q = prioq_new(test_compare);
 110         assert_se(q);
 111
 112         s = set_new(test_hash, test_compare);
 113         assert_se(s);
 114
 115         for (i = 0; i < SET_SIZE; i++) {
 116                 struct test *t;
 117
 118                 t = new0(struct test, 1);
 119                 assert_se(t);
 120                 t->value = (unsigned) rand();
 121
 122                 r = prioq_put(q, t, &t->idx);
 123                 assert_se(r >= 0);
 124
 125                 if (i % 4 == 0) {
 126                         r = set_consume(s, t);
 127                         assert_se(r >= 0);
 128                 }
 129         }
 130
 131         for (;;) {
 132                 struct test *t;
 133
 134                 t = set_steal_first(s);
 135                 if (!t)
 136                         break;
 137
 138                 r = prioq_remove(q, t, &t->idx);
 139                 assert_se(r > 0);
 140
 141                 free(t);
 142         }
 143
 144         for (i = 0; i < SET_SIZE * 3 / 4; i++) {
 145                 struct test *t;
 146
 147                 assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i);
 148
 149                 t = prioq_pop(q);
 150                 assert_se(t);
 151
 152                 assert_se(previous <= t->value);
 153                 previous = t->value;
 154                 free(t);
 155         }
 156
 157         assert_se(prioq_isempty(q));
 158         prioq_free(q);
 159
 160         assert_se(set_isempty(s));
 161         set_free(s);
 162 }
 163
 164 int main(int argc, char* argv[]) {
 165
 166         test_unsigned();
 167         test_struct();
 168
 169         return 0;
 170 }