src/test/test-prioq.c

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