lib/bitset.c

   1 /* General bitsets.
   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 #ifdef HAVE_CONFIG_H
  20 #include "config.h"
  21 #endif
  22
  23 #include <stdlib.h>
  24 #include "bitset.h"
  25 #include "sbitset.h"
  26 #include "lbitset.h"
  27 #include "ebitset.h"
  28 #include "obstack.h"
  29
  30 static void bitset_print PARAMS ((FILE *, bitset, int));
  31
  32 #if BITSET_STATS
  33 #define BITSET_STATS_FILE "bitset.dat"
  34
  35 #define BITSET_LOG_COUNT_BINS 10
  36 #define BITSET_LOG_SIZE_BINS  16
  37 #define BITSET_DENSITY_BINS  20
  38
  39 struct bitset_type_stats_struct
  40 {
  41   unsigned int xmallocs;
  42   unsigned int xfrees;
  43   unsigned int oballocs;
  44   unsigned int obfrees;
  45   unsigned int lists;
  46   unsigned int list_counts[BITSET_LOG_COUNT_BINS];
  47   unsigned int list_sizes[BITSET_LOG_SIZE_BINS];
  48   unsigned int list_density[BITSET_DENSITY_BINS];
  49 };
  50
  51 struct bitset_stats_struct
  52 {
  53   unsigned int runs;
  54   struct bitset_type_stats_struct types[BITSET_TYPE_NUM];
  55 };
  56
  57 struct bitset_stats_struct bitset_stats_data;
  58 struct bitset_stats_struct *bitset_stats;
  59
  60 static void bitset_percent_histogram_print PARAMS ((FILE *, const char *,
  61                                                     const char *,
  62                                                     unsigned int,
  63                                                     unsigned int *));
  64 static void bitset_log_histogram_print PARAMS ((FILE *, const char *,
  65                                                 const char *,
  66                                                 unsigned int,
  67                                                 unsigned int *));
  68 static void bitset_stats_print_1
  69 PARAMS ((FILE *, const char *, struct bitset_type_stats_struct *));
  70 static void bitset_stats_print PARAMS ((FILE *, int));
  71 static void bitset_stats_read PARAMS ((void));
  72 static void bitset_stats_write PARAMS ((void));
  73
  74 #define BITSET_STATS_XMALLOCS_INC(TYPE)                 \
  75   if (bitset_stats)                                     \
  76     bitset_stats->types[(TYPE)].xmallocs++
  77
  78 #define BITSET_STATS_XFREES_INC(BSET)                   \
  79   if (bitset_stats)                                     \
  80     bitset_stats->types[BITSET_TYPE_ (BSET)].xfrees++
  81
  82 #define BITSET_STATS_OBALLOCS_INC(TYPE)                 \
  83   if (bitset_stats)                                     \
  84     bitset_stats->types[(TYPE)].oballocs++
  85
  86 #define BITSET_STATS_OBFREES_INC(BSET)                  \
  87   if (bitset_stats)                                     \
  88     bitset_stats->types[BITSET_TYPE_ (BSET)].obfrees++
  89
  90 #define BITSET_STATS_LISTS_INC(BSET)                    \
  91   if (bitset_stats)                                     \
  92     bitset_stats->types[BITSET_TYPE_ (BSET)].lists++
  93
  94 #define BITSET_STATS_LIST_COUNTS_INC(BSET, I)           \
  95   if (bitset_stats)                                     \
  96     bitset_stats->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++
  97
  98 #define BITSET_STATS_LIST_SIZES_INC(BSET, I)            \
  99   if (bitset_stats)                                     \
 100     bitset_stats->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++
 101
 102 #define BITSET_STATS_LIST_DENSITY_INC(BSET, I)          \
 103   if (bitset_stats)                                     \
 104     bitset_stats->types[BITSET_TYPE_ (BSET)].list_density[(I)]++
 105
 106 #else
 107 #define BITSET_STATS_XMALLOCS_INC(TYPE)
 108
 109 #define BITSET_STATS_XFREES_INC(BSET)
 110
 111 #define BITSET_STATS_OBALLOCS_INC(TYPE)
 112
 113 #define BITSET_STATS_OBFREES_INC(BSET)
 114
 115 #define BITSET_STATS_LISTS_INC(BSET)
 116
 117 #define BITSET_STATS_LIST_COUNTS_INC(BSET, I)
 118
 119 #define BITSET_STATS_LIST_SIZES_INC(BSET, I)
 120
 121 #define BITSET_STATS_LIST_DENSITY_INC(BSET, I)
 122 #endif /* BITSET_STATS  */
 123
 124
 125 /* Return number of bytes required to create a N_BIT bitset
 126    of TYPE.  The bitset may grow to require more bytes than this.  */
 127 int
 128 bitset_bytes (type, n_bits)
 129      enum bitset_type type;
 130      bitset_bindex n_bits;
 131 {
 132   unsigned int bytes;
 133
 134   switch (type)
 135     {
 136     case BITSET_ARRAY:
 137       bytes = sbitset_bytes (n_bits);
 138       break;
 139
 140     case BITSET_LIST:
 141       bytes = lbitset_bytes (n_bits);
 142       break;
 143
 144     case BITSET_TABLE:
 145       bytes = ebitset_bytes (n_bits);
 146       break;
 147
 148     default:
 149       abort ();
 150     }
 151
 152   return bytes;
 153 }
 154
 155
 156 /* Initialise bitset BSET of TYPE for N_BITS.  */
 157 bitset
 158 bitset_init (bset, n_bits, type)
 159      bitset bset;
 160      bitset_bindex n_bits;
 161      enum bitset_type type;
 162 {
 163   switch (type)
 164     {
 165     case BITSET_ARRAY:
 166       return sbitset_init (bset, n_bits);
 167
 168     case BITSET_LIST:
 169       return lbitset_init (bset, n_bits);
 170
 171     case BITSET_TABLE:
 172       return ebitset_init (bset, n_bits);
 173
 174     default:
 175       abort ();
 176     }
 177 }
 178
 179
 180 /* Select a bitset type for a set of N_BITS and with attribute hints
 181    specified by ATTR.  For variable size bitsets, N_BITS is only a
 182    hint and may be zero.  */
 183 enum bitset_type
 184 bitset_type_choose (n_bits, attr)
 185      bitset_bindex n_bits ATTRIBUTE_UNUSED;
 186      unsigned int attr;
 187 {
 188   enum bitset_type type;
 189
 190 #if BITSET_CHECK
 191   /* Check attributes.  */
 192   if (attr & BITSET_FIXED && attr & BITSET_VARIABLE)
 193     abort ();
 194   if (attr & BITSET_SPARSE && attr & BITSET_DENSE)
 195     abort ();
 196
 197   /* Note that sometimes we will be asked for a zero length
 198      fixed size bitset.  */
 199 #endif
 200
 201   /* Choose the type of bitset.  */
 202
 203   type = BITSET_ARRAY;
 204   /* Currently, the simple bitsets do not support a variable size.  */
 205   if (attr & BITSET_VARIABLE || attr & BITSET_SPARSE)
 206     {
 207       type = BITSET_LIST;
 208       if (attr & BITSET_DENSE || attr & BITSET_GREEDY)
 209         type = BITSET_TABLE;
 210     }
 211
 212   return type;
 213 }
 214
 215
 216 /* Create a bitset of N_BITS of type TYPE.  */
 217 bitset
 218 bitset_alloc (n_bits, type)
 219      bitset_bindex n_bits;
 220      enum bitset_type type;
 221 {
 222   unsigned int bytes;
 223   bitset bset;
 224
 225   BITSET_STATS_XMALLOCS_INC (type);
 226
 227   bytes = bitset_bytes (type, n_bits);
 228
 229   bset = (bitset) xcalloc (1, bytes);
 230
 231   /* The cache is disabled until some elements are allocated.  If we
 232      have variable length arrays, then we may need to allocate dummy
 233      element.  */
 234
 235   return bitset_init (bset, n_bits, type);
 236 }
 237
 238
 239 /* Create a bitset of N_BITS of type TYPE.  */
 240 bitset
 241 bitset_obstack_alloc (bobstack, n_bits, type)
 242      struct obstack *bobstack;
 243      bitset_bindex n_bits;
 244      enum bitset_type type;
 245 {
 246   unsigned int bytes;
 247   bitset bset;
 248
 249   BITSET_STATS_OBALLOCS_INC (type);
 250
 251   bytes = bitset_bytes (type, n_bits);
 252
 253   bset = obstack_alloc (bobstack, bytes);
 254   memset (bset, 0, bytes);
 255
 256   return bitset_init (bset, n_bits, type);
 257 }
 258
 259
 260 /* Create a bitset of N_BITS and with attribute hints specified by
 261    ATTR.  */
 262 bitset
 263 bitset_create (n_bits, attr)
 264      bitset_bindex n_bits;
 265      unsigned int attr;
 266 {
 267   enum bitset_type type;
 268
 269   type = bitset_type_choose (n_bits, attr);
 270
 271   return bitset_alloc (n_bits, type);
 272 }
 273
 274
 275 /* Free bitset BSET.  */
 276 void
 277 bitset_free (bset)
 278      bitset bset;
 279 {
 280   BITSET_STATS_XFREES_INC (bset);
 281
 282   BITSET_FREE_ (bset);
 283   free (bset);
 284 }
 285
 286
 287 /* Free bitset BSET allocated on obstack.  */
 288 void
 289 bitset_obstack_free (bset)
 290      bitset bset;
 291 {
 292   BITSET_STATS_OBFREES_INC (bset);
 293
 294   BITSET_FREE_ (bset);
 295 }
 296
 297
 298 /* Find next bit set in SRC starting from and including BITNO.
 299    Return -1 if SRC empty.  */
 300 int
 301 bitset_next (src, bitno)
 302      bitset src;
 303      bitset_bindex bitno;
 304 {
 305   bitset_bindex val;
 306   bitset_bindex next = bitno;
 307
 308   if (!bitset_list (src, &val, 1, &next))
 309     return -1;
 310   return val;
 311 }
 312
 313
 314 /* Find previous bit set in SRC starting from and including BITNO.
 315    Return -1 if SRC empty.  */
 316 int
 317 bitset_prev (src, bitno)
 318      bitset src;
 319      bitset_bindex bitno;
 320 {
 321   bitset_bindex val;
 322   bitset_bindex next = bitno;
 323
 324   if (!bitset_reverse_list (src, &val, 1, &next))
 325     return -1;
 326   return val;
 327 }
 328
 329
 330 /* Find first set bit.   */
 331 int
 332 bitset_first (src)
 333      bitset src;
 334 {
 335   return bitset_next (src, 0);
 336 }
 337
 338
 339 /* Find last set bit.   */
 340 int
 341 bitset_last (src)
 342      bitset src;
 343 {
 344   return bitset_prev (src, 0);
 345 }
 346
 347
 348 /* Return non-zero if BITNO in SRC is the only set bit.  */
 349 int
 350 bitset_only_set_p (src, bitno)
 351      bitset src;
 352      bitset_bindex bitno;
 353 {
 354   bitset_bindex val[2];
 355   bitset_bindex next = 0;
 356
 357   if (bitset_list (src, val, 2, &next) != 1)
 358     return 0;
 359   return val[0] == bitno;
 360 }
 361
 362
 363 /* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
 364 int
 365 bitset_toggle (bset, bitno)
 366     bitset bset;
 367     bitset_bindex bitno;
 368 {
 369   /* This routine is for completeness.  It could be optimized if
 370      required.  */
 371   if (bitset_test (bset, bitno))
 372     {
 373       bitset_reset (bset, bitno);
 374       return 0;
 375     }
 376   else
 377     {
 378       bitset_set (bset, bitno);
 379       return 1;
 380     }
 381 }
 382
 383
 384 /* Print contents of bitset BSET to FILE.   */
 385 static void
 386 bitset_print (file, bset, verbose)
 387      FILE *file;
 388      bitset bset;
 389      int verbose;
 390 {
 391   unsigned int i, pos;
 392
 393   if (verbose)
 394     fprintf (file, "n_bits = %d, set = {", bitset_size (bset));
 395
 396   pos = 30;
 397   BITSET_EXECUTE (bset, 0, i,
 398   {
 399     if (pos > 70)
 400       {
 401         fprintf (file, "\n");
 402         pos = 0;
 403       }
 404
 405     fprintf (file, "%d ", i);
 406     pos += 1 + (i >= 10) + (i >= 100);
 407   });
 408
 409   if (verbose)
 410     fprintf (file, "}\n");
 411 }
 412
 413
 414 /* DST = SRC.  Return non-zero if DST != SRC.  */
 415 int
 416 bitset_copy (dst, src)
 417      bitset dst;
 418      bitset src;
 419 {
 420   unsigned int i;
 421
 422   if (BITSET_COMPATIBLE_ (dst, src))
 423     return BITSET_COPY_ (dst, src);
 424
 425   /* Convert bitset types.  We assume that the DST bitset
 426      is large enough to hold the SRC bitset.  */
 427   bitset_zero (dst);
 428   BITSET_EXECUTE (src, 0, i,
 429   {
 430      bitset_set (dst, i);
 431   });
 432
 433   return 1;
 434 }
 435
 436
 437 /* Return size in bits of bitset SRC.  */
 438 int
 439 bitset_size (src)
 440      bitset src;
 441 {
 442   return BITSET_SIZE_ (src);
 443 }
 444
 445
 446 /* Return number of bits set in bitset SRC.  */
 447 int
 448 bitset_count (src)
 449      bitset src;
 450 {
 451   bitset_bindex list[BITSET_LIST_SIZE];
 452   bitset_bindex next;
 453   int num;
 454   int count;
 455
 456   next = 0;
 457   for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next));
 458        count += num)
 459     continue;
 460
 461   return count;
 462 }
 463
 464
 465 /* DST = 0.  */
 466 int
 467 bitset_zero (dst)
 468      bitset dst;
 469 {
 470   return BITSET_ZERO_ (dst);
 471 }
 472
 473
 474 /* DST = ~0.  */
 475 int
 476 bitset_ones (dst)
 477      bitset dst;
 478 {
 479   return BITSET_ONES_ (dst);
 480 }
 481
 482
 483 /* Return SRC == 0.  */
 484 int
 485 bitset_empty_p (src)
 486      bitset src;
 487 {
 488   return BITSET_EMPTY_P_ (src);
 489 }
 490
 491
 492 /* Return DST == DST | SRC.  */
 493 int
 494 bitset_subset_p (dst, src)
 495      bitset dst;
 496      bitset src;
 497 {
 498   BITSET_CHECK2_ (dst, src);
 499   return BITSET_SUBSET_P_ (dst, src);
 500 }
 501
 502
 503 /* Return DST == SRC.  */
 504 int
 505 bitset_equal_p (dst, src)
 506      bitset dst;
 507      bitset src;
 508 {
 509   BITSET_CHECK2_ (dst, src);
 510   return BITSET_EQUAL_P_ (dst, src);
 511 }
 512
 513
 514 /* Return DST & SRC == 0.  */
 515 int
 516 bitset_disjoint_p (dst, src)
 517      bitset dst;
 518      bitset src;
 519 {
 520   BITSET_CHECK2_ (dst, src);
 521   return BITSET_DISJOINT_P_ (dst, src);
 522 }
 523
 524
 525 /* DST = ~SRC.  */
 526 int
 527 bitset_not (dst, src)
 528      bitset dst;
 529      bitset src;
 530 {
 531   BITSET_CHECK2_ (dst, src);
 532   return BITSET_NOT_ (dst, src);
 533 }
 534
 535
 536 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 537 int
 538 bitset_or (dst, src1, src2)
 539      bitset dst;
 540      bitset src1;
 541      bitset src2;
 542 {
 543   BITSET_CHECK3_ (dst, src1, src2);
 544   return BITSET_OR_ (dst, src1, src2);
 545 }
 546
 547
 548 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 549 int
 550 bitset_and (dst, src1, src2)
 551      bitset dst;
 552      bitset src1;
 553      bitset src2;
 554 {
 555   BITSET_CHECK3_ (dst, src1, src2);
 556   return BITSET_AND_ (dst, src1, src2);
 557 }
 558
 559
 560 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 561 int
 562 bitset_xor (dst, src1, src2)
 563      bitset dst;
 564      bitset src1;
 565      bitset src2;
 566 {
 567   BITSET_CHECK3_ (dst, src1, src2);
 568   return BITSET_XOR_ (dst, src1, src2);
 569 }
 570
 571
 572 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 573 int
 574 bitset_andn (dst, src1, src2)
 575      bitset dst;
 576      bitset src1;
 577      bitset src2;
 578 {
 579   BITSET_CHECK3_ (dst, src1, src2);
 580   return BITSET_ANDN_ (dst, src1, src2);
 581 }
 582
 583
 584 int
 585 bitset_op4 (dst, src1, src2, src3, op)
 586      bitset dst;
 587      bitset src1;
 588      bitset src2;
 589      bitset src3;
 590      enum bitset_ops op;
 591 {
 592   int changed = 0;
 593   bitset tmp;
 594
 595   /* Create temporary bitset.  */
 596   tmp = bitset_alloc (0, BITSET_TYPE_ (dst));
 597
 598   switch (op)
 599     {
 600     case BITSET_OP_OR_AND:
 601       BITSET_OR_ (tmp, src1, src2);
 602       changed = BITSET_AND_ (dst, src3, tmp);
 603       break;
 604
 605     case BITSET_OP_AND_OR:
 606       BITSET_AND_ (tmp, src1, src2);
 607       changed = BITSET_OR_ (dst, src3, tmp);
 608       break;
 609
 610     case BITSET_OP_ANDN_OR:
 611       BITSET_ANDN_ (tmp, src1, src2);
 612       changed = BITSET_OR_ (dst, src3, tmp);
 613       break;
 614
 615     default:
 616       abort ();
 617     }
 618
 619   bitset_free (tmp);
 620   return changed;
 621 }
 622
 623
 624 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 625    DST != (SRC1 | SRC2) & SRC3.  */
 626 int
 627 bitset_or_and (dst, src1, src2, src3)
 628      bitset dst;
 629      bitset src1;
 630      bitset src2;
 631      bitset src3;
 632 {
 633   BITSET_CHECK4_ (dst, src1, src2, src3);
 634   return BITSET_OR_AND_ (dst, src1, src2, src3);
 635 }
 636
 637
 638 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 639    DST != (SRC1 & SRC2) | SRC3.  */
 640 int
 641 bitset_and_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   return BITSET_AND_OR_ (dst, src1, src2, src3);
 649 }
 650
 651
 652 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 653    DST != (SRC1 & ~SRC2) | SRC3.  */
 654 int
 655 bitset_andn_or (dst, src1, src2, src3)
 656      bitset dst;
 657      bitset src1;
 658      bitset src2;
 659      bitset src3;
 660 {
 661   BITSET_CHECK4_ (dst, src1, src2, src3);
 662   return BITSET_ANDN_OR_ (dst, src1, src2, src3);
 663 }
 664
 665
 666 /* Dump bitset BSET to FILE.  */
 667 void
 668 bitset_dump (file, bset)
 669      FILE *file;
 670      bitset bset;
 671 {
 672   bitset_print (file, bset, 0);
 673 }
 674
 675
 676 /* Function to be called from debugger to print bitset.  */
 677 void
 678 debug_bitset (bset)
 679      bitset bset;
 680 {
 681   if (bset)
 682     bitset_print (stderr, bset, 1);
 683 }
 684
 685
 686 /* Release memory associated with bitsets.  */
 687 void
 688 bitset_release_memory ()
 689 {
 690   lbitset_release_memory ();
 691   ebitset_release_memory ();
 692 }
 693
 694
 695 #if BITSET_STATS
 696 int
 697 bitset_list (bset, list, num, next)
 698      bitset bset;
 699      bitset_bindex *list;
 700      bitset_bindex num;
 701      bitset_bindex *next;
 702 {
 703   bitset_bindex count;
 704
 705   count = BITSET_LIST_ (bset, list, num, next);
 706
 707   if (bitset_stats)
 708     {
 709       bitset_bindex tmp;
 710       bitset_bindex size;
 711       bitset_bindex i;
 712       enum bitset_type type;
 713
 714       type = BITSET_TYPE_ (bset);
 715       BITSET_STATS_LISTS_INC (bset);
 716
 717       /* Log histogram of number of set bits.  */
 718       for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
 719         continue;
 720       if (i >= BITSET_LOG_COUNT_BINS)
 721         i = BITSET_LOG_COUNT_BINS - 1;
 722       BITSET_STATS_LIST_COUNTS_INC (bset, i);
 723
 724       /* Log histogram of number of bits in set.  */
 725       size = bitset_size (bset);
 726       for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
 727         continue;
 728       if (i >= BITSET_LOG_SIZE_BINS)
 729         i = BITSET_LOG_SIZE_BINS - 1;
 730       BITSET_STATS_LIST_SIZES_INC (bset, i);
 731
 732       /* Histogram of fraction of bits set.  */
 733       i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
 734       if (i >= BITSET_DENSITY_BINS)
 735         i = BITSET_DENSITY_BINS - 1;
 736       BITSET_STATS_LIST_DENSITY_INC (bset, i);
 737     }
 738   return count;
 739 }
 740
 741
 742 /* Print a percentage histogram with message MSG to FILE.  */
 743 static void
 744 bitset_percent_histogram_print (file, name, msg, n_bins, bins)
 745      FILE *file;
 746      const char *name;
 747      const char *msg;
 748      unsigned int n_bins;
 749      unsigned int *bins;
 750 {
 751   unsigned int i;
 752   unsigned int total;
 753
 754   total = 0;
 755   for (i = 0; i < n_bins; i++)
 756     total += bins[i];
 757
 758   if (!total)
 759     return;
 760
 761   fprintf (file, "%s %s", name, msg);
 762   for (i = 0; i < n_bins; i++)
 763     fprintf (file, "%.0f-%.0f%%\t%8d (%5.1f%%)\n",
 764              i * 100.0 / n_bins,
 765              (i + 1) * 100.0 / n_bins, bins[i],
 766              (100.0 * bins[i]) / total);
 767 }
 768
 769
 770 /* Print a log histogram with message MSG to FILE.  */
 771 static void
 772 bitset_log_histogram_print (file, name, msg, n_bins, bins)
 773      FILE *file;
 774      const char *name;
 775      const char *msg;
 776      unsigned int n_bins;
 777      unsigned int *bins;
 778 {
 779   unsigned int i;
 780   unsigned int total;
 781   unsigned int max_width;
 782
 783   total = 0;
 784   for (i = 0; i < n_bins; i++)
 785     total += bins[i];
 786
 787   if (!total)
 788     return;
 789
 790   /* 2 * ceil (log10(2) * (N - 1)) + 1  */
 791   max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;
 792
 793   fprintf (file, "%s %s", name, msg);
 794   for (i = 0; i < 2; i++)
 795     fprintf (file, "%*d\t%8d (%5.1f%%)\n",
 796              max_width, i, bins[i], 100.0 * bins[i] / total);
 797
 798   /* Perhaps we should bail out once the histogram goes to zero.  */
 799   for (; i < n_bins; i++)
 800     fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n",
 801              max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
 802              1 << (i - 1), (1 << i) - 1, bins[i],
 803              (100.0 * bins[i]) / total);
 804 }
 805
 806
 807 /* Print bitset statistics to FILE.  */
 808 static void
 809 bitset_stats_print_1 (file, name, stats)
 810      FILE *file;
 811      const char *name;
 812      struct bitset_type_stats_struct *stats;
 813 {
 814   if (!stats)
 815     return;
 816
 817   fprintf (file, "%d %ss xmalloced, %d freed.\n",
 818            stats->xmallocs, name, stats->xfrees);
 819   fprintf (file, "%d %ss oballoced, %d freed.\n",
 820            stats->oballocs, name, stats->obfrees);
 821
 822   fprintf (file, "%d bitset_lists\n", stats->lists);
 823
 824   bitset_log_histogram_print (file, name, "count log histogram\n",
 825                               BITSET_LOG_COUNT_BINS, stats->list_counts);
 826
 827   bitset_log_histogram_print (file, name, "size log histogram\n",
 828                               BITSET_LOG_SIZE_BINS, stats->list_sizes);
 829
 830   bitset_percent_histogram_print (file, name, "density histogram\n",
 831                                   BITSET_DENSITY_BINS, stats->list_density);
 832 }
 833
 834
 835 /* Print all bitset statistics to FILE.  */
 836 static void
 837 bitset_stats_print (file, verbose)
 838      FILE *file;
 839      int verbose ATTRIBUTE_UNUSED;
 840 {
 841   int i;
 842   static const char *names[] = BITSET_TYPE_NAMES;
 843
 844   if (!bitset_stats)
 845     return;
 846
 847   fprintf (file, "Bitset statistics:\n\n");
 848
 849   if (bitset_stats->runs > 1)
 850     fprintf (file, "Accumulated runs = %d\n", bitset_stats->runs);
 851
 852   for (i = 0; i < BITSET_TYPE_NUM; i++)
 853     bitset_stats_print_1 (file, names[i], &bitset_stats->types[i]);
 854 }
 855 #endif /* BITSET_STATS  */
 856
 857
 858 /* Initialise bitset statistics logging.  */
 859 void
 860 bitset_stats_init ()
 861 {
 862 #if BITSET_STATS
 863   bitset_stats = &bitset_stats_data;
 864   bitset_stats_read ();
 865 #endif /* BITSET_STATS  */
 866 }
 867
 868
 869 /* Read bitset statistics file.  */
 870 static void
 871 bitset_stats_read ()
 872 {
 873   FILE *file;
 874
 875   if (!bitset_stats)
 876     return;
 877
 878   file = fopen (BITSET_STATS_FILE, "r");
 879   if (file)
 880     {
 881       if (fread (&bitset_stats_data, sizeof (bitset_stats_data),
 882                  1, file) != 1)
 883         {
 884           if (ferror (file))
 885             perror ("Could not read stats file.");
 886           else
 887             fprintf (stderr, "Bad stats file size.\n");
 888         }
 889       fclose (file);
 890     }
 891   bitset_stats_data.runs++;
 892 }
 893
 894
 895 /* Write bitset statistics file.  */
 896 static void
 897 bitset_stats_write ()
 898 {
 899   FILE *file;
 900
 901   if (!bitset_stats)
 902     return;
 903
 904   file = fopen (BITSET_STATS_FILE, "w");
 905   if (file)
 906     {
 907       if (fwrite (&bitset_stats_data, sizeof (bitset_stats_data),
 908                   1, file) != 1)
 909         perror ("Could not write stats file.");
 910       fclose (file);
 911     }
 912   else
 913     perror ("Could not open stats file for writing.");
 914 }
 915
 916
 917 /* Dump bitset statistics to FILE.  */
 918 void
 919 bitset_stats_dump (file)
 920      FILE *file;
 921 {
 922 #if BITSET_STATS
 923   bitset_stats_print (file, 0);
 924   bitset_stats_write ();
 925 #endif /* BITSET_STATS  */
 926 }
 927
 928
 929 /* Function to be called from debugger to print bitset stats.  */
 930 void
 931 debug_bitset_stats (void)
 932 {
 933 #if BITSET_STATS
 934   bitset_stats_print (stderr, 1);
 935 #endif /* BITSET_STATS  */
 936 }