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