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