1/* Bitset statistics.
2   Copyright (C) 2002, 2003, 2004, 2005, 2006 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 Foundation,
17   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
18
19/* This file is a wrapper bitset implementation for the other bitset
20   implementations.  It provides bitset compatibility checking and
21   statistics gathering without having to instrument the bitset
22   implementations.  When statistics gathering is enabled, the bitset
23   operations get vectored through here and we then call the appropriate
24   routines.  */
25
26#ifdef HAVE_CONFIG_H
27# include <config.h>
28#endif
29
30#include "bbitset.h"
31#include "abitset.h"
32#include "ebitset.h"
33#include "lbitset.h"
34#include "vbitset.h"
35#include "bitset_stats.h"
36#include <stdlib.h>
37#include <string.h>
38#include <stdio.h>
39
40#include "gettext.h"
41#define _(Msgid)  gettext (Msgid)
42
43/* Configuration macros.  */
44#define BITSET_STATS_FILE "bitset.dat"
45#define BITSET_LOG_COUNT_BINS 10
46#define BITSET_LOG_SIZE_BINS  16
47#define BITSET_DENSITY_BINS  20
48
49
50/* Accessor macros.  */
51#define BITSET_STATS_ALLOCS_INC(TYPE)			\
52    bitset_stats_info->types[(TYPE)].allocs++
53#define BITSET_STATS_FREES_INC(BSET)			\
54    bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++
55#define BITSET_STATS_SETS_INC(BSET)			\
56    bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++
57#define BITSET_STATS_CACHE_SETS_INC(BSET)		\
58    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++
59#define BITSET_STATS_RESETS_INC(BSET)			\
60    bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++
61#define BITSET_STATS_CACHE_RESETS_INC(BSET)		\
62    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++
63#define BITSET_STATS_TESTS_INC(BSET)			\
64    bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++
65#define BITSET_STATS_CACHE_TESTS_INC(BSET)		\
66    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++
67#define BITSET_STATS_LISTS_INC(BSET)			\
68    bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++
69#define BITSET_STATS_LIST_COUNTS_INC(BSET, I)		\
70    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++
71#define BITSET_STATS_LIST_SIZES_INC(BSET, I)		\
72    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++
73#define BITSET_STATS_LIST_DENSITY_INC(BSET, I)		\
74    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++
75
76
77struct bitset_type_info_struct
78{
79  unsigned int allocs;
80  unsigned int frees;
81  unsigned int lists;
82  unsigned int sets;
83  unsigned int cache_sets;
84  unsigned int resets;
85  unsigned int cache_resets;
86  unsigned int tests;
87  unsigned int cache_tests;
88  unsigned int list_counts[BITSET_LOG_COUNT_BINS];
89  unsigned int list_sizes[BITSET_LOG_SIZE_BINS];
90  unsigned int list_density[BITSET_DENSITY_BINS];
91};
92
93struct bitset_stats_info_struct
94{
95  unsigned int runs;
96  struct bitset_type_info_struct types[BITSET_TYPE_NUM];
97};
98
99
100struct bitset_stats_info_struct bitset_stats_info_data;
101struct bitset_stats_info_struct *bitset_stats_info;
102bool bitset_stats_enabled = false;
103
104
105/* Print a percentage histogram with message MSG to FILE.  */
106static void
107bitset_percent_histogram_print (FILE *file, const char *name, const char *msg,
108				unsigned int n_bins, unsigned int *bins)
109{
110  unsigned int i;
111  unsigned int total;
112
113  total = 0;
114  for (i = 0; i < n_bins; i++)
115    total += bins[i];
116
117  if (!total)
118    return;
119
120  fprintf (file, "%s %s", name, msg);
121  for (i = 0; i < n_bins; i++)
122    fprintf (file, "%.0f-%.0f%%\t%8u (%5.1f%%)\n",
123	     i * 100.0 / n_bins,
124	     (i + 1) * 100.0 / n_bins, bins[i],
125	     (100.0 * bins[i]) / total);
126}
127
128
129/* Print a log histogram with message MSG to FILE.  */
130static void
131bitset_log_histogram_print (FILE *file, const char *name, const char *msg,
132			    unsigned int n_bins, unsigned int *bins)
133{
134  unsigned int i;
135  unsigned int total;
136  unsigned int max_width;
137
138  total = 0;
139  for (i = 0; i < n_bins; i++)
140    total += bins[i];
141
142  if (!total)
143    return;
144
145  /* Determine number of useful bins.  */
146  for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
147     continue;
148  n_bins = i;
149
150  /* 2 * ceil (log10 (2) * (N - 1)) + 1.  */
151  max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;
152
153  fprintf (file, "%s %s", name, msg);
154  for (i = 0; i < 2; i++)
155    fprintf (file, "%*d\t%8u (%5.1f%%)\n",
156	     max_width, i, bins[i], 100.0 * bins[i] / total);
157
158  for (; i < n_bins; i++)
159    fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n",
160	     max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
161	     1UL << (i - 1),
162	     (1UL << i) - 1,
163	     bins[i],
164	     (100.0 * bins[i]) / total);
165}
166
167
168/* Print bitset statistics to FILE.  */
169static void
170bitset_stats_print_1 (FILE *file, const char *name,
171		      struct bitset_type_info_struct *stats)
172{
173  if (!stats)
174    return;
175
176  fprintf (file, "%s:\n", name);
177  fprintf (file, _("%u bitset_allocs, %u freed (%.2f%%).\n"),
178	   stats->allocs, stats->frees,
179	   stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
180  fprintf (file, _("%u bitset_sets, %u cached (%.2f%%)\n"),
181	   stats->sets, stats->cache_sets,
182	   stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
183  fprintf (file, _("%u bitset_resets, %u cached (%.2f%%)\n"),
184	   stats->resets, stats->cache_resets,
185	   stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
186  fprintf (file, _("%u bitset_tests, %u cached (%.2f%%)\n"),
187	   stats->tests, stats->cache_tests,
188	   stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);
189
190  fprintf (file, _("%u bitset_lists\n"), stats->lists);
191
192  bitset_log_histogram_print (file, name, _("count log histogram\n"),
193			      BITSET_LOG_COUNT_BINS, stats->list_counts);
194
195  bitset_log_histogram_print (file, name, _("size log histogram\n"),
196			      BITSET_LOG_SIZE_BINS, stats->list_sizes);
197
198  bitset_percent_histogram_print (file, name, _("density histogram\n"),
199				  BITSET_DENSITY_BINS, stats->list_density);
200}
201
202
203/* Print all bitset statistics to FILE.  */
204static void
205bitset_stats_print (FILE *file, bool verbose ATTRIBUTE_UNUSED)
206{
207  int i;
208
209  if (!bitset_stats_info)
210    return;
211
212  fprintf (file, _("Bitset statistics:\n\n"));
213
214  if (bitset_stats_info->runs > 1)
215    fprintf (file, _("Accumulated runs = %u\n"), bitset_stats_info->runs);
216
217  for (i = 0; i < BITSET_TYPE_NUM; i++)
218    bitset_stats_print_1 (file, bitset_type_names[i],
219			  &bitset_stats_info->types[i]);
220}
221
222
223/* Initialise bitset statistics logging.  */
224void
225bitset_stats_enable (void)
226{
227  if (!bitset_stats_info)
228    bitset_stats_info = &bitset_stats_info_data;
229  bitset_stats_enabled = true;
230}
231
232
233void
234bitset_stats_disable (void)
235{
236  bitset_stats_enabled = false;
237}
238
239
240/* Read bitset statistics file.  */
241void
242bitset_stats_read (const char *file_name)
243{
244  FILE *file;
245
246  if (!bitset_stats_info)
247    return;
248
249  if (!file_name)
250    file_name = BITSET_STATS_FILE;
251
252  file = fopen (file_name, "r");
253  if (file)
254    {
255      if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
256		 1, file) != 1)
257	{
258	  if (ferror (file))
259	    perror (_("Could not read stats file."));
260	  else
261	    fprintf (stderr, _("Bad stats file size.\n"));
262	}
263      if (fclose (file) != 0)
264	perror (_("Could not read stats file."));
265    }
266  bitset_stats_info_data.runs++;
267}
268
269
270/* Write bitset statistics file.  */
271void
272bitset_stats_write (const char *file_name)
273{
274  FILE *file;
275
276  if (!bitset_stats_info)
277    return;
278
279  if (!file_name)
280    file_name = BITSET_STATS_FILE;
281
282  file = fopen (file_name, "w");
283  if (file)
284    {
285      if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
286		  1, file) != 1)
287	perror (_("Could not write stats file."));
288      if (fclose (file) != 0)
289	perror (_("Could not write stats file."));
290    }
291  else
292    perror (_("Could not open stats file for writing."));
293}
294
295
296/* Dump bitset statistics to FILE.  */
297void
298bitset_stats_dump (FILE *file)
299{
300  bitset_stats_print (file, false);
301}
302
303
304/* Function to be called from debugger to print bitset stats.  */
305void
306debug_bitset_stats (void)
307{
308  bitset_stats_print (stderr, true);
309}
310
311
312static void
313bitset_stats_set (bitset dst, bitset_bindex bitno)
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
331static void
332bitset_stats_reset (bitset dst, bitset_bindex bitno)
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
351static bool
352bitset_stats_toggle (bitset src, bitset_bindex bitno)
353{
354    return BITSET_TOGGLE_ (src->s.bset, bitno);
355}
356
357
358static bool
359bitset_stats_test (bitset src, bitset_bindex bitno)
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
377static bitset_bindex
378bitset_stats_resize (bitset src, bitset_bindex size)
379{
380    return BITSET_RESIZE_ (src->s.bset, size);
381}
382
383
384static bitset_bindex
385bitset_stats_size (bitset src)
386{
387  return BITSET_SIZE_ (src->s.bset);
388}
389
390
391static bitset_bindex
392bitset_stats_count (bitset src)
393{
394  return BITSET_COUNT_ (src->s.bset);
395}
396
397
398static bool
399bitset_stats_empty_p (bitset dst)
400{
401  return BITSET_EMPTY_P_ (dst->s.bset);
402}
403
404
405static void
406bitset_stats_ones (bitset dst)
407{
408  BITSET_ONES_ (dst->s.bset);
409}
410
411
412static void
413bitset_stats_zero (bitset dst)
414{
415  BITSET_ZERO_ (dst->s.bset);
416}
417
418
419static void
420bitset_stats_copy (bitset dst, bitset src)
421{
422  BITSET_CHECK2_ (dst, src);
423  BITSET_COPY_ (dst->s.bset, src->s.bset);
424}
425
426
427static bool
428bitset_stats_disjoint_p (bitset dst, bitset src)
429{
430  BITSET_CHECK2_ (dst, src);
431  return BITSET_DISJOINT_P_ (dst->s.bset, src->s.bset);
432}
433
434
435static bool
436bitset_stats_equal_p (bitset dst, bitset src)
437{
438  BITSET_CHECK2_ (dst, src);
439  return BITSET_EQUAL_P_ (dst->s.bset, src->s.bset);
440}
441
442
443static void
444bitset_stats_not (bitset dst, bitset src)
445{
446  BITSET_CHECK2_ (dst, src);
447  BITSET_NOT_ (dst->s.bset, src->s.bset);
448}
449
450
451static bool
452bitset_stats_subset_p (bitset dst, bitset src)
453{
454  BITSET_CHECK2_ (dst, src);
455  return BITSET_SUBSET_P_ (dst->s.bset, src->s.bset);
456}
457
458
459static void
460bitset_stats_and (bitset dst, bitset src1, bitset src2)
461{
462  BITSET_CHECK3_ (dst, src1, src2);
463  BITSET_AND_ (dst->s.bset, src1->s.bset, src2->s.bset);
464}
465
466
467static bool
468bitset_stats_and_cmp (bitset dst, bitset src1, bitset src2)
469{
470  BITSET_CHECK3_ (dst, src1, src2);
471  return BITSET_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
472}
473
474
475static void
476bitset_stats_andn (bitset dst, bitset src1, bitset src2)
477{
478  BITSET_CHECK3_ (dst, src1, src2);
479  BITSET_ANDN_ (dst->s.bset, src1->s.bset, src2->s.bset);
480}
481
482
483static bool
484bitset_stats_andn_cmp (bitset dst, bitset src1, bitset src2)
485{
486  BITSET_CHECK3_ (dst, src1, src2);
487  return BITSET_ANDN_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
488}
489
490
491static void
492bitset_stats_or (bitset dst, bitset src1, bitset src2)
493{
494  BITSET_CHECK3_ (dst, src1, src2);
495  BITSET_OR_ (dst->s.bset, src1->s.bset, src2->s.bset);
496}
497
498
499static bool
500bitset_stats_or_cmp (bitset dst, bitset src1, bitset src2)
501{
502  BITSET_CHECK3_ (dst, src1, src2);
503  return BITSET_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
504}
505
506
507static void
508bitset_stats_xor (bitset dst, bitset src1, bitset src2)
509{
510  BITSET_CHECK3_ (dst, src1, src2);
511  BITSET_XOR_ (dst->s.bset, src1->s.bset, src2->s.bset);
512}
513
514
515static bool
516bitset_stats_xor_cmp (bitset dst, bitset src1, bitset src2)
517{
518  BITSET_CHECK3_ (dst, src1, src2);
519  return BITSET_XOR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
520}
521
522
523static void
524bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
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
531static bool
532bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
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
539static void
540bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
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
547static bool
548bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
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
555static void
556bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
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
563static bool
564bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
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
571static bitset_bindex
572bitset_stats_list (bitset bset, bitset_bindex *list,
573		   bitset_bindex num, bitset_bindex *next)
574{
575  bitset_bindex count;
576  bitset_bindex tmp;
577  bitset_bindex size;
578  bitset_bindex i;
579  enum bitset_type type;
580
581  count = BITSET_LIST_ (bset->s.bset, list, num, next);
582
583  type = BITSET_TYPE_ (bset->s.bset);
584  BITSET_STATS_LISTS_INC (bset->s.bset);
585
586  /* Log histogram of number of set bits.  */
587  for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
588     continue;
589  if (i >= BITSET_LOG_COUNT_BINS)
590     i = BITSET_LOG_COUNT_BINS - 1;
591  BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i);
592
593  /* Log histogram of number of bits in set.  */
594  size = BITSET_SIZE_ (bset->s.bset);
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  /* Histogram of fraction of bits set.  */
602  i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
603  if (i >= BITSET_DENSITY_BINS)
604     i = BITSET_DENSITY_BINS - 1;
605  BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i);
606  return count;
607}
608
609
610static bitset_bindex
611bitset_stats_list_reverse (bitset bset, bitset_bindex *list,
612			   bitset_bindex num, bitset_bindex *next)
613{
614  return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next);
615}
616
617
618static void
619bitset_stats_free (bitset bset)
620{
621  BITSET_STATS_FREES_INC (bset->s.bset);
622  BITSET_FREE_ (bset->s.bset);
623}
624
625
626struct bitset_vtable bitset_stats_vtable = {
627  bitset_stats_set,
628  bitset_stats_reset,
629  bitset_stats_toggle,
630  bitset_stats_test,
631  bitset_stats_resize,
632  bitset_stats_size,
633  bitset_stats_count,
634  bitset_stats_empty_p,
635  bitset_stats_ones,
636  bitset_stats_zero,
637  bitset_stats_copy,
638  bitset_stats_disjoint_p,
639  bitset_stats_equal_p,
640  bitset_stats_not,
641  bitset_stats_subset_p,
642  bitset_stats_and,
643  bitset_stats_and_cmp,
644  bitset_stats_andn,
645  bitset_stats_andn_cmp,
646  bitset_stats_or,
647  bitset_stats_or_cmp,
648  bitset_stats_xor,
649  bitset_stats_xor_cmp,
650  bitset_stats_and_or,
651  bitset_stats_and_or_cmp,
652  bitset_stats_andn_or,
653  bitset_stats_andn_or_cmp,
654  bitset_stats_or_and,
655  bitset_stats_or_and_cmp,
656  bitset_stats_list,
657  bitset_stats_list_reverse,
658  bitset_stats_free,
659  BITSET_STATS
660};
661
662
663/* Return enclosed bitset type.  */
664enum bitset_type
665bitset_stats_type_get (bitset bset)
666{
667   return BITSET_TYPE_ (bset->s.bset);
668}
669
670
671size_t
672bitset_stats_bytes (void)
673{
674  return sizeof (struct bitset_stats_struct);
675}
676
677
678bitset
679bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
680{
681  size_t bytes;
682  bitset sbset;
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      bytes = abitset_bytes (n_bits);
702      sbset = xcalloc (1, bytes);
703      abitset_init (sbset, n_bits);
704      break;
705
706    case BITSET_LIST:
707      bytes = lbitset_bytes (n_bits);
708      sbset = xcalloc (1, bytes);
709      lbitset_init (sbset, n_bits);
710      break;
711
712    case BITSET_TABLE:
713      bytes = ebitset_bytes (n_bits);
714      sbset = xcalloc (1, bytes);
715      ebitset_init (sbset, n_bits);
716      break;
717
718    case BITSET_VARRAY:
719      bytes = vbitset_bytes (n_bits);
720      sbset = xcalloc (1, bytes);
721      vbitset_init (sbset, n_bits);
722      break;
723    }
724
725  bset->s.bset = sbset;
726
727  BITSET_STATS_ALLOCS_INC (type);
728
729  return bset;
730}
731