Branch data     Line data    Source code

       1                 :            : /* SPDX-License-Identifier: LGPL-2.1+ */
       2                 :            : 
       3                 :            : #include <stdlib.h>
       4                 :            : 
       5                 :            : #include "alloc-util.h"
       6                 :            : #include "prioq.h"
       7                 :            : #include "set.h"
       8                 :            : #include "siphash24.h"
       9                 :            : #include "sort-util.h"
      10                 :            : 
      11                 :            : #define SET_SIZE 1024*4
      12                 :            : 
      13                 :     175864 : static int unsigned_compare(const unsigned *a, const unsigned *b) {
      14         [ +  + ]:     175864 :         return CMP(*a, *b);
      15                 :            : }
      16                 :            : 
      17                 :          4 : static void test_unsigned(void) {
      18                 :          4 :         _cleanup_(prioq_freep) Prioq *q = NULL;
      19                 :            :         unsigned buffer[SET_SIZE], i, u, n;
      20                 :            : 
      21                 :          4 :         srand(0);
      22                 :            : 
      23         [ -  + ]:          4 :         assert_se(q = prioq_new(trivial_compare_func));
      24                 :            : 
      25         [ +  + ]:      16388 :         for (i = 0; i < ELEMENTSOF(buffer); i++) {
      26                 :      16384 :                 u = (unsigned) rand();
      27                 :      16384 :                 buffer[i] = u;
      28         [ -  + ]:      16384 :                 assert_se(prioq_put(q, UINT_TO_PTR(u), NULL) >= 0);
      29                 :            : 
      30                 :      16384 :                 n = prioq_size(q);
      31         [ -  + ]:      16384 :                 assert_se(prioq_remove(q, UINT_TO_PTR(u), &n) == 0);
      32                 :            :         }
      33                 :            : 
      34                 :          4 :         typesafe_qsort(buffer, ELEMENTSOF(buffer), unsigned_compare);
      35                 :            : 
      36         [ +  + ]:      16388 :         for (i = 0; i < ELEMENTSOF(buffer); i++) {
      37         [ -  + ]:      16384 :                 assert_se(prioq_size(q) == ELEMENTSOF(buffer) - i);
      38                 :            : 
      39                 :      16384 :                 u = PTR_TO_UINT(prioq_pop(q));
      40         [ -  + ]:      16384 :                 assert_se(buffer[i] == u);
      41                 :            :         }
      42                 :            : 
      43         [ -  + ]:          4 :         assert_se(prioq_isempty(q));
      44                 :          4 : }
      45                 :            : 
      46                 :            : struct test {
      47                 :            :         unsigned value;
      48                 :            :         unsigned idx;
      49                 :            : };
      50                 :            : 
      51                 :     288433 : static int test_compare(const struct test *x, const struct test *y) {
      52         [ +  + ]:     288433 :         return CMP(x->value, y->value);
      53                 :            : }
      54                 :            : 
      55                 :       9920 : static void test_hash(const struct test *x, struct siphash *state) {
      56                 :       9920 :         siphash24_compress(&x->value, sizeof(x->value), state);
      57                 :       9920 : }
      58                 :            : 
      59                 :            : DEFINE_PRIVATE_HASH_OPS(test_hash_ops, struct test, test_hash, test_compare);
      60                 :            : 
      61                 :          4 : static void test_struct(void) {
      62                 :          4 :         _cleanup_(prioq_freep) Prioq *q = NULL;
      63                 :          4 :         _cleanup_(set_freep) Set *s = NULL;
      64                 :          4 :         unsigned previous = 0, i;
      65                 :            :         struct test *t;
      66                 :            : 
      67                 :          4 :         srand(0);
      68                 :            : 
      69         [ -  + ]:          4 :         assert_se(q = prioq_new((compare_func_t) test_compare));
      70         [ -  + ]:          4 :         assert_se(s = set_new(&test_hash_ops));
      71                 :            : 
      72         [ -  + ]:          4 :         assert_se(prioq_peek(q) == NULL);
      73         [ -  + ]:          4 :         assert_se(prioq_peek_by_index(q, 0) == NULL);
      74         [ -  + ]:          4 :         assert_se(prioq_peek_by_index(q, 1) == NULL);
      75         [ -  + ]:          4 :         assert_se(prioq_peek_by_index(q, (unsigned) -1) == NULL);
      76                 :            : 
      77         [ +  + ]:      16388 :         for (i = 0; i < SET_SIZE; i++) {
      78         [ -  + ]:      16384 :                 assert_se(t = new0(struct test, 1));
      79                 :      16384 :                 t->value = (unsigned) rand();
      80                 :            : 
      81         [ -  + ]:      16384 :                 assert_se(prioq_put(q, t, &t->idx) >= 0);
      82                 :            : 
      83         [ +  + ]:      16384 :                 if (i % 4 == 0)
      84         [ -  + ]:       4096 :                         assert_se(set_consume(s, t) >= 0);
      85                 :            :         }
      86                 :            : 
      87         [ +  + ]:      16388 :         for (i = 0; i < SET_SIZE; i++)
      88         [ -  + ]:      16384 :                 assert_se(prioq_peek_by_index(q, i));
      89         [ -  + ]:          4 :         assert_se(prioq_peek_by_index(q, SET_SIZE) == NULL);
      90                 :            : 
      91                 :          4 :         unsigned count = 0;
      92         [ +  + ]:      16388 :         PRIOQ_FOREACH_ITEM(q, t) {
      93         [ -  + ]:      16384 :                 assert_se(t);
      94                 :      16384 :                 count++;
      95                 :            :         }
      96         [ -  + ]:          4 :         assert_se(count == SET_SIZE);
      97                 :            : 
      98         [ +  + ]:       4100 :         while ((t = set_steal_first(s))) {
      99         [ -  + ]:       4096 :                 assert_se(prioq_remove(q, t, &t->idx) == 1);
     100         [ -  + ]:       4096 :                 assert_se(prioq_remove(q, t, &t->idx) == 0);
     101         [ -  + ]:       4096 :                 assert_se(prioq_remove(q, t, NULL) == 0);
     102                 :            : 
     103                 :       4096 :                 free(t);
     104                 :            :         }
     105                 :            : 
     106         [ +  + ]:      12292 :         for (i = 0; i < SET_SIZE * 3 / 4; i++) {
     107         [ -  + ]:      12288 :                 assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i);
     108                 :            : 
     109         [ -  + ]:      12288 :                 assert_se(t = prioq_pop(q));
     110         [ -  + ]:      12288 :                 assert_se(prioq_remove(q, t, &t->idx) == 0);
     111         [ -  + ]:      12288 :                 assert_se(prioq_remove(q, t, NULL) == 0);
     112         [ -  + ]:      12288 :                 assert_se(previous <= t->value);
     113                 :            : 
     114                 :      12288 :                 previous = t->value;
     115                 :      12288 :                 free(t);
     116                 :            :         }
     117                 :            : 
     118         [ -  + ]:          4 :         assert_se(prioq_isempty(q));
     119         [ -  + ]:          4 :         assert_se(set_isempty(s));
     120                 :          4 : }
     121                 :            : 
     122                 :          4 : int main(int argc, char* argv[]) {
     123                 :            : 
     124                 :          4 :         test_unsigned();
     125                 :          4 :         test_struct();
     126                 :            : 
     127                 :          4 :         return 0;
     128                 :            : }