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 /* Print contents of bitset BSET to FILE.   */
 349 static void
 350 bitset_print (file, bset, verbose)
 351      FILE *file;
 352      bitset bset;
 353      int verbose;
 354 {
 355   unsigned int i, pos;
 356
 357   if (verbose)
 358     fprintf (file, "n_bits = %d, set = {", bitset_size (bset));
 359
 360   pos = 30;
 361   BITSET_EXECUTE (bset, 0, i,
 362   {
 363     if (pos > 70)
 364       {
 365         fprintf (file, "\n");
 366         pos = 0;
 367       }
 368
 369     fprintf (file, "%d ", i);
 370     pos += 1 + (i >= 10) + (i >= 100);
 371   });
 372
 373   if (verbose)
 374     fprintf (file, "}\n");
 375 }
 376
 377
 378 /* DST = SRC.  Return non-zero if DST != SRC.  */
 379 int
 380 bitset_copy (dst, src)
 381      bitset dst;
 382      bitset src;
 383 {
 384   unsigned int i;
 385
 386   if (BITSET_COMPATIBLE_ (dst, src))
 387     return BITSET_COPY_ (dst, src);
 388
 389   /* Convert bitset types.  We assume that the DST bitset
 390      is large enough to hold the SRC bitset.  */
 391   bitset_zero (dst);
 392   BITSET_EXECUTE (src, 0, i,
 393   {
 394      bitset_set (dst, i);
 395   });
 396
 397   return 1;
 398 }
 399
 400
 401 /* Return size in bits of bitset SRC.  */
 402 int
 403 bitset_size (src)
 404      bitset src;
 405 {
 406   return BITSET_SIZE_ (src);
 407 }
 408
 409
 410 /* Return number of bits set in bitset SRC.  */
 411 int
 412 bitset_count (src)
 413      bitset src;
 414 {
 415   bitset_bindex list[BITSET_LIST_SIZE];
 416   bitset_bindex next;
 417   int num;
 418   int count;
 419
 420   next = 0;
 421   for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next));
 422        count += num)
 423     continue;
 424
 425   return count;
 426 }
 427
 428
 429 /* DST = 0.  */
 430 int
 431 bitset_zero (dst)
 432      bitset dst;
 433 {
 434   return BITSET_ZERO_ (dst);
 435 }
 436
 437
 438 /* DST = ~0.  */
 439 int
 440 bitset_ones (dst)
 441      bitset dst;
 442 {
 443   return BITSET_ONES_ (dst);
 444 }
 445
 446
 447 /* Return SRC == 0.  */
 448 int
 449 bitset_empty_p (src)
 450      bitset src;
 451 {
 452   return BITSET_EMPTY_P_ (src);
 453 }
 454
 455
 456 /* Return DST == DST | SRC.  */
 457 int
 458 bitset_subset_p (dst, src)
 459      bitset dst;
 460      bitset src;
 461 {
 462   BITSET_CHECK2_ (dst, src);
 463   return BITSET_SUBSET_P_ (dst, src);
 464 }
 465
 466
 467 /* Return DST == SRC.  */
 468 int
 469 bitset_equal_p (dst, src)
 470      bitset dst;
 471      bitset src;
 472 {
 473   BITSET_CHECK2_ (dst, src);
 474   return BITSET_EQUAL_P_ (dst, src);
 475 }
 476
 477
 478 /* Return DST & SRC == 0.  */
 479 int
 480 bitset_disjoint_p (dst, src)
 481      bitset dst;
 482      bitset src;
 483 {
 484   BITSET_CHECK2_ (dst, src);
 485   return BITSET_DISJOINT_P_ (dst, src);
 486 }
 487
 488
 489 /* DST = ~SRC.  */
 490 int
 491 bitset_not (dst, src)
 492      bitset dst;
 493      bitset src;
 494 {
 495   BITSET_CHECK2_ (dst, src);
 496   return BITSET_NOT_ (dst, src);
 497 }
 498
 499
 500 /* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
 501 int
 502 bitset_or (dst, src1, src2)
 503      bitset dst;
 504      bitset src1;
 505      bitset src2;
 506 {
 507   BITSET_CHECK3_ (dst, src1, src2);
 508   return BITSET_OR_ (dst, src1, src2);
 509 }
 510
 511
 512 /* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
 513 int
 514 bitset_and (dst, src1, src2)
 515      bitset dst;
 516      bitset src1;
 517      bitset src2;
 518 {
 519   BITSET_CHECK3_ (dst, src1, src2);
 520   return BITSET_AND_ (dst, src1, src2);
 521 }
 522
 523
 524 /* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
 525 int
 526 bitset_xor (dst, src1, src2)
 527      bitset dst;
 528      bitset src1;
 529      bitset src2;
 530 {
 531   BITSET_CHECK3_ (dst, src1, src2);
 532   return BITSET_XOR_ (dst, src1, src2);
 533 }
 534
 535
 536 /* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
 537 int
 538 bitset_andn (dst, src1, src2)
 539      bitset dst;
 540      bitset src1;
 541      bitset src2;
 542 {
 543   BITSET_CHECK3_ (dst, src1, src2);
 544   return BITSET_ANDN_ (dst, src1, src2);
 545 }
 546
 547
 548 /* DST = SRC1 | ~SRC2.  Return non-zero if DST != SRC1 | ~SRC2.  */
 549 int
 550 bitset_orn (dst, src1, src2)
 551      bitset dst;
 552      bitset src1;
 553      bitset src2;
 554 {
 555   BITSET_CHECK3_ (dst, src1, src2);
 556   return BITSET_ORN_ (dst, src1, src2);
 557 }
 558
 559
 560 int
 561 bitset_op4 (dst, src1, src2, src3, op)
 562      bitset dst;
 563      bitset src1;
 564      bitset src2;
 565      bitset src3;
 566      enum bitset_ops op;
 567 {
 568   int changed = 0;
 569   bitset tmp;
 570
 571   /* Create temporary bitset.  */
 572   tmp = bitset_alloc (BITSET_TYPE_ (dst), 0);
 573
 574   switch (op)
 575     {
 576     case BITSET_OP_OR_AND:
 577       BITSET_OR_ (tmp, src1, src2);
 578       changed = BITSET_AND_ (dst, src3, tmp);
 579       break;
 580
 581     case BITSET_OP_AND_OR:
 582       BITSET_AND_ (tmp, src1, src2);
 583       changed = BITSET_OR_ (dst, src3, tmp);
 584       break;
 585
 586     case BITSET_OP_ANDN_OR:
 587       BITSET_ANDN_ (tmp, src1, src2);
 588       changed = BITSET_OR_ (dst, src3, tmp);
 589       break;
 590
 591     default:
 592       abort ();
 593     }
 594
 595   bitset_free (tmp);
 596   return changed;
 597 }
 598
 599
 600 /* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
 601    DST != (SRC1 | SRC2) & SRC3.  */
 602 int
 603 bitset_or_and (dst, src1, src2, src3)
 604      bitset dst;
 605      bitset src1;
 606      bitset src2;
 607      bitset src3;
 608 {
 609   BITSET_CHECK4_ (dst, src1, src2, src3);
 610   return BITSET_OR_AND_ (dst, src1, src2, src3);
 611 }
 612
 613
 614 /* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
 615    DST != (SRC1 & SRC2) | SRC3.  */
 616 int
 617 bitset_and_or (dst, src1, src2, src3)
 618      bitset dst;
 619      bitset src1;
 620      bitset src2;
 621      bitset src3;
 622 {
 623   BITSET_CHECK4_ (dst, src1, src2, src3);
 624   return BITSET_AND_OR_ (dst, src1, src2, src3);
 625 }
 626
 627
 628 /* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
 629    DST != (SRC1 & ~SRC2) | SRC3.  */
 630 int
 631 bitset_andn_or (dst, src1, src2, src3)
 632      bitset dst;
 633      bitset src1;
 634      bitset src2;
 635      bitset src3;
 636 {
 637   BITSET_CHECK4_ (dst, src1, src2, src3);
 638   return BITSET_ANDN_OR_ (dst, src1, src2, src3);
 639 }
 640
 641
 642 /* Dump bitset BSET to FILE.  */
 643 void
 644 bitset_dump (file, bset)
 645      FILE *file;
 646      bitset bset;
 647 {
 648   bitset_print (file, bset, 0);
 649 }
 650
 651
 652 /* Function to be called from debugger to print bitset.  */
 653 void
 654 debug_bitset (bset)
 655      bitset bset;
 656 {
 657   if (bset)
 658     bitset_print (stderr, bset, 1);
 659 }
 660
 661
 662 /* Release memory associated with bitsets.  */
 663 void
 664 bitset_release_memory ()
 665 {
 666   lbitset_release_memory ();
 667   ebitset_release_memory ();
 668 }
 669
 670
 671 #if BITSET_STATS
 672 int
 673 bitset_list (bset, list, num, next)
 674      bitset bset;
 675      bitset_bindex *list;
 676      bitset_bindex num;
 677      bitset_bindex *next;
 678 {
 679   bitset_bindex count;
 680
 681   count = BITSET_LIST_ (bset, list, num, next);
 682
 683   if (bitset_stats)
 684     {
 685       bitset_bindex tmp;
 686       bitset_bindex size;
 687       bitset_bindex i;
 688       enum bitset_type type;
 689
 690       type = BITSET_TYPE_ (bset);
 691       BITSET_STATS_LISTS_INC (bset);
 692
 693       /* Log histogram of number of set bits.  */
 694       for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
 695         continue;
 696       if (i >= BITSET_LOG_COUNT_BINS)
 697         i = BITSET_LOG_COUNT_BINS - 1;
 698       BITSET_STATS_LIST_COUNTS_INC (bset, i);
 699
 700       /* Log histogram of number of bits in set.  */
 701       size = bitset_size (bset);
 702       for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
 703         continue;
 704       if (i >= BITSET_LOG_SIZE_BINS)
 705         i = BITSET_LOG_SIZE_BINS - 1;
 706       BITSET_STATS_LIST_SIZES_INC (bset, i);
 707
 708       /* Histogram of fraction of bits set.  */
 709       i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
 710       if (i >= BITSET_DENSITY_BINS)
 711         i = BITSET_DENSITY_BINS - 1;
 712       BITSET_STATS_LIST_DENSITY_INC (bset, i);
 713     }
 714   return count;
 715 }
 716
 717
 718 /* Print a percentage histogram with message MSG to FILE.  */
 719 static void
 720 bitset_percent_histogram_print (file, name, msg, n_bins, bins)
 721      FILE *file;
 722      const char *name;
 723      const char *msg;
 724      unsigned int n_bins;
 725      unsigned int *bins;
 726 {
 727   unsigned int i;
 728   unsigned int total;
 729
 730   total = 0;
 731   for (i = 0; i < n_bins; i++)
 732     total += bins[i];
 733
 734   if (!total)
 735     return;
 736
 737   fprintf (file, "%s %s", name, msg);
 738   for (i = 0; i < n_bins; i++)
 739     fprintf (file, "%.0f-%.0f%%\t%8d (%5.1f%%)\n",
 740              i * 100.0 / n_bins,
 741              (i + 1) * 100.0 / n_bins, bins[i],
 742              (100.0 * bins[i]) / total);
 743 }
 744
 745
 746 /* Print a log histogram with message MSG to FILE.  */
 747 static void
 748 bitset_log_histogram_print (file, name, msg, n_bins, bins)
 749      FILE *file;
 750      const char *name;
 751      const char *msg;
 752      unsigned int n_bins;
 753      unsigned int *bins;
 754 {
 755   unsigned int i;
 756   unsigned int total;
 757   unsigned int max_width;
 758
 759   total = 0;
 760   for (i = 0; i < n_bins; i++)
 761     total += bins[i];
 762
 763   if (!total)
 764     return;
 765
 766   /* 2 * ceil (log10(2) * (N - 1)) + 1  */
 767   max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;
 768
 769   fprintf (file, "%s %s", name, msg);
 770   for (i = 0; i < 2; i++)
 771     fprintf (file, "%*d\t%8d (%5.1f%%)\n",
 772              max_width, i, bins[i], 100.0 * bins[i] / total);
 773
 774   /* Perhaps we should bail out once the histogram goes to zero.  */
 775   for (; i < n_bins; i++)
 776     fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n",
 777              max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
 778              1 << (i - 1), (1 << i) - 1, bins[i],
 779              (100.0 * bins[i]) / total);
 780 }
 781
 782
 783 /* Print bitset statistics to FILE.  */
 784 static void
 785 bitset_stats_print_1 (file, name, stats)
 786      FILE *file;
 787      const char *name;
 788      struct bitset_type_stats_struct *stats;
 789 {
 790   if (!stats)
 791     return;
 792
 793   fprintf (file, "%d %ss xmalloced, %d freed.\n",
 794            stats->xmallocs, name, stats->xfrees);
 795   fprintf (file, "%d %ss oballoced, %d freed.\n",
 796            stats->oballocs, name, stats->obfrees);
 797
 798   fprintf (file, "%d bitset_lists\n", stats->lists);
 799
 800   bitset_log_histogram_print (file, name, "count log histogram\n",
 801                               BITSET_LOG_COUNT_BINS, stats->list_counts);
 802
 803   bitset_log_histogram_print (file, name, "size log histogram\n",
 804                               BITSET_LOG_SIZE_BINS, stats->list_sizes);
 805
 806   bitset_percent_histogram_print (file, name, "density histogram\n",
 807                                   BITSET_DENSITY_BINS, stats->list_density);
 808 }
 809
 810
 811 /* Print all bitset statistics to FILE.  */
 812 static void
 813 bitset_stats_print (file, verbose)
 814      FILE *file;
 815      int verbose ATTRIBUTE_UNUSED;
 816 {
 817   int i;
 818   static const char *names[] = BITSET_TYPE_NAMES;
 819
 820   if (!bitset_stats)
 821     return;
 822
 823   fprintf (file, "Bitset statistics:\n\n");
 824
 825   if (bitset_stats->runs > 1)
 826     fprintf (file, "Accumulated runs = %d\n", bitset_stats->runs);
 827
 828   for (i = 0; i < BITSET_TYPE_NUM; i++)
 829     bitset_stats_print_1 (file, names[i], &bitset_stats->types[i]);
 830 }
 831 #endif /* BITSET_STATS  */
 832
 833
 834 /* Initialise bitset statistics logging.  */
 835 void
 836 bitset_stats_init ()
 837 {
 838 #if BITSET_STATS
 839   bitset_stats = &bitset_stats_data;
 840   bitset_stats_read ();
 841 #endif /* BITSET_STATS  */
 842 }
 843
 844
 845 /* Read bitset statistics file.  */
 846 static void
 847 bitset_stats_read ()
 848 {
 849   FILE *file;
 850
 851   if (!bitset_stats)
 852     return;
 853
 854   file = fopen (BITSET_STATS_FILE, "r");
 855   if (file)
 856     {
 857       if (fread (&bitset_stats_data, sizeof (bitset_stats_data),
 858                  1, file) != 1)
 859         {
 860           if (ferror (file))
 861             perror ("Could not read stats file.");
 862           else
 863             fprintf (stderr, "Bad stats file size.\n");
 864         }
 865       fclose (file);
 866     }
 867   bitset_stats_data.runs++;
 868 }
 869
 870
 871 /* Write bitset statistics file.  */
 872 static void
 873 bitset_stats_write ()
 874 {
 875   FILE *file;
 876
 877   if (!bitset_stats)
 878     return;
 879
 880   file = fopen (BITSET_STATS_FILE, "w");
 881   if (file)
 882     {
 883       if (fwrite (&bitset_stats_data, sizeof (bitset_stats_data),
 884                   1, file) != 1)
 885         perror ("Could not write stats file.");
 886       fclose (file);
 887     }
 888   else
 889     perror ("Could not open stats file for writing.");
 890 }
 891
 892
 893 /* Dump bitset statistics to FILE.  */
 894 void
 895 bitset_stats_dump (file)
 896      FILE *file;
 897 {
 898 #if BITSET_STATS
 899   bitset_stats_print (file, 0);
 900   bitset_stats_write ();
 901 #endif /* BITSET_STATS  */
 902 }
 903
 904
 905 /* Function to be called from debugger to print bitset stats.  */
 906 void
 907 debug_bitset_stats (void)
 908 {
 909 #if BITSET_STATS
 910   bitset_stats_print (stderr, 1);
 911 #endif /* BITSET_STATS  */
 912 }