lib/bitset_stats.c

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