]>
Commit | Line | Data |
---|---|---|
53e1b683 | 1 | /* SPDX-License-Identifier: LGPL-2.1+ */ |
30bdd695 LP |
2 | /*** |
3 | This file is part of systemd. | |
4 | ||
5 | Copyright 2013 Lennart Poettering | |
6 | ||
7 | systemd is free software; you can redistribute it and/or modify it | |
8 | under the terms of the GNU Lesser General Public License as published by | |
9 | the Free Software Foundation; either version 2.1 of the License, or | |
10 | (at your option) any later version. | |
11 | ||
12 | systemd is distributed in the hope that it will be useful, but | |
13 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
14 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
15 | Lesser General Public License for more details. | |
16 | ||
17 | You should have received a copy of the GNU Lesser General Public License | |
18 | along with systemd; If not, see <http://www.gnu.org/licenses/>. | |
19 | ***/ | |
20 | ||
21 | #include <stdlib.h> | |
22 | ||
b5efdb8a | 23 | #include "alloc-util.h" |
30bdd695 | 24 | #include "prioq.h" |
b5efdb8a | 25 | #include "set.h" |
9bf3b535 | 26 | #include "siphash24.h" |
b5efdb8a | 27 | #include "util.h" |
30bdd695 LP |
28 | |
29 | #define SET_SIZE 1024*4 | |
30 | ||
31 | static int unsigned_compare(const void *a, const void *b) { | |
32 | const unsigned *x = a, *y = b; | |
33 | ||
34 | if (*x < *y) | |
35 | return -1; | |
36 | ||
37 | if (*x > *y) | |
38 | return 1; | |
39 | ||
40 | return 0; | |
41 | } | |
42 | ||
43 | static void test_unsigned(void) { | |
44 | unsigned buffer[SET_SIZE], i; | |
45 | Prioq *q; | |
46 | ||
47 | srand(0); | |
48 | ||
49 | q = prioq_new(trivial_compare_func); | |
50 | assert_se(q); | |
51 | ||
52 | for (i = 0; i < ELEMENTSOF(buffer); i++) { | |
53 | unsigned u; | |
54 | ||
55 | u = (unsigned) rand(); | |
56 | buffer[i] = u; | |
57 | assert_se(prioq_put(q, UINT_TO_PTR(u), NULL) >= 0); | |
58 | } | |
59 | ||
60 | qsort(buffer, ELEMENTSOF(buffer), sizeof(buffer[0]), unsigned_compare); | |
61 | ||
62 | for (i = 0; i < ELEMENTSOF(buffer); i++) { | |
63 | unsigned u; | |
64 | ||
65 | assert_se(prioq_size(q) == ELEMENTSOF(buffer) - i); | |
66 | ||
67 | u = PTR_TO_UINT(prioq_pop(q)); | |
68 | assert_se(buffer[i] == u); | |
69 | } | |
70 | ||
71 | assert_se(prioq_isempty(q)); | |
72 | prioq_free(q); | |
73 | } | |
74 | ||
75 | struct test { | |
76 | unsigned value; | |
77 | unsigned idx; | |
78 | }; | |
79 | ||
80 | static int test_compare(const void *a, const void *b) { | |
81 | const struct test *x = a, *y = b; | |
82 | ||
83 | if (x->value < y->value) | |
84 | return -1; | |
85 | ||
86 | if (x->value > y->value) | |
87 | return 1; | |
88 | ||
89 | return 0; | |
90 | } | |
91 | ||
b826ab58 | 92 | static void test_hash(const void *a, struct siphash *state) { |
30bdd695 LP |
93 | const struct test *x = a; |
94 | ||
b826ab58 | 95 | siphash24_compress(&x->value, sizeof(x->value), state); |
30bdd695 LP |
96 | } |
97 | ||
d5099efc MS |
98 | static const struct hash_ops test_hash_ops = { |
99 | .hash = test_hash, | |
100 | .compare = test_compare | |
101 | }; | |
102 | ||
30bdd695 LP |
103 | static void test_struct(void) { |
104 | Prioq *q; | |
105 | Set *s; | |
106 | unsigned previous = 0, i; | |
107 | int r; | |
108 | ||
109 | srand(0); | |
110 | ||
111 | q = prioq_new(test_compare); | |
112 | assert_se(q); | |
113 | ||
d5099efc | 114 | s = set_new(&test_hash_ops); |
30bdd695 LP |
115 | assert_se(s); |
116 | ||
117 | for (i = 0; i < SET_SIZE; i++) { | |
118 | struct test *t; | |
119 | ||
120 | t = new0(struct test, 1); | |
121 | assert_se(t); | |
122 | t->value = (unsigned) rand(); | |
123 | ||
124 | r = prioq_put(q, t, &t->idx); | |
125 | assert_se(r >= 0); | |
126 | ||
127 | if (i % 4 == 0) { | |
ef42202a | 128 | r = set_consume(s, t); |
30bdd695 LP |
129 | assert_se(r >= 0); |
130 | } | |
131 | } | |
132 | ||
133 | for (;;) { | |
134 | struct test *t; | |
135 | ||
136 | t = set_steal_first(s); | |
137 | if (!t) | |
138 | break; | |
139 | ||
140 | r = prioq_remove(q, t, &t->idx); | |
141 | assert_se(r > 0); | |
142 | ||
143 | free(t); | |
144 | } | |
145 | ||
146 | for (i = 0; i < SET_SIZE * 3 / 4; i++) { | |
147 | struct test *t; | |
148 | ||
149 | assert_se(prioq_size(q) == (SET_SIZE * 3 / 4) - i); | |
150 | ||
151 | t = prioq_pop(q); | |
152 | assert_se(t); | |
153 | ||
154 | assert_se(previous <= t->value); | |
155 | previous = t->value; | |
156 | free(t); | |
157 | } | |
158 | ||
159 | assert_se(prioq_isempty(q)); | |
160 | prioq_free(q); | |
161 | ||
162 | assert_se(set_isempty(s)); | |
163 | set_free(s); | |
164 | } | |
165 | ||
166 | int main(int argc, char* argv[]) { | |
167 | ||
168 | test_unsigned(); | |
169 | test_struct(); | |
170 | ||
171 | return 0; | |
172 | } |