Commit | Line | Data |
---|---|---|
613f5e1a | 1 | /* Bitset statistics. |
68cae94e | 2 | Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. |
613f5e1a AD |
3 | Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). |
4 | ||
f16b0819 | 5 | This program is free software: you can redistribute it and/or modify |
613f5e1a | 6 | it under the terms of the GNU General Public License as published by |
f16b0819 | 7 | the Free Software Foundation, either version 3 of the License, or |
613f5e1a AD |
8 | (at your option) any later version. |
9 | ||
10 | This program is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
13 | GNU General Public License for more details. | |
14 | ||
15 | You should have received a copy of the GNU General Public License | |
f16b0819 | 16 | along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
613f5e1a AD |
17 | |
18 | /* This file is a wrapper bitset implementation for the other bitset | |
19 | implementations. It provides bitset compatibility checking and | |
20 | statistics gathering without having to instrument the bitset | |
21 | implementations. When statistics gathering is enabled, the bitset | |
22 | operations get vectored through here and we then call the appropriate | |
02650b7f | 23 | routines. */ |
613f5e1a | 24 | |
231ed89a PE |
25 | #include <config.h> |
26 | ||
27 | #include "bitset_stats.h" | |
613f5e1a AD |
28 | |
29 | #include "bbitset.h" | |
30 | #include "abitset.h" | |
31 | #include "ebitset.h" | |
32 | #include "lbitset.h" | |
eaef5507 | 33 | #include "vbitset.h" |
613f5e1a AD |
34 | #include <stdlib.h> |
35 | #include <string.h> | |
36 | #include <stdio.h> | |
37 | ||
c131cbff PE |
38 | #include "gettext.h" |
39 | #define _(Msgid) gettext (Msgid) | |
613f5e1a AD |
40 | |
41 | /* Configuration macros. */ | |
42 | #define BITSET_STATS_FILE "bitset.dat" | |
43 | #define BITSET_LOG_COUNT_BINS 10 | |
44 | #define BITSET_LOG_SIZE_BINS 16 | |
45 | #define BITSET_DENSITY_BINS 20 | |
46 | ||
47 | ||
48 | /* Accessor macros. */ | |
04098407 | 49 | #define BITSET_STATS_ALLOCS_INC(TYPE) \ |
613f5e1a | 50 | bitset_stats_info->types[(TYPE)].allocs++ |
04098407 | 51 | #define BITSET_STATS_FREES_INC(BSET) \ |
613f5e1a | 52 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++ |
04098407 | 53 | #define BITSET_STATS_SETS_INC(BSET) \ |
613f5e1a | 54 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++ |
04098407 | 55 | #define BITSET_STATS_CACHE_SETS_INC(BSET) \ |
613f5e1a | 56 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++ |
04098407 | 57 | #define BITSET_STATS_RESETS_INC(BSET) \ |
613f5e1a | 58 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++ |
04098407 | 59 | #define BITSET_STATS_CACHE_RESETS_INC(BSET) \ |
613f5e1a | 60 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++ |
04098407 | 61 | #define BITSET_STATS_TESTS_INC(BSET) \ |
613f5e1a | 62 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++ |
04098407 | 63 | #define BITSET_STATS_CACHE_TESTS_INC(BSET) \ |
613f5e1a | 64 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++ |
04098407 | 65 | #define BITSET_STATS_LISTS_INC(BSET) \ |
613f5e1a | 66 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++ |
04098407 | 67 | #define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \ |
613f5e1a | 68 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++ |
04098407 | 69 | #define BITSET_STATS_LIST_SIZES_INC(BSET, I) \ |
613f5e1a | 70 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++ |
04098407 | 71 | #define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \ |
613f5e1a AD |
72 | bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++ |
73 | ||
74 | ||
613f5e1a AD |
75 | struct bitset_type_info_struct |
76 | { | |
77 | unsigned int allocs; | |
78 | unsigned int frees; | |
79 | unsigned int lists; | |
80 | unsigned int sets; | |
81 | unsigned int cache_sets; | |
82 | unsigned int resets; | |
83 | unsigned int cache_resets; | |
84 | unsigned int tests; | |
85 | unsigned int cache_tests; | |
86 | unsigned int list_counts[BITSET_LOG_COUNT_BINS]; | |
87 | unsigned int list_sizes[BITSET_LOG_SIZE_BINS]; | |
88 | unsigned int list_density[BITSET_DENSITY_BINS]; | |
89 | }; | |
90 | ||
91 | struct bitset_stats_info_struct | |
92 | { | |
93 | unsigned int runs; | |
94 | struct bitset_type_info_struct types[BITSET_TYPE_NUM]; | |
95 | }; | |
96 | ||
97 | ||
98 | struct bitset_stats_info_struct bitset_stats_info_data; | |
99 | struct bitset_stats_info_struct *bitset_stats_info; | |
d0829076 | 100 | bool bitset_stats_enabled = false; |
613f5e1a AD |
101 | |
102 | ||
613f5e1a AD |
103 | /* Print a percentage histogram with message MSG to FILE. */ |
104 | static void | |
d65ec44e PE |
105 | bitset_percent_histogram_print (FILE *file, const char *name, const char *msg, |
106 | unsigned int n_bins, unsigned int *bins) | |
613f5e1a AD |
107 | { |
108 | unsigned int i; | |
109 | unsigned int total; | |
110 | ||
111 | total = 0; | |
112 | for (i = 0; i < n_bins; i++) | |
113 | total += bins[i]; | |
114 | ||
115 | if (!total) | |
116 | return; | |
117 | ||
118 | fprintf (file, "%s %s", name, msg); | |
119 | for (i = 0; i < n_bins; i++) | |
2d382ea8 | 120 | fprintf (file, "%.0f-%.0f%%\t%8u (%5.1f%%)\n", |
613f5e1a AD |
121 | i * 100.0 / n_bins, |
122 | (i + 1) * 100.0 / n_bins, bins[i], | |
123 | (100.0 * bins[i]) / total); | |
124 | } | |
125 | ||
126 | ||
127 | /* Print a log histogram with message MSG to FILE. */ | |
128 | static void | |
d65ec44e PE |
129 | bitset_log_histogram_print (FILE *file, const char *name, const char *msg, |
130 | unsigned int n_bins, unsigned int *bins) | |
613f5e1a AD |
131 | { |
132 | unsigned int i; | |
133 | unsigned int total; | |
134 | unsigned int max_width; | |
613f5e1a AD |
135 | |
136 | total = 0; | |
137 | for (i = 0; i < n_bins; i++) | |
138 | total += bins[i]; | |
139 | ||
140 | if (!total) | |
141 | return; | |
142 | ||
6aa452a6 | 143 | /* Determine number of useful bins. */ |
613f5e1a AD |
144 | for (i = n_bins; i > 3 && ! bins[i - 1]; i--) |
145 | continue; | |
6aa452a6 | 146 | n_bins = i; |
613f5e1a AD |
147 | |
148 | /* 2 * ceil (log10 (2) * (N - 1)) + 1. */ | |
149 | max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1; | |
150 | ||
151 | fprintf (file, "%s %s", name, msg); | |
152 | for (i = 0; i < 2; i++) | |
2d382ea8 | 153 | fprintf (file, "%*d\t%8u (%5.1f%%)\n", |
613f5e1a AD |
154 | max_width, i, bins[i], 100.0 * bins[i] / total); |
155 | ||
6aa452a6 | 156 | for (; i < n_bins; i++) |
2d382ea8 | 157 | fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n", |
613f5e1a | 158 | max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1), |
779e7ceb PE |
159 | 1UL << (i - 1), |
160 | (1UL << i) - 1, | |
2d382ea8 | 161 | bins[i], |
613f5e1a AD |
162 | (100.0 * bins[i]) / total); |
163 | } | |
164 | ||
165 | ||
166 | /* Print bitset statistics to FILE. */ | |
167 | static void | |
d65ec44e PE |
168 | bitset_stats_print_1 (FILE *file, const char *name, |
169 | struct bitset_type_info_struct *stats) | |
613f5e1a AD |
170 | { |
171 | if (!stats) | |
172 | return; | |
d65ec44e | 173 | |
613f5e1a | 174 | fprintf (file, "%s:\n", name); |
2d382ea8 | 175 | fprintf (file, _("%u bitset_allocs, %u freed (%.2f%%).\n"), |
613f5e1a AD |
176 | stats->allocs, stats->frees, |
177 | stats->allocs ? 100.0 * stats->frees / stats->allocs : 0); | |
2d382ea8 | 178 | fprintf (file, _("%u bitset_sets, %u cached (%.2f%%)\n"), |
613f5e1a AD |
179 | stats->sets, stats->cache_sets, |
180 | stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0); | |
2d382ea8 | 181 | fprintf (file, _("%u bitset_resets, %u cached (%.2f%%)\n"), |
613f5e1a AD |
182 | stats->resets, stats->cache_resets, |
183 | stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0); | |
2d382ea8 | 184 | fprintf (file, _("%u bitset_tests, %u cached (%.2f%%)\n"), |
613f5e1a AD |
185 | stats->tests, stats->cache_tests, |
186 | stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0); | |
187 | ||
2d382ea8 | 188 | fprintf (file, _("%u bitset_lists\n"), stats->lists); |
613f5e1a | 189 | |
c131cbff | 190 | bitset_log_histogram_print (file, name, _("count log histogram\n"), |
613f5e1a AD |
191 | BITSET_LOG_COUNT_BINS, stats->list_counts); |
192 | ||
c131cbff | 193 | bitset_log_histogram_print (file, name, _("size log histogram\n"), |
613f5e1a AD |
194 | BITSET_LOG_SIZE_BINS, stats->list_sizes); |
195 | ||
c131cbff | 196 | bitset_percent_histogram_print (file, name, _("density histogram\n"), |
613f5e1a AD |
197 | BITSET_DENSITY_BINS, stats->list_density); |
198 | } | |
199 | ||
200 | ||
201 | /* Print all bitset statistics to FILE. */ | |
202 | static void | |
d0829076 | 203 | bitset_stats_print (FILE *file, bool verbose ATTRIBUTE_UNUSED) |
613f5e1a AD |
204 | { |
205 | int i; | |
613f5e1a AD |
206 | |
207 | if (!bitset_stats_info) | |
208 | return; | |
209 | ||
c131cbff | 210 | fprintf (file, _("Bitset statistics:\n\n")); |
613f5e1a AD |
211 | |
212 | if (bitset_stats_info->runs > 1) | |
2d382ea8 | 213 | fprintf (file, _("Accumulated runs = %u\n"), bitset_stats_info->runs); |
613f5e1a AD |
214 | |
215 | for (i = 0; i < BITSET_TYPE_NUM; i++) | |
d65ec44e | 216 | bitset_stats_print_1 (file, bitset_type_names[i], |
6aa452a6 | 217 | &bitset_stats_info->types[i]); |
613f5e1a AD |
218 | } |
219 | ||
220 | ||
221 | /* Initialise bitset statistics logging. */ | |
222 | void | |
d65ec44e | 223 | bitset_stats_enable (void) |
613f5e1a AD |
224 | { |
225 | if (!bitset_stats_info) | |
226 | bitset_stats_info = &bitset_stats_info_data; | |
d0829076 | 227 | bitset_stats_enabled = true; |
613f5e1a AD |
228 | } |
229 | ||
230 | ||
231 | void | |
d65ec44e | 232 | bitset_stats_disable (void) |
613f5e1a | 233 | { |
d0829076 | 234 | bitset_stats_enabled = false; |
613f5e1a AD |
235 | } |
236 | ||
237 | ||
238 | /* Read bitset statistics file. */ | |
239 | void | |
48b16bbc | 240 | bitset_stats_read (const char *file_name) |
613f5e1a AD |
241 | { |
242 | FILE *file; | |
243 | ||
244 | if (!bitset_stats_info) | |
245 | return; | |
d65ec44e | 246 | |
48b16bbc PE |
247 | if (!file_name) |
248 | file_name = BITSET_STATS_FILE; | |
613f5e1a | 249 | |
48b16bbc | 250 | file = fopen (file_name, "r"); |
613f5e1a AD |
251 | if (file) |
252 | { | |
253 | if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data), | |
254 | 1, file) != 1) | |
255 | { | |
256 | if (ferror (file)) | |
c131cbff | 257 | perror (_("Could not read stats file.")); |
613f5e1a | 258 | else |
c131cbff | 259 | fprintf (stderr, _("Bad stats file size.\n")); |
613f5e1a | 260 | } |
11a71262 PE |
261 | if (fclose (file) != 0) |
262 | perror (_("Could not read stats file.")); | |
613f5e1a AD |
263 | } |
264 | bitset_stats_info_data.runs++; | |
265 | } | |
266 | ||
267 | ||
268 | /* Write bitset statistics file. */ | |
269 | void | |
48b16bbc | 270 | bitset_stats_write (const char *file_name) |
613f5e1a AD |
271 | { |
272 | FILE *file; | |
273 | ||
274 | if (!bitset_stats_info) | |
275 | return; | |
276 | ||
48b16bbc PE |
277 | if (!file_name) |
278 | file_name = BITSET_STATS_FILE; | |
613f5e1a | 279 | |
48b16bbc | 280 | file = fopen (file_name, "w"); |
613f5e1a AD |
281 | if (file) |
282 | { | |
283 | if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data), | |
284 | 1, file) != 1) | |
c131cbff | 285 | perror (_("Could not write stats file.")); |
11a71262 PE |
286 | if (fclose (file) != 0) |
287 | perror (_("Could not write stats file.")); | |
613f5e1a AD |
288 | } |
289 | else | |
c131cbff | 290 | perror (_("Could not open stats file for writing.")); |
613f5e1a AD |
291 | } |
292 | ||
293 | ||
294 | /* Dump bitset statistics to FILE. */ | |
295 | void | |
d65ec44e | 296 | bitset_stats_dump (FILE *file) |
613f5e1a | 297 | { |
d0829076 | 298 | bitset_stats_print (file, false); |
613f5e1a AD |
299 | } |
300 | ||
301 | ||
302 | /* Function to be called from debugger to print bitset stats. */ | |
303 | void | |
304 | debug_bitset_stats (void) | |
305 | { | |
d0829076 | 306 | bitset_stats_print (stderr, true); |
613f5e1a AD |
307 | } |
308 | ||
309 | ||
310 | static void | |
d65ec44e | 311 | bitset_stats_set (bitset dst, bitset_bindex bitno) |
613f5e1a AD |
312 | { |
313 | bitset bset = dst->s.bset; | |
c131cbff PE |
314 | bitset_windex wordno = bitno / BITSET_WORD_BITS; |
315 | bitset_windex offset = wordno - bset->b.cindex; | |
d65ec44e | 316 | |
613f5e1a AD |
317 | BITSET_STATS_SETS_INC (bset); |
318 | ||
319 | if (offset < bset->b.csize) | |
320 | { | |
c131cbff | 321 | bset->b.cdata[offset] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS); |
613f5e1a AD |
322 | BITSET_STATS_CACHE_SETS_INC (bset); |
323 | } | |
324 | else | |
325 | BITSET_SET_ (bset, bitno); | |
326 | } | |
327 | ||
328 | ||
329 | static void | |
d65ec44e | 330 | bitset_stats_reset (bitset dst, bitset_bindex bitno) |
613f5e1a AD |
331 | { |
332 | bitset bset = dst->s.bset; | |
c131cbff PE |
333 | bitset_windex wordno = bitno / BITSET_WORD_BITS; |
334 | bitset_windex offset = wordno - bset->b.cindex; | |
d65ec44e | 335 | |
613f5e1a AD |
336 | BITSET_STATS_RESETS_INC (bset); |
337 | ||
338 | if (offset < bset->b.csize) | |
339 | { | |
c131cbff PE |
340 | bset->b.cdata[offset] &= |
341 | ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS)); | |
613f5e1a AD |
342 | BITSET_STATS_CACHE_RESETS_INC (bset); |
343 | } | |
344 | else | |
345 | BITSET_RESET_ (bset, bitno); | |
346 | } | |
347 | ||
348 | ||
d0829076 | 349 | static bool |
d65ec44e | 350 | bitset_stats_toggle (bitset src, bitset_bindex bitno) |
6aa452a6 AD |
351 | { |
352 | return BITSET_TOGGLE_ (src->s.bset, bitno); | |
353 | } | |
354 | ||
355 | ||
d0829076 | 356 | static bool |
d65ec44e | 357 | bitset_stats_test (bitset src, bitset_bindex bitno) |
613f5e1a AD |
358 | { |
359 | bitset bset = src->s.bset; | |
c131cbff PE |
360 | bitset_windex wordno = bitno / BITSET_WORD_BITS; |
361 | bitset_windex offset = wordno - bset->b.cindex; | |
613f5e1a AD |
362 | |
363 | BITSET_STATS_TESTS_INC (bset); | |
d65ec44e | 364 | |
613f5e1a AD |
365 | if (offset < bset->b.csize) |
366 | { | |
367 | BITSET_STATS_CACHE_TESTS_INC (bset); | |
368 | return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1; | |
369 | } | |
370 | else | |
371 | return BITSET_TEST_ (bset, bitno); | |
372 | } | |
373 | ||
374 | ||
eaef5507 PE |
375 | static bitset_bindex |
376 | bitset_stats_resize (bitset src, bitset_bindex size) | |
377 | { | |
378 | return BITSET_RESIZE_ (src->s.bset, size); | |
379 | } | |
380 | ||
381 | ||
2d382ea8 | 382 | static bitset_bindex |
d65ec44e | 383 | bitset_stats_size (bitset src) |
613f5e1a AD |
384 | { |
385 | return BITSET_SIZE_ (src->s.bset); | |
386 | } | |
387 | ||
388 | ||
2d382ea8 | 389 | static bitset_bindex |
d65ec44e | 390 | bitset_stats_count (bitset src) |
6aa452a6 AD |
391 | { |
392 | return BITSET_COUNT_ (src->s.bset); | |
393 | } | |
394 | ||
395 | ||
d0829076 | 396 | static bool |
d65ec44e | 397 | bitset_stats_empty_p (bitset dst) |
6aa452a6 AD |
398 | { |
399 | return BITSET_EMPTY_P_ (dst->s.bset); | |
400 | } | |
401 | ||
402 | ||
403 | static void | |
d65ec44e | 404 | bitset_stats_ones (bitset dst) |
6aa452a6 AD |
405 | { |
406 | BITSET_ONES_ (dst->s.bset); | |
407 | } | |
408 | ||
409 | ||
410 | static void | |
d65ec44e | 411 | bitset_stats_zero (bitset dst) |
6aa452a6 AD |
412 | { |
413 | BITSET_ZERO_ (dst->s.bset); | |
414 | } | |
415 | ||
416 | ||
417 | static void | |
d65ec44e | 418 | bitset_stats_copy (bitset dst, bitset src) |
6aa452a6 AD |
419 | { |
420 | BITSET_CHECK2_ (dst, src); | |
421 | BITSET_COPY_ (dst->s.bset, src->s.bset); | |
422 | } | |
423 | ||
424 | ||
d0829076 | 425 | static bool |
d65ec44e | 426 | bitset_stats_disjoint_p (bitset dst, bitset src) |
613f5e1a | 427 | { |
6aa452a6 AD |
428 | BITSET_CHECK2_ (dst, src); |
429 | return BITSET_DISJOINT_P_ (dst->s.bset, src->s.bset); | |
613f5e1a AD |
430 | } |
431 | ||
432 | ||
d0829076 | 433 | static bool |
d65ec44e | 434 | bitset_stats_equal_p (bitset dst, bitset src) |
613f5e1a AD |
435 | { |
436 | BITSET_CHECK2_ (dst, src); | |
6aa452a6 AD |
437 | return BITSET_EQUAL_P_ (dst->s.bset, src->s.bset); |
438 | } | |
439 | ||
440 | ||
441 | static void | |
d65ec44e | 442 | bitset_stats_not (bitset dst, bitset src) |
6aa452a6 AD |
443 | { |
444 | BITSET_CHECK2_ (dst, src); | |
445 | BITSET_NOT_ (dst->s.bset, src->s.bset); | |
446 | } | |
447 | ||
448 | ||
d0829076 | 449 | static bool |
d65ec44e | 450 | bitset_stats_subset_p (bitset dst, bitset src) |
6aa452a6 AD |
451 | { |
452 | BITSET_CHECK2_ (dst, src); | |
453 | return BITSET_SUBSET_P_ (dst->s.bset, src->s.bset); | |
454 | } | |
455 | ||
456 | ||
457 | static void | |
d65ec44e | 458 | bitset_stats_and (bitset dst, bitset src1, bitset src2) |
6aa452a6 AD |
459 | { |
460 | BITSET_CHECK3_ (dst, src1, src2); | |
461 | BITSET_AND_ (dst->s.bset, src1->s.bset, src2->s.bset); | |
462 | } | |
463 | ||
464 | ||
d0829076 | 465 | static bool |
d65ec44e | 466 | bitset_stats_and_cmp (bitset dst, bitset src1, bitset src2) |
6aa452a6 AD |
467 | { |
468 | BITSET_CHECK3_ (dst, src1, src2); | |
469 | return BITSET_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); | |
470 | } | |
471 | ||
472 | ||
473 | static void | |
d65ec44e | 474 | bitset_stats_andn (bitset dst, bitset src1, bitset src2) |
6aa452a6 AD |
475 | { |
476 | BITSET_CHECK3_ (dst, src1, src2); | |
477 | BITSET_ANDN_ (dst->s.bset, src1->s.bset, src2->s.bset); | |
478 | } | |
479 | ||
480 | ||
d0829076 | 481 | static bool |
d65ec44e | 482 | bitset_stats_andn_cmp (bitset dst, bitset src1, bitset src2) |
6aa452a6 AD |
483 | { |
484 | BITSET_CHECK3_ (dst, src1, src2); | |
485 | return BITSET_ANDN_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); | |
486 | } | |
487 | ||
488 | ||
489 | static void | |
d65ec44e | 490 | bitset_stats_or (bitset dst, bitset src1, bitset src2) |
6aa452a6 AD |
491 | { |
492 | BITSET_CHECK3_ (dst, src1, src2); | |
493 | BITSET_OR_ (dst->s.bset, src1->s.bset, src2->s.bset); | |
494 | } | |
495 | ||
496 | ||
d0829076 | 497 | static bool |
d65ec44e | 498 | bitset_stats_or_cmp (bitset dst, bitset src1, bitset src2) |
6aa452a6 AD |
499 | { |
500 | BITSET_CHECK3_ (dst, src1, src2); | |
501 | return BITSET_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); | |
502 | } | |
503 | ||
504 | ||
505 | static void | |
d65ec44e | 506 | bitset_stats_xor (bitset dst, bitset src1, bitset src2) |
6aa452a6 AD |
507 | { |
508 | BITSET_CHECK3_ (dst, src1, src2); | |
509 | BITSET_XOR_ (dst->s.bset, src1->s.bset, src2->s.bset); | |
613f5e1a AD |
510 | } |
511 | ||
512 | ||
d0829076 | 513 | static bool |
d65ec44e | 514 | bitset_stats_xor_cmp (bitset dst, bitset src1, bitset src2) |
613f5e1a AD |
515 | { |
516 | BITSET_CHECK3_ (dst, src1, src2); | |
6aa452a6 AD |
517 | return BITSET_XOR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset); |
518 | } | |
519 | ||
520 | ||
521 | static void | |
d65ec44e | 522 | bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 AD |
523 | { |
524 | BITSET_CHECK4_ (dst, src1, src2, src3); | |
6aa452a6 | 525 | BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); |
613f5e1a AD |
526 | } |
527 | ||
528 | ||
d0829076 | 529 | static bool |
d65ec44e | 530 | bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) |
613f5e1a AD |
531 | { |
532 | BITSET_CHECK4_ (dst, src1, src2, src3); | |
6aa452a6 AD |
533 | return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); |
534 | } | |
535 | ||
536 | ||
537 | static void | |
d65ec44e | 538 | bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 AD |
539 | { |
540 | BITSET_CHECK4_ (dst, src1, src2, src3); | |
6aa452a6 AD |
541 | BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); |
542 | } | |
543 | ||
544 | ||
d0829076 | 545 | static bool |
d65ec44e | 546 | bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 AD |
547 | { |
548 | BITSET_CHECK4_ (dst, src1, src2, src3); | |
6aa452a6 AD |
549 | return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); |
550 | } | |
551 | ||
552 | ||
553 | static void | |
d65ec44e | 554 | bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 AD |
555 | { |
556 | BITSET_CHECK4_ (dst, src1, src2, src3); | |
6aa452a6 AD |
557 | BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); |
558 | } | |
559 | ||
560 | ||
d0829076 | 561 | static bool |
d65ec44e | 562 | bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3) |
6aa452a6 AD |
563 | { |
564 | BITSET_CHECK4_ (dst, src1, src2, src3); | |
6aa452a6 | 565 | return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset); |
613f5e1a AD |
566 | } |
567 | ||
568 | ||
2d382ea8 | 569 | static bitset_bindex |
d65ec44e PE |
570 | bitset_stats_list (bitset bset, bitset_bindex *list, |
571 | bitset_bindex num, bitset_bindex *next) | |
613f5e1a AD |
572 | { |
573 | bitset_bindex count; | |
574 | bitset_bindex tmp; | |
575 | bitset_bindex size; | |
576 | bitset_bindex i; | |
eaef5507 | 577 | enum bitset_type type; |
613f5e1a AD |
578 | |
579 | count = BITSET_LIST_ (bset->s.bset, list, num, next); | |
d65ec44e | 580 | |
eaef5507 | 581 | type = BITSET_TYPE_ (bset->s.bset); |
613f5e1a | 582 | BITSET_STATS_LISTS_INC (bset->s.bset); |
d65ec44e | 583 | |
613f5e1a AD |
584 | /* Log histogram of number of set bits. */ |
585 | for (i = 0, tmp = count; tmp; tmp >>= 1, i++) | |
586 | continue; | |
587 | if (i >= BITSET_LOG_COUNT_BINS) | |
588 | i = BITSET_LOG_COUNT_BINS - 1; | |
589 | BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i); | |
d65ec44e | 590 | |
613f5e1a AD |
591 | /* Log histogram of number of bits in set. */ |
592 | size = BITSET_SIZE_ (bset->s.bset); | |
593 | for (i = 0, tmp = size; tmp; tmp >>= 1, i++) | |
594 | continue; | |
595 | if (i >= BITSET_LOG_SIZE_BINS) | |
596 | i = BITSET_LOG_SIZE_BINS - 1; | |
597 | BITSET_STATS_LIST_SIZES_INC (bset->s.bset, i); | |
d65ec44e | 598 | |
613f5e1a AD |
599 | /* Histogram of fraction of bits set. */ |
600 | i = size ? (count * BITSET_DENSITY_BINS) / size : 0; | |
601 | if (i >= BITSET_DENSITY_BINS) | |
602 | i = BITSET_DENSITY_BINS - 1; | |
603 | BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i); | |
604 | return count; | |
605 | } | |
606 | ||
607 | ||
2d382ea8 | 608 | static bitset_bindex |
d65ec44e PE |
609 | bitset_stats_list_reverse (bitset bset, bitset_bindex *list, |
610 | bitset_bindex num, bitset_bindex *next) | |
613f5e1a | 611 | { |
6aa452a6 | 612 | return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next); |
613f5e1a AD |
613 | } |
614 | ||
615 | ||
616 | static void | |
d65ec44e | 617 | bitset_stats_free (bitset bset) |
613f5e1a AD |
618 | { |
619 | BITSET_STATS_FREES_INC (bset->s.bset); | |
620 | BITSET_FREE_ (bset->s.bset); | |
621 | } | |
622 | ||
623 | ||
6aa452a6 | 624 | struct bitset_vtable bitset_stats_vtable = { |
613f5e1a AD |
625 | bitset_stats_set, |
626 | bitset_stats_reset, | |
6aa452a6 | 627 | bitset_stats_toggle, |
613f5e1a | 628 | bitset_stats_test, |
eaef5507 | 629 | bitset_stats_resize, |
613f5e1a | 630 | bitset_stats_size, |
6aa452a6 AD |
631 | bitset_stats_count, |
632 | bitset_stats_empty_p, | |
633 | bitset_stats_ones, | |
634 | bitset_stats_zero, | |
635 | bitset_stats_copy, | |
636 | bitset_stats_disjoint_p, | |
637 | bitset_stats_equal_p, | |
638 | bitset_stats_not, | |
639 | bitset_stats_subset_p, | |
640 | bitset_stats_and, | |
641 | bitset_stats_and_cmp, | |
642 | bitset_stats_andn, | |
643 | bitset_stats_andn_cmp, | |
644 | bitset_stats_or, | |
645 | bitset_stats_or_cmp, | |
646 | bitset_stats_xor, | |
647 | bitset_stats_xor_cmp, | |
648 | bitset_stats_and_or, | |
649 | bitset_stats_and_or_cmp, | |
650 | bitset_stats_andn_or, | |
651 | bitset_stats_andn_or_cmp, | |
652 | bitset_stats_or_and, | |
653 | bitset_stats_or_and_cmp, | |
613f5e1a | 654 | bitset_stats_list, |
6aa452a6 | 655 | bitset_stats_list_reverse, |
613f5e1a AD |
656 | bitset_stats_free, |
657 | BITSET_STATS | |
658 | }; | |
659 | ||
660 | ||
661 | /* Return enclosed bitset type. */ | |
662 | enum bitset_type | |
d65ec44e | 663 | bitset_stats_type_get (bitset bset) |
613f5e1a AD |
664 | { |
665 | return BITSET_TYPE_ (bset->s.bset); | |
666 | } | |
667 | ||
668 | ||
2d382ea8 PE |
669 | size_t |
670 | bitset_stats_bytes (void) | |
613f5e1a | 671 | { |
55e728eb | 672 | return sizeof (struct bitset_stats_struct); |
613f5e1a AD |
673 | } |
674 | ||
675 | ||
676 | bitset | |
d65ec44e | 677 | bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) |
613f5e1a | 678 | { |
2d382ea8 | 679 | size_t bytes; |
613f5e1a AD |
680 | bitset sbset; |
681 | ||
6aa452a6 | 682 | bset->b.vtable = &bitset_stats_vtable; |
613f5e1a AD |
683 | |
684 | /* Disable cache. */ | |
685 | bset->b.cindex = 0; | |
686 | bset->b.csize = 0; | |
687 | bset->b.cdata = 0; | |
688 | ||
eaef5507 PE |
689 | BITSET_NBITS_ (bset) = n_bits; |
690 | ||
613f5e1a AD |
691 | /* Set up the actual bitset implementation that |
692 | we are a wrapper over. */ | |
693 | switch (type) | |
694 | { | |
68cae94e PE |
695 | default: |
696 | abort (); | |
697 | ||
613f5e1a AD |
698 | case BITSET_ARRAY: |
699 | bytes = abitset_bytes (n_bits); | |
89519adf | 700 | sbset = xcalloc (1, bytes); |
613f5e1a AD |
701 | abitset_init (sbset, n_bits); |
702 | break; | |
703 | ||
704 | case BITSET_LIST: | |
705 | bytes = lbitset_bytes (n_bits); | |
89519adf | 706 | sbset = xcalloc (1, bytes); |
613f5e1a AD |
707 | lbitset_init (sbset, n_bits); |
708 | break; | |
709 | ||
710 | case BITSET_TABLE: | |
711 | bytes = ebitset_bytes (n_bits); | |
89519adf | 712 | sbset = xcalloc (1, bytes); |
613f5e1a AD |
713 | ebitset_init (sbset, n_bits); |
714 | break; | |
715 | ||
eaef5507 PE |
716 | case BITSET_VARRAY: |
717 | bytes = vbitset_bytes (n_bits); | |
89519adf | 718 | sbset = xcalloc (1, bytes); |
eaef5507 PE |
719 | vbitset_init (sbset, n_bits); |
720 | break; | |
613f5e1a AD |
721 | } |
722 | ||
723 | bset->s.bset = sbset; | |
724 | ||
725 | BITSET_STATS_ALLOCS_INC (type); | |
d65ec44e | 726 | |
613f5e1a AD |
727 | return bset; |
728 | } |