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