/* Bitset statistics.   Copyright (C) 2002, 2003, 2004 Free Software Foundation, Inc.   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).   This program is free software; you can redistribute it and/or modify   it under the terms of the GNU General Public License as published by   the Free Software Foundation; either version 2 of the License, or   (at your option) any later version.   This program is distributed in the hope that it will be useful,   but WITHOUT ANY WARRANTY; without even the implied warranty of   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the   GNU General Public License for more details.   You should have received a copy of the GNU General Public License   along with this program; if not, write to the Free Software   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.*//* This file is a wrapper bitset implementation for the other bitset   implementations.  It provides bitset compatibility checking and   statistics gathering without having to instrument the bitset   implementations.  When statistics gathering is enabled, the bitset   operations get vectored through here and we then call the appropriate   routines.*/#ifdef HAVE_CONFIG_H#include "config.h"#endif#include "bbitset.h"#include "abitset.h"#include "ebitset.h"#include "lbitset.h"#include "vbitset.h"#include "bitset_stats.h"#include <stdlib.h>#include <string.h>#include <stdio.h>#include "gettext.h"#define _(Msgid)  gettext (Msgid)/* Configuration macros.  */#define BITSET_STATS_FILE "bitset.dat"#define BITSET_LOG_COUNT_BINS 10#define BITSET_LOG_SIZE_BINS  16#define BITSET_DENSITY_BINS  20/* Accessor macros.  */#define BITSET_STATS_ALLOCS_INC(TYPE)	 		\    bitset_stats_info->types[(TYPE)].allocs++#define BITSET_STATS_FREES_INC(BSET) 			\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++#define BITSET_STATS_SETS_INC(BSET) 			\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++#define BITSET_STATS_CACHE_SETS_INC(BSET) 		\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++#define BITSET_STATS_RESETS_INC(BSET) 			\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++#define BITSET_STATS_CACHE_RESETS_INC(BSET) 		\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++#define BITSET_STATS_TESTS_INC(BSET) 			\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++#define BITSET_STATS_CACHE_TESTS_INC(BSET) 		\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++#define BITSET_STATS_LISTS_INC(BSET) 			\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++#define BITSET_STATS_LIST_COUNTS_INC(BSET, I) 		\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++#define BITSET_STATS_LIST_SIZES_INC(BSET, I) 		\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++#define BITSET_STATS_LIST_DENSITY_INC(BSET, I) 		\    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++struct bitset_type_info_struct{  unsigned int allocs;  unsigned int frees;  unsigned int lists;  unsigned int sets;  unsigned int cache_sets;  unsigned int resets;  unsigned int cache_resets;  unsigned int tests;  unsigned int cache_tests;  unsigned int list_counts[BITSET_LOG_COUNT_BINS];  unsigned int list_sizes[BITSET_LOG_SIZE_BINS];  unsigned int list_density[BITSET_DENSITY_BINS];};struct bitset_stats_info_struct{  unsigned int runs;  struct bitset_type_info_struct types[BITSET_TYPE_NUM];};struct bitset_stats_info_struct bitset_stats_info_data;struct bitset_stats_info_struct *bitset_stats_info;bool bitset_stats_enabled = false;/* Print a percentage histogram with message MSG to FILE.  */static voidbitset_percent_histogram_print (FILE *file, const char *name, const char *msg,				unsigned int n_bins, unsigned int *bins){  unsigned int i;  unsigned int total;  total = 0;  for (i = 0; i < n_bins; i++)    total += bins[i];  if (!total)    return;  fprintf (file, "%s %s", name, msg);  for (i = 0; i < n_bins; i++)    fprintf (file, "%.0f-%.0f%%\t%8u (%5.1f%%)\n",	     i * 100.0 / n_bins,	     (i + 1) * 100.0 / n_bins, bins[i],	     (100.0 * bins[i]) / total);}/* Print a log histogram with message MSG to FILE.  */static voidbitset_log_histogram_print (FILE *file, const char *name, const char *msg,			    unsigned int n_bins, unsigned int *bins){  unsigned int i;  unsigned int total;  unsigned int max_width;  total = 0;  for (i = 0; i < n_bins; i++)    total += bins[i];  if (!total)    return;  /* Determine number of useful bins.  */  for (i = n_bins; i > 3 && ! bins[i - 1]; i--)     continue;  n_bins = i;  /* 2 * ceil (log10 (2) * (N - 1)) + 1.  */  max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;  fprintf (file, "%s %s", name, msg);  for (i = 0; i < 2; i++)    fprintf (file, "%*d\t%8u (%5.1f%%)\n",	     max_width, i, bins[i], 100.0 * bins[i] / total);  for (; i < n_bins; i++)    fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n",	     max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),	     1UL << (i - 1),	     (1UL << i) - 1,	     bins[i],	     (100.0 * bins[i]) / total);}/* Print bitset statistics to FILE.  */static voidbitset_stats_print_1 (FILE *file, const char *name,		      struct bitset_type_info_struct *stats){  if (!stats)    return;  fprintf (file, "%s:\n", name);  fprintf (file, _("%u bitset_allocs, %u freed (%.2f%%).\n"),	   stats->allocs, stats->frees,	   stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);  fprintf (file, _("%u bitset_sets, %u cached (%.2f%%)\n"),	   stats->sets, stats->cache_sets,	   stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);  fprintf (file, _("%u bitset_resets, %u cached (%.2f%%)\n"),	   stats->resets, stats->cache_resets,	   stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);  fprintf (file, _("%u bitset_tests, %u cached (%.2f%%)\n"),	   stats->tests, stats->cache_tests,	   stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);  fprintf (file, _("%u bitset_lists\n"), stats->lists);  bitset_log_histogram_print (file, name, _("count log histogram\n"),			      BITSET_LOG_COUNT_BINS, stats->list_counts);  bitset_log_histogram_print (file, name, _("size log histogram\n"),			      BITSET_LOG_SIZE_BINS, stats->list_sizes);  bitset_percent_histogram_print (file, name, _("density histogram\n"),				  BITSET_DENSITY_BINS, stats->list_density);}/* Print all bitset statistics to FILE.  */static voidbitset_stats_print (FILE *file, bool verbose ATTRIBUTE_UNUSED){  int i;  if (!bitset_stats_info)    return;  fprintf (file, _("Bitset statistics:\n\n"));  if (bitset_stats_info->runs > 1)    fprintf (file, _("Accumulated runs = %u\n"), bitset_stats_info->runs);  for (i = 0; i < BITSET_TYPE_NUM; i++)    bitset_stats_print_1 (file, bitset_type_names[i],			  &bitset_stats_info->types[i]);}/* Initialise bitset statistics logging.  */voidbitset_stats_enable (void){  if (!bitset_stats_info)    bitset_stats_info = &bitset_stats_info_data;  bitset_stats_enabled = true;}voidbitset_stats_disable (void){  bitset_stats_enabled = false;}/* Read bitset statistics file.  */voidbitset_stats_read (const char *filename){  FILE *file;  if (!bitset_stats_info)    return;  if (!filename)    filename = BITSET_STATS_FILE;  file = fopen (filename, "r");  if (file)    {      if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data),		 1, file) != 1)	{	  if (ferror (file))	    perror (_("Could not read stats file."));	  else	    fprintf (stderr, _("Bad stats file size.\n"));	}      if (fclose (file) != 0)	perror (_("Could not read stats file."));    }  bitset_stats_info_data.runs++;}/* Write bitset statistics file.  */voidbitset_stats_write (const char *filename){  FILE *file;  if (!bitset_stats_info)    return;  if (!filename)    filename = BITSET_STATS_FILE;  file = fopen (filename, "w");  if (file)    {      if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data),		  1, file) != 1)	perror (_("Could not write stats file."));      if (fclose (file) != 0)	perror (_("Could not write stats file."));    }  else    perror (_("Could not open stats file for writing."));}/* Dump bitset statistics to FILE.  */voidbitset_stats_dump (FILE *file){  bitset_stats_print (file, false);}/* Function to be called from debugger to print bitset stats.  */voiddebug_bitset_stats (void){  bitset_stats_print (stderr, true);}static voidbitset_stats_set (bitset dst, bitset_bindex bitno){  bitset bset = dst->s.bset;  bitset_windex wordno = bitno / BITSET_WORD_BITS;  bitset_windex offset = wordno - bset->b.cindex;  BITSET_STATS_SETS_INC (bset);  if (offset < bset->b.csize)    {      bset->b.cdata[offset] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS);      BITSET_STATS_CACHE_SETS_INC (bset);    }  else    BITSET_SET_ (bset, bitno);}static voidbitset_stats_reset (bitset dst, bitset_bindex bitno){  bitset bset = dst->s.bset;  bitset_windex wordno = bitno / BITSET_WORD_BITS;  bitset_windex offset = wordno - bset->b.cindex;  BITSET_STATS_RESETS_INC (bset);  if (offset < bset->b.csize)    {      bset->b.cdata[offset] &=	~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));      BITSET_STATS_CACHE_RESETS_INC (bset);    }  else    BITSET_RESET_ (bset, bitno);}static boolbitset_stats_toggle (bitset src, bitset_bindex bitno){    return BITSET_TOGGLE_ (src->s.bset, bitno);}static boolbitset_stats_test (bitset src, bitset_bindex bitno){  bitset bset = src->s.bset;  bitset_windex wordno = bitno / BITSET_WORD_BITS;  bitset_windex offset = wordno - bset->b.cindex;  BITSET_STATS_TESTS_INC (bset);