This source file includes following definitions.
- assert_bitset_equal
- bitset_random
- compare
- check_zero
- check_one_bit
- check_ones
- check_attributes
- main
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 #include <config.h>
18
19 #include "bitset.h"
20
21 #include "macros.h"
22
23 #define RANDOM(n) (rand () % (n))
24
25 static void
26 assert_bitset_equal (bitset bs1, bitset bs2)
27 {
28 debug_bitset (bs1);
29 debug_bitset (bs2);
30 ASSERT (bitset_size (bs1) == bitset_size (bs2));
31 for (bitset_bindex i = 0; i < bitset_size (bs1); ++i)
32 ASSERT (bitset_test (bs1, i) == bitset_test (bs2, i));
33 }
34
35 static void
36 bitset_random (bitset bs)
37 {
38 for (bitset_bindex i = 0; i < bitset_size (bs); ++i)
39 bitset_set (bs, RANDOM (2));
40 }
41
42
43
44
45
46 static void
47 compare (enum bitset_attr a, enum bitset_attr b)
48 {
49
50
51 const int nbits = RANDOM (2 * BITSET_LIST_SIZE);
52
53
54 const bitset asrc0 = bitset_create (nbits, a);
55 bitset_random (asrc0);
56 const bitset asrc1 = bitset_create (nbits, a);
57 bitset_random (asrc1);
58 const bitset asrc2 = bitset_create (nbits, a);
59 bitset_random (asrc2);
60 const bitset asrc3 = bitset_create (nbits, a);
61 bitset_random (asrc3);
62
63
64 const bitset bsrc0 = bitset_create (nbits, b);
65 bitset_copy (bsrc0, asrc0);
66 const bitset bsrc1 = bitset_create (nbits, b);
67 bitset_copy (bsrc1, asrc1);
68 const bitset bsrc2 = bitset_create (nbits, b);
69 bitset_copy (bsrc2, asrc2);
70 const bitset bsrc3 = bitset_create (nbits, b);
71 bitset_copy (bsrc3, asrc3);
72
73
74 bitset adst = bitset_create (nbits, a);
75 bitset bdst = bitset_create (nbits, b);
76
77
78 ASSERT (bitset_count (asrc0) == bitset_count (bsrc0));
79
80
81 bitset_not (adst, asrc0);
82 bitset_not (bdst, bsrc0);
83 assert_bitset_equal (adst, bdst);
84
85
86 bitset_and (adst, asrc0, asrc1);
87 bitset_and (bdst, bsrc0, bsrc1);
88 assert_bitset_equal (adst, bdst);
89 ASSERT (bitset_and_cmp (adst, asrc0, asrc1)
90 == bitset_and_cmp (bdst, bsrc0, bsrc1));
91 assert_bitset_equal (adst, bdst);
92
93
94 bitset_andn (adst, asrc0, asrc1);
95 bitset_andn (bdst, bsrc0, bsrc1);
96 assert_bitset_equal (adst, bdst);
97 ASSERT (bitset_andn_cmp (adst, asrc0, asrc1)
98 == bitset_andn_cmp (bdst, bsrc0, bsrc1));
99 assert_bitset_equal (adst, bdst);
100
101
102 bitset_or (adst, asrc0, asrc1);
103 bitset_or (bdst, bsrc0, bsrc1);
104 assert_bitset_equal (adst, bdst);
105 ASSERT (bitset_or_cmp (adst, asrc0, asrc1)
106 == bitset_or_cmp (bdst, bsrc0, bsrc1));
107 assert_bitset_equal (adst, bdst);
108
109
110 bitset_xor (adst, asrc0, asrc1);
111 bitset_xor (bdst, bsrc0, bsrc1);
112 assert_bitset_equal (adst, bdst);
113 ASSERT (bitset_xor_cmp (adst, asrc0, asrc1)
114 == bitset_xor_cmp (bdst, bsrc0, bsrc1));
115 assert_bitset_equal (adst, bdst);
116
117
118 bitset_and_or (adst, asrc0, asrc1, asrc2);
119 bitset_and_or (bdst, bsrc0, bsrc1, bsrc2);
120 assert_bitset_equal (adst, bdst);
121 ASSERT (bitset_and_or_cmp (adst, asrc0, asrc1, asrc2)
122 == bitset_and_or_cmp (bdst, bsrc0, bsrc1, bsrc2));
123 assert_bitset_equal (adst, bdst);
124
125
126 bitset_andn_or (adst, asrc0, asrc1, asrc2);
127 bitset_andn_or (bdst, bsrc0, bsrc1, bsrc2);
128 assert_bitset_equal (adst, bdst);
129 ASSERT (bitset_andn_or_cmp (adst, asrc0, asrc1, asrc2)
130 == bitset_andn_or_cmp (bdst, bsrc0, bsrc1, bsrc2));
131 assert_bitset_equal (adst, bdst);
132
133
134 bitset_or_and (adst, asrc0, asrc1, asrc2);
135 bitset_or_and (bdst, bsrc0, bsrc1, bsrc2);
136 assert_bitset_equal (adst, bdst);
137 ASSERT (bitset_or_and_cmp (adst, asrc0, asrc1, asrc2)
138 == bitset_or_and_cmp (bdst, bsrc0, bsrc1, bsrc2));
139 assert_bitset_equal (adst, bdst);
140
141
142 bitset_ones (adst);
143 bitset_ones (bdst);
144 assert_bitset_equal (adst, bdst);
145
146
147 bitset_zero (adst);
148 bitset_zero (bdst);
149 assert_bitset_equal (adst, bdst);
150
151
152
153
154 bitset_copy (bdst, bsrc0);
155 debug_bitset (bdst);
156 debug_bitset (bsrc0);
157 bitset_copy (adst, bdst);
158
159
160 ASSERT (bitset_count (adst) == bitset_count (bdst));
161
162
163 {
164 bitset_bindex first = bitset_first (adst);
165 ASSERT (first == bitset_first (bdst));
166
167 bitset_bindex last = bitset_last (adst);
168 ASSERT (last == bitset_last (bdst));
169
170 ASSERT (first <= last);
171 }
172
173
174
175 {
176 bitset_iterator iter;
177 bitset_bindex j;
178 bitset_bindex first = bitset_first (bdst);
179 bitset_bindex last = bitset_last (bdst);
180 bool seen_first = false;
181 bool seen_last = false;
182 BITSET_FOR_EACH (iter, bdst, j, 0)
183 {
184 ASSERT (first <= j && j <= last);
185 ASSERT (bitset_test (bdst, j));
186 if (j == first)
187 seen_first = true;
188 if (j == last)
189 seen_last = true;
190 }
191 if (first == BITSET_BINDEX_MAX)
192 {
193 ASSERT (!seen_first);
194 ASSERT (!seen_last);
195 }
196 else
197 {
198 ASSERT (seen_first);
199 ASSERT (seen_last);
200 }
201 }
202
203
204 {
205 bitset_iterator iter;
206 bitset_bindex j;
207 bitset_bindex first = bitset_first (bdst);
208 bitset_bindex last = bitset_last (bdst);
209 bool seen_first = false;
210 bool seen_last = false;
211 BITSET_FOR_EACH_REVERSE (iter, bdst, j, 0)
212 {
213 ASSERT (first <= j && j <= last);
214 ASSERT (bitset_test (bdst, j));
215 if (j == first)
216 seen_first = true;
217 if (j == last)
218 seen_last = true;
219 }
220 if (first == BITSET_BINDEX_MAX)
221 {
222 ASSERT (!seen_first);
223 ASSERT (!seen_last);
224 }
225 else
226 {
227 ASSERT (seen_first);
228 ASSERT (seen_last);
229 }
230 }
231
232
233
234
235
236 if (bitset_type_get (bsrc0) != BITSET_ARRAY)
237 {
238 const int nbits_new = RANDOM (256);
239 bitset_copy (adst, asrc0);
240 bitset_copy (bdst, bsrc0);
241 ASSERT (nbits_new == bitset_resize (adst, nbits_new));
242 ASSERT (nbits_new == bitset_resize (bdst, nbits_new));
243 assert_bitset_equal (adst, bdst);
244 }
245
246 bitset_free (bdst);
247 bitset_free (bsrc3);
248 bitset_free (bsrc2);
249 bitset_free (bsrc1);
250 bitset_free (bsrc0);
251 bitset_free (adst);
252 bitset_free (asrc3);
253 bitset_free (asrc2);
254 bitset_free (asrc1);
255 bitset_free (asrc0);
256 }
257
258
259
260
261 static void
262 check_zero (bitset bs)
263 {
264 fprintf (stderr, "check_zero\n");
265 bitset_zero (bs);
266
267
268 ASSERT (bitset_count (bs) == 0);
269
270
271 ASSERT (bitset_first (bs) == BITSET_BINDEX_MAX);
272 ASSERT (bitset_last (bs) == BITSET_BINDEX_MAX);
273
274
275 {
276 bitset_iterator iter;
277 bitset_bindex i;
278 BITSET_FOR_EACH (iter, bs, i, 0)
279 ASSERT (0);
280 BITSET_FOR_EACH_REVERSE (iter, bs, i, 0)
281 ASSERT (0);
282 }
283 }
284
285
286
287
288 static void
289 check_one_bit (bitset bs, int bitno)
290 {
291 fprintf (stderr, "check_one_bit(%d)\n", bitno);
292 bitset_zero (bs);
293 bitset_set (bs, bitno);
294
295
296 ASSERT (bitset_count (bs) == 1);
297
298
299 ASSERT (bitset_test (bs, bitno));
300
301
302 ASSERT (bitset_first (bs) == bitno);
303 ASSERT (bitset_last (bs) == bitno);
304
305
306 {
307 bitset_iterator iter;
308 bitset_bindex i;
309 BITSET_FOR_EACH (iter, bs, i, 0)
310 ASSERT (i == bitno);
311
312 BITSET_FOR_EACH_REVERSE (iter, bs, i, 0)
313 ASSERT (i == bitno);
314 }
315 }
316
317
318
319 static void
320 check_ones (bitset bs)
321 {
322 fprintf (stderr, "check_ones\n");
323 const bitset_bindex size = bitset_size (bs);
324
325 bitset_ones (bs);
326 debug_bitset (bs);
327
328
329 ASSERT (bitset_count (bs) == size);
330
331
332 ASSERT (bitset_first (bs) == 0);
333 ASSERT (bitset_last (bs) == size - 1);
334
335
336 {
337 bitset_iterator iter;
338 bitset_bindex i;
339 bitset_bindex count = 0;
340 BITSET_FOR_EACH (iter, bs, i, 0)
341 ASSERT (i == count++);
342 ASSERT (count == size);
343 BITSET_FOR_EACH_REVERSE (iter, bs, i, 0)
344 ASSERT (i == --count);
345 ASSERT (count == 0);
346 }
347 }
348
349
350
351
352 static void
353 check_attributes (enum bitset_attr attr, int nbits)
354 {
355 bitset bs0 = bitset_create (nbits, attr);
356 ASSERT (bitset_size (bs0) == nbits);
357 ASSERT (bitset_count (bs0) == 0);
358 ASSERT (bitset_empty_p (bs0));
359
360 bitset bs1 = bitset_create (nbits, attr);
361 bitset_set (bs1, 1);
362 bitset_set (bs1, 3);
363 bitset_set (bs1, 5);
364 ASSERT (bitset_count (bs1) == 3);
365 ASSERT (!bitset_empty_p (bs1));
366
367 bitset bs2 = bitset_create (nbits, attr);
368 bitset_set (bs2, 0);
369 bitset_set (bs2, 2);
370 bitset_set (bs2, 4);
371
372
373 ASSERT (bitset_disjoint_p (bs1, bs2));
374
375
376 bitset bs = bitset_create (nbits, attr);
377 bitset_and (bs, bs1, bs2);
378 ASSERT (bitset_count (bs) == 0);
379
380
381 bitset_or (bs, bs1, bs2);
382 ASSERT (bitset_count (bs) == 6);
383
384 check_zero (bs);
385 check_ones (bs);
386
387
388
389 for (int bitno = 0; bitno < nbits; ++bitno)
390 check_one_bit (bs, bitno);
391
392 bitset_free (bs);
393 bitset_free (bs2);
394 bitset_free (bs1);
395 bitset_free (bs0);
396 }
397
398 int main (void)
399 {
400 bitset_stats_enable ();
401
402 for (int i = 0; i < 4; ++i)
403 {
404
405
406
407 int nbits =
408 i == 0 ? 1
409 : i == 1 ? 32
410 : i == 2 ? 257
411 : (BITSET_LIST_SIZE + 1);
412 check_attributes (BITSET_FIXED, nbits);
413 check_attributes (BITSET_VARIABLE, nbits);
414 check_attributes (BITSET_DENSE, nbits);
415 check_attributes (BITSET_SPARSE, nbits);
416 check_attributes (BITSET_FRUGAL, nbits);
417 check_attributes (BITSET_GREEDY, nbits);
418 }
419
420 compare (BITSET_VARIABLE, BITSET_FIXED);
421 compare (BITSET_VARIABLE, BITSET_VARIABLE);
422 compare (BITSET_VARIABLE, BITSET_DENSE);
423 compare (BITSET_VARIABLE, BITSET_SPARSE);
424 compare (BITSET_VARIABLE, BITSET_FRUGAL);
425 compare (BITSET_VARIABLE, BITSET_GREEDY);
426
427 bitset_stats_dump (stderr);
428 return 0;
429 }