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