root/maint/gnulib/lib/bitset/stats.c

/* [previous][next][first][last][top][bottom][index][help] */

DEFINITIONS

This source file includes following definitions.
  1. bitset_percent_histogram_print
  2. bitset_log_histogram_print
  3. bitset_stats_print_1
  4. bitset_stats_print
  5. bitset_stats_enable
  6. bitset_stats_disable
  7. bitset_stats_read
  8. bitset_stats_write
  9. bitset_stats_dump
  10. debug_bitset_stats
  11. bitset_stats_set
  12. bitset_stats_reset
  13. bitset_stats_toggle
  14. bitset_stats_test
  15. bitset_stats_resize
  16. bitset_stats_size
  17. bitset_stats_count
  18. bitset_stats_empty_p
  19. bitset_stats_ones
  20. bitset_stats_zero
  21. bitset_stats_copy
  22. bitset_stats_disjoint_p
  23. bitset_stats_equal_p
  24. bitset_stats_not
  25. bitset_stats_subset_p
  26. bitset_stats_and
  27. bitset_stats_and_cmp
  28. bitset_stats_andn
  29. bitset_stats_andn_cmp
  30. bitset_stats_or
  31. bitset_stats_or_cmp
  32. bitset_stats_xor
  33. bitset_stats_xor_cmp
  34. bitset_stats_and_or
  35. bitset_stats_and_or_cmp
  36. bitset_stats_andn_or
  37. bitset_stats_andn_or_cmp
  38. bitset_stats_or_and
  39. bitset_stats_or_and_cmp
  40. bitset_stats_list
  41. bitset_stats_list_reverse
  42. bitset_stats_free
  43. bitset_stats_type_get
  44. bitset_stats_bytes
  45. bitset_stats_init

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

/* [previous][next][first][last][top][bottom][index][help] */