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