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