]>
Commit | Line | Data |
---|---|---|
db9ecf05 | 1 | /* SPDX-License-Identifier: LGPL-2.1-or-later */ |
30bdd695 LP |
2 | |
3 | #include <stdlib.h> | |
4 | ||
b5efdb8a | 5 | #include "alloc-util.h" |
30bdd695 | 6 | #include "prioq.h" |
b5efdb8a | 7 | #include "set.h" |
9bf3b535 | 8 | #include "siphash24.h" |
760877e9 | 9 | #include "sort-util.h" |
4f7452a8 | 10 | #include "tests.h" |
30bdd695 LP |
11 | |
12 | #define SET_SIZE 1024*4 | |
13 | ||
93bab288 YW |
14 | static int unsigned_compare(const unsigned *a, const unsigned *b) { |
15 | return CMP(*a, *b); | |
30bdd695 LP |
16 | } |
17 | ||
4f7452a8 | 18 | TEST(unsigned) { |
d13b5f5a | 19 | _cleanup_(prioq_freep) Prioq *q = NULL; |
5023c62e | 20 | unsigned buffer[SET_SIZE], i, u, n; |
30bdd695 LP |
21 | |
22 | srand(0); | |
23 | ||
d13b5f5a | 24 | assert_se(q = prioq_new(trivial_compare_func)); |
30bdd695 LP |
25 | |
26 | for (i = 0; i < ELEMENTSOF(buffer); i++) { | |
30bdd695 LP |
27 | u = (unsigned) rand(); |
28 | buffer[i] = u; | |
29 | assert_se(prioq_put(q, UINT_TO_PTR(u), NULL) >= 0); | |
5023c62e YW |
30 | |
31 | n = prioq_size(q); | |
32 | assert_se(prioq_remove(q, UINT_TO_PTR(u), &n) == 0); | |
30bdd695 LP |
33 | } |
34 | ||
93bab288 | 35 | typesafe_qsort(buffer, ELEMENTSOF(buffer), unsigned_compare); |
30bdd695 LP |
36 | |
37 | for (i = 0; i < ELEMENTSOF(buffer); i++) { | |
30bdd695 LP |
38 | assert_se(prioq_size(q) == ELEMENTSOF(buffer) - i); |
39 | ||
40 | u = PTR_TO_UINT(prioq_pop(q)); | |
41 | assert_se(buffer[i] == u); | |
42 | } | |
43 | ||
44 | assert_se(prioq_isempty(q)); | |
30bdd695 LP |
45 | } |
46 | ||
47 | struct test { | |
48 | unsigned value; | |
49 | unsigned idx; | |
50 | }; | |
51 | ||
7a08d314 | 52 | static int test_compare(const struct test *x, const struct test *y) { |
bbddd2b8 | 53 | return CMP(x->value, y->value); |
30bdd695 LP |
54 | } |
55 | ||
7a08d314 | 56 | static void test_hash(const struct test *x, struct siphash *state) { |
c01a5c05 | 57 | siphash24_compress_typesafe(x->value, state); |
30bdd695 LP |
58 | } |
59 | ||
7a08d314 | 60 | DEFINE_PRIVATE_HASH_OPS(test_hash_ops, struct test, test_hash, test_compare); |
d5099efc | 61 | |
4f7452a8 | 62 | TEST(struct) { |
d13b5f5a | 63 | _cleanup_(prioq_freep) Prioq *q = NULL; |
e57ac1b0 | 64 | _cleanup_set_free_ Set *s = NULL; |
30bdd695 | 65 | unsigned previous = 0, i; |
d13b5f5a | 66 | struct test *t; |
30bdd695 LP |
67 | |
68 | srand(0); | |
69 | ||
7a08d314 | 70 | assert_se(q = prioq_new((compare_func_t) test_compare)); |
d13b5f5a | 71 | assert_se(s = set_new(&test_hash_ops)); |
30bdd695 | 72 | |
5152b845 IK |
73 | ASSERT_NULL(prioq_peek(q)); |
74 | ASSERT_NULL(prioq_peek_by_index(q, 0)); | |
75 | ASSERT_NULL(prioq_peek_by_index(q, 1)); | |
76 | ASSERT_NULL(prioq_peek_by_index(q, UINT_MAX)); | |
ef21b3b5 | 77 | |
30bdd695 | 78 | for (i = 0; i < SET_SIZE; i++) { |
d13b5f5a | 79 | assert_se(t = new0(struct test, 1)); |
30bdd695 LP |
80 | t->value = (unsigned) rand(); |
81 | ||
d13b5f5a | 82 | assert_se(prioq_put(q, t, &t->idx) >= 0); |
30bdd695 | 83 | |
d13b5f5a YW |
84 | if (i % 4 == 0) |
85 | assert_se(set_consume(s, t) >= 0); | |
30bdd695 LP |
86 | } |
87 | ||
ef21b3b5 ZJS |
88 | for (i = 0; i < SET_SIZE; i++) |
89 | assert_se(prioq_peek_by_index(q, i)); | |
5152b845 | 90 | ASSERT_NULL(prioq_peek_by_index(q, SET_SIZE)); |
ef21b3b5 ZJS |
91 | |
92 | unsigned count = 0; | |
93 | PRIOQ_FOREACH_ITEM(q, t) { | |
94 | assert_se(t); | |
95 | count++; | |
96 | } | |
97 | assert_se(count == SET_SIZE); | |
98 | ||
d13b5f5a YW |
99 | while ((t = set_steal_first(s))) { |
100 | assert_se(prioq_remove(q, t, &t->idx) == 1); | |
101 | assert_se(prioq_remove(q, t, &t->idx) == 0); | |
cd86deef | 102 | assert_se(prioq_remove(q, t, NULL) == 0); |
30bdd695 LP |
103 | |
104 | free(t); | |
105 | } | |
106 | ||
107 | for (i = 0; i < SET_SIZE * 3 / 4; i++) { | |
30bdd695 LP |
108 | assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i); |
109 | ||
d13b5f5a | 110 | assert_se(t = prioq_pop(q)); |
cd86deef YW |
111 | assert_se(prioq_remove(q, t, &t->idx) == 0); |
112 | assert_se(prioq_remove(q, t, NULL) == 0); | |
30bdd695 | 113 | assert_se(previous <= t->value); |
d13b5f5a | 114 | |
30bdd695 LP |
115 | previous = t->value; |
116 | free(t); | |
117 | } | |
118 | ||
119 | assert_se(prioq_isempty(q)); | |
30bdd695 | 120 | assert_se(set_isempty(s)); |
30bdd695 LP |
121 | } |
122 | ||
4f7452a8 | 123 | DEFINE_TEST_MAIN(LOG_INFO); |