[bison.git] / lib / bitset_stats.c

/* Bitset statistics.
   Copyright (C) 2002 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 "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)]++


typedef struct bitset_stats_struct
{
  bitset bset;
} *bitset_stats;


struct bitset_struct
{
  struct bbitset_struct b;
  struct bitset_stats_struct s;
};


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;
int bitset_stats_enabled = 0;


static void bitset_stats_set PARAMS ((bitset, bitset_bindex));
static void bitset_stats_reset PARAMS ((bitset, bitset_bindex));
static int bitset_stats_test PARAMS ((bitset, bitset_bindex));
static int bitset_stats_size PARAMS ((bitset));
static int bitset_stats_op1 PARAMS ((bitset, enum bitset_ops));
static int bitset_stats_op2 PARAMS ((bitset, bitset, enum bitset_ops));
static int bitset_stats_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
static int bitset_stats_op4 PARAMS ((bitset, bitset, bitset, bitset,
				     enum bitset_ops));
static int bitset_stats_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
				      bitset_bindex *));
static int bitset_stats_reverse_list
PARAMS ((bitset, bitset_bindex *, bitset_bindex, bitset_bindex *));
static void bitset_stats_free PARAMS ((bitset));
static void bitset_percent_histogram_print PARAMS ((FILE *, const char *,
						    const char *,
						    unsigned int,
						    unsigned int *));
static void bitset_log_histogram_print PARAMS ((FILE *, const char *,
						const char *,
						unsigned int,
						unsigned int *));
static void bitset_stats_print_1
PARAMS ((FILE *, const char *, struct bitset_type_info_struct *));
static void bitset_stats_print PARAMS ((FILE *, int));


/* Print a percentage histogram with message MSG to FILE.  */
static void
bitset_percent_histogram_print (file, name, msg, n_bins, bins)
     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%8d (%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 void
bitset_log_histogram_print (file, name, msg, n_bins, bins)
     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;
  unsigned int last_bin;

  total = 0;
  for (i = 0; i < n_bins; i++)
    total += bins[i];

  if (!total)
    return;

  for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
     continue;
  last_bin = i - 1;

  /* 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%8d (%5.1f%%)\n",
	     max_width, i, bins[i], 100.0 * bins[i] / total);

  for (; i <= last_bin; i++)
    fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n",
	     max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
	     1 << (i - 1), (1 << i) - 1, bins[i],
	     (100.0 * bins[i]) / total);
}


/* Print bitset statistics to FILE.  */
static void
bitset_stats_print_1 (file, name, stats)
     FILE *file;
     const char *name;
     struct bitset_type_info_struct *stats;
{
  if (!stats)
    return;
  
  fprintf (file, "%s:\n", name);
  fprintf (file, _("%d bitset_allocs, %d freed (%.2f%%).\n"),
	   stats->allocs, stats->frees,
	   stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
  fprintf (file, _("%d bitset_sets, %d cached (%.2f%%)\n"),
	   stats->sets, stats->cache_sets,
	   stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
  fprintf (file, _("%d bitset_resets, %d cached (%.2f%%)\n"),
	   stats->resets, stats->cache_resets,
	   stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
  fprintf (file, _("%d bitset_tests, %d cached (%.2f%%)\n"),
	   stats->tests, stats->cache_tests,
	   stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);

  fprintf (file, _("%d 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 void
bitset_stats_print (file, verbose)
     FILE *file;
     int verbose ATTRIBUTE_UNUSED;
{
  int i;
  static const char *names[] = BITSET_TYPE_NAMES;

  if (!bitset_stats_info)
    return;

  fprintf (file, _("Bitset statistics:\n\n"));

  if (bitset_stats_info->runs > 1)
    fprintf (file, _("Accumulated runs = %d\n"), bitset_stats_info->runs);

  for (i = 0; i < BITSET_TYPE_NUM; i++)
    bitset_stats_print_1 (file, names[i], &bitset_stats_info->types[i]);
}


/* Initialise bitset statistics logging.  */
void
bitset_stats_enable ()
{
  if (!bitset_stats_info)
    bitset_stats_info = &bitset_stats_info_data;
  bitset_stats_enabled = 1;
}


void
bitset_stats_disable ()
{
  bitset_stats_enabled = 0;
}


/* Read bitset statistics file.  */
void
bitset_stats_read (filename)
     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"));
	}
      fclose (file);
    }
  bitset_stats_info_data.runs++;
}


/* Write bitset statistics file.  */
void
bitset_stats_write (filename)
     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."));
      fclose (file);
    }
  else
    perror (_("Could not open stats file for writing."));
}


/* Dump bitset statistics to FILE.  */
void
bitset_stats_dump (file)
     FILE *file;
{
  bitset_stats_print (file, 0);
}


/* Function to be called from debugger to print bitset stats.  */
void
debug_bitset_stats (void)
{
  bitset_stats_print (stderr, 1);
}


static void
bitset_stats_set (dst, bitno)
     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 void
bitset_stats_reset (dst, bitno)
     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 int
bitset_stats_test (src, bitno)
     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);
  
  if (offset < bset->b.csize)
    {
      BITSET_STATS_CACHE_TESTS_INC (bset);
      return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
    }
  else
    return BITSET_TEST_ (bset, bitno);
}


static int
bitset_stats_size (src)
     bitset src;
{
  return BITSET_SIZE_ (src->s.bset);
}


static int
bitset_stats_op1 (dst, op)
     bitset dst;
     enum bitset_ops op;
{
  return BITSET_OP1_ (dst->s.bset, op);
}


static int
bitset_stats_op2 (dst, src, op)
     bitset dst;
     bitset src;
     enum bitset_ops op;
{
  BITSET_CHECK2_ (dst, src);
  return BITSET_OP2_ (dst->s.bset, src->s.bset, op);
}


static int
bitset_stats_op3 (dst, src1, src2, op)
     bitset dst;
     bitset src1;
     bitset src2;
     enum bitset_ops op;
{
  BITSET_CHECK3_ (dst, src1, src2);
  return BITSET_OP3_ (dst->s.bset, src1->s.bset, src2->s.bset, op);
}


static int
bitset_stats_op4 (dst, src1, src2, src3, op)
     bitset dst;
     bitset src1;
     bitset src2;
     bitset src3;
     enum bitset_ops op;
{
  BITSET_CHECK4_ (dst, src1, src2, src3);

  /* This is a bit of a hack.  If the implementation handles
     a four operand operation then vector to it, passing
     the enclosed bitsets.  Otherwise use the fallback 
     bitset_op4 routine.  */
  if (dst->s.bset->b.ops->op4 != bitset_op4)
     return BITSET_OP4_ (dst->s.bset, src1->s.bset, src2->s.bset,
			 src3->s.bset, op);

  return bitset_op4 (dst, src1, src2, src3, op);
}


static int
bitset_stats_list (bset, list, num, next)
     bitset bset;
     bitset_bindex *list;
     bitset_bindex num;
     bitset_bindex *next;
{
  bitset_bindex count;
  bitset_bindex tmp;
  bitset_bindex size;
  bitset_bindex i;
  enum bitset_type type;

  count = BITSET_LIST_ (bset->s.bset, list, num, next);
  
  type = BITSET_TYPE_ (bset->s.bset);
  BITSET_STATS_LISTS_INC (bset->s.bset);
  
  /* Log histogram of number of set bits.  */
  for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
     continue;
  if (i >= BITSET_LOG_COUNT_BINS)
     i = BITSET_LOG_COUNT_BINS - 1;
  BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i);
  
  /* Log histogram of number of bits in set.  */
  size = BITSET_SIZE_ (bset->s.bset);
  for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
     continue;
  if (i >= BITSET_LOG_SIZE_BINS)
     i = BITSET_LOG_SIZE_BINS - 1;
  BITSET_STATS_LIST_SIZES_INC (bset->s.bset, i);
  
  /* Histogram of fraction of bits set.  */
  i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
  if (i >= BITSET_DENSITY_BINS)
     i = BITSET_DENSITY_BINS - 1;
  BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i);
  return count;
}


static int
bitset_stats_reverse_list (bset, list, num, next)
     bitset bset;
     bitset_bindex *list;
     bitset_bindex num;
     bitset_bindex *next;
{
  return BITSET_REVERSE_LIST_ (bset->s.bset, list, num, next);
}


static void
bitset_stats_free (bset)
     bitset bset;
{
  BITSET_STATS_FREES_INC (bset->s.bset);
  BITSET_FREE_ (bset->s.bset);
}


struct bitset_ops_struct bitset_stats_ops = {
  bitset_stats_set,
  bitset_stats_reset,
  bitset_stats_test,
  bitset_stats_size,
  bitset_stats_op1,
  bitset_stats_op2,
  bitset_stats_op3,
  bitset_stats_op4,
  bitset_stats_list,
  bitset_stats_reverse_list,
  bitset_stats_free,
  BITSET_STATS
};


/* Return enclosed bitset type.  */
enum bitset_type
bitset_stats_type_get (bset)
   bitset bset;
{
   return BITSET_TYPE_ (bset->s.bset);
}


int bitset_stats_bytes (void)
{
  return sizeof (struct bitset_struct);
}


bitset
bitset_stats_init (bset, n_bits, type)
     bitset bset;
     bitset_bindex n_bits;
     enum bitset_type type;
{
  unsigned int bytes;
  bitset sbset;

  bset->b.ops = &bitset_stats_ops;

  /* Disable cache.  */
  bset->b.cindex = 0;
  bset->b.csize = 0;
  bset->b.cdata = 0;

  /* Set up the actual bitset implementation that
     we are a wrapper over.  */
  switch (type)
    {
    case BITSET_ARRAY:
      bytes = abitset_bytes (n_bits);
      sbset = (bitset) xcalloc (1, bytes);
      abitset_init (sbset, n_bits);
      break;

    case BITSET_LIST:
      bytes = lbitset_bytes (n_bits);
      sbset = (bitset) xcalloc (1, bytes);
      lbitset_init (sbset, n_bits);
      break;

    case BITSET_TABLE:
      bytes = ebitset_bytes (n_bits);
      sbset = (bitset) xcalloc (1, bytes);
      ebitset_init (sbset, n_bits);
      break;

    default:
      abort ();
    }

  bset->s.bset = sbset;

  BITSET_STATS_ALLOCS_INC (type);
  
  return bset;
}
Commit	Line	Data
613f5e1a AD	1	/* Bitset statistics.
	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
	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
	28	#ifdef HAVE_CONFIG_H
	29	#include "config.h"
	30	#endif
	31
	32	#include "bbitset.h"
	33	#include "abitset.h"
	34	#include "ebitset.h"
	35	#include "lbitset.h"
	36	#include "bitset_stats.h"
	37	#include <stdlib.h>
	38	#include <string.h>
	39	#include <stdio.h>
	40
c131cbff PE	41	#include "gettext.h"
c131cbff PE	42	#define _(Msgid) gettext (Msgid)
613f5e1a AD	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	typedef struct bitset_stats_struct
	79	{
	80	bitset bset;
	81	} *bitset_stats;
	82
	83
	84	struct bitset_struct
	85	{
	86	struct bbitset_struct b;
	87	struct bitset_stats_struct s;
	88	};
	89
	90
	91	struct bitset_type_info_struct
	92	{
	93	unsigned int allocs;
	94	unsigned int frees;
	95	unsigned int lists;
	96	unsigned int sets;
	97	unsigned int cache_sets;
	98	unsigned int resets;
	99	unsigned int cache_resets;
	100	unsigned int tests;
	101	unsigned int cache_tests;
	102	unsigned int list_counts[BITSET_LOG_COUNT_BINS];
	103	unsigned int list_sizes[BITSET_LOG_SIZE_BINS];
	104	unsigned int list_density[BITSET_DENSITY_BINS];
	105	};
	106
107	struct bitset_stats_info_struct
108	{
109	unsigned int runs;
110	struct bitset_type_info_struct types[BITSET_TYPE_NUM];
111	};
112
113
114	struct bitset_stats_info_struct bitset_stats_info_data;
115	struct bitset_stats_info_struct *bitset_stats_info;
116	int bitset_stats_enabled = 0;
117
118
119	static void bitset_stats_set PARAMS ((bitset, bitset_bindex));
120	static void bitset_stats_reset PARAMS ((bitset, bitset_bindex));
121	static int bitset_stats_test PARAMS ((bitset, bitset_bindex));
122	static int bitset_stats_size PARAMS ((bitset));
123	static int bitset_stats_op1 PARAMS ((bitset, enum bitset_ops));
124	static int bitset_stats_op2 PARAMS ((bitset, bitset, enum bitset_ops));
125	static int bitset_stats_op3 PARAMS ((bitset, bitset, bitset, enum bitset_ops));
126	static int bitset_stats_op4 PARAMS ((bitset, bitset, bitset, bitset,
127	enum bitset_ops));
128	static int bitset_stats_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
129	bitset_bindex *));
130	static int bitset_stats_reverse_list
131	PARAMS ((bitset, bitset_bindex , bitset_bindex, bitset_bindex ));
132	static void bitset_stats_free PARAMS ((bitset));
133	static void bitset_percent_histogram_print PARAMS ((FILE , const char ,
134	const char *,
135	unsigned int,
136	unsigned int *));
137	static void bitset_log_histogram_print PARAMS ((FILE , const char ,
138	const char *,
139	unsigned int,
140	unsigned int *));
141	static void bitset_stats_print_1
142	PARAMS ((FILE , const char , struct bitset_type_info_struct *));
143	static void bitset_stats_print PARAMS ((FILE *, int));
144
145
146	/* Print a percentage histogram with message MSG to FILE. */
147	static void
148	bitset_percent_histogram_print (file, name, msg, n_bins, bins)
149	FILE *file;
150	const char *name;
151	const char *msg;
152	unsigned int n_bins;
153	unsigned int *bins;
154	{
155	unsigned int i;
156	unsigned int total;
157
158	total = 0;
159	for (i = 0; i < n_bins; i++)
160	total += bins[i];
161
162	if (!total)
163	return;
164
165	fprintf (file, "%s %s", name, msg);
166	for (i = 0; i < n_bins; i++)
167	fprintf (file, "%.0f-%.0f%%\t%8d (%5.1f%%)\n",
168	i * 100.0 / n_bins,
169	(i + 1) * 100.0 / n_bins, bins[i],
170	(100.0 * bins[i]) / total);
171	}
172
173
174	/* Print a log histogram with message MSG to FILE. */
175	static void
176	bitset_log_histogram_print (file, name, msg, n_bins, bins)
177	FILE *file;
178	const char *name;
179	const char *msg;
180	unsigned int n_bins;
181	unsigned int *bins;
182	{
183	unsigned int i;
184	unsigned int total;
185	unsigned int max_width;
186	unsigned int last_bin;
187
188	total = 0;
189	for (i = 0; i < n_bins; i++)
190	total += bins[i];
191
192	if (!total)
193	return;
194
195	for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
196	continue;
197	last_bin = i - 1;
198
199	/* 2 * ceil (log10 (2) * (N - 1)) + 1. */
200	max_width = 2 * (unsigned int) (0.30103 * (n_bins - 1) + 0.9999) + 1;
201
202	fprintf (file, "%s %s", name, msg);
203	for (i = 0; i < 2; i++)
204	fprintf (file, "%*d\t%8d (%5.1f%%)\n",
205	max_width, i, bins[i], 100.0 * bins[i] / total);
206
207	for (; i <= last_bin; i++)
208	fprintf (file, "%*d-%d\t%8d (%5.1f%%)\n",
209	max_width - ((unsigned int) (0.30103 * (i) + 0.9999) + 1),
210	1 << (i - 1), (1 << i) - 1, bins[i],
211	(100.0 * bins[i]) / total);
212	}
213
214
215	/* Print bitset statistics to FILE. */
216	static void
217	bitset_stats_print_1 (file, name, stats)
218	FILE *file;
219	const char *name;
220	struct bitset_type_info_struct *stats;
221	{
222	if (!stats)
223	return;
224
225	fprintf (file, "%s:\n", name);
c131cbff	226	fprintf (file, _("%d bitset_allocs, %d freed (%.2f%%).\n"),
613f5e1a AD	227	stats->allocs, stats->frees,
613f5e1a AD	228	stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
c131cbff	229	fprintf (file, _("%d bitset_sets, %d cached (%.2f%%)\n"),
613f5e1a AD	230	stats->sets, stats->cache_sets,
613f5e1a AD	231	stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
c131cbff	232	fprintf (file, _("%d bitset_resets, %d cached (%.2f%%)\n"),
613f5e1a AD	233	stats->resets, stats->cache_resets,
613f5e1a AD	234	stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
c131cbff	235	fprintf (file, _("%d bitset_tests, %d cached (%.2f%%)\n"),
613f5e1a AD	236	stats->tests, stats->cache_tests,
	237	stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);
	238
c131cbff	239	fprintf (file, _("%d bitset_lists\n"), stats->lists);
613f5e1a	240
c131cbff	241	bitset_log_histogram_print (file, name, _("count log histogram\n"),
613f5e1a AD	242	BITSET_LOG_COUNT_BINS, stats->list_counts);
613f5e1a AD	243
c131cbff	244	bitset_log_histogram_print (file, name, _("size log histogram\n"),
613f5e1a AD	245	BITSET_LOG_SIZE_BINS, stats->list_sizes);
613f5e1a AD	246
c131cbff	247	bitset_percent_histogram_print (file, name, _("density histogram\n"),
613f5e1a AD	248	BITSET_DENSITY_BINS, stats->list_density);
	249	}
	250
	251
	252	/* Print all bitset statistics to FILE. */
	253	static void
	254	bitset_stats_print (file, verbose)
	255	FILE *file;
	256	int verbose ATTRIBUTE_UNUSED;
	257	{
	258	int i;
	259	static const char *names[] = BITSET_TYPE_NAMES;
	260
	261	if (!bitset_stats_info)
	262	return;
	263
c131cbff	264	fprintf (file, _("Bitset statistics:\n\n"));
613f5e1a AD	265
613f5e1a AD	266	if (bitset_stats_info->runs > 1)
c131cbff	267	fprintf (file, _("Accumulated runs = %d\n"), bitset_stats_info->runs);
613f5e1a AD	268
	269	for (i = 0; i < BITSET_TYPE_NUM; i++)
	270	bitset_stats_print_1 (file, names[i], &bitset_stats_info->types[i]);
	271	}
	272
	273
	274	/* Initialise bitset statistics logging. */
	275	void
	276	bitset_stats_enable ()
	277	{
	278	if (!bitset_stats_info)
	279	bitset_stats_info = &bitset_stats_info_data;
	280	bitset_stats_enabled = 1;
	281	}
	282
	283
	284	void
	285	bitset_stats_disable ()
	286	{
	287	bitset_stats_enabled = 0;
	288	}
	289
	290
	291	/* Read bitset statistics file. */
	292	void
	293	bitset_stats_read (filename)
	294	const char *filename;
	295	{
	296	FILE *file;
	297
	298	if (!bitset_stats_info)
	299	return;
	300
	301	if (!filename)
	302	filename = BITSET_STATS_FILE;
	303
	304	file = fopen (filename, "r");
	305	if (file)
	306	{
	307	if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
	308	1, file) != 1)
	309	{
	310	if (ferror (file))
c131cbff	311	perror (_("Could not read stats file."));
613f5e1a	312	else
c131cbff	313	fprintf (stderr, _("Bad stats file size.\n"));
613f5e1a AD	314	}
	315	fclose (file);
	316	}
	317	bitset_stats_info_data.runs++;
	318	}
	319
	320
	321	/* Write bitset statistics file. */
	322	void
	323	bitset_stats_write (filename)
	324	const char *filename;
	325	{
	326	FILE *file;
	327
	328	if (!bitset_stats_info)
	329	return;
	330
	331	if (!filename)
	332	filename = BITSET_STATS_FILE;
	333
	334	file = fopen (filename, "w");
	335	if (file)
	336	{
	337	if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
	338	1, file) != 1)
c131cbff	339	perror (_("Could not write stats file."));
613f5e1a AD	340	fclose (file);
	341	}
	342	else
c131cbff	343	perror (_("Could not open stats file for writing."));
613f5e1a AD	344	}
	345
	346
	347	/* Dump bitset statistics to FILE. */
	348	void
	349	bitset_stats_dump (file)
	350	FILE *file;
	351	{
	352	bitset_stats_print (file, 0);
	353	}
	354
	355
	356	/* Function to be called from debugger to print bitset stats. */
	357	void
	358	debug_bitset_stats (void)
	359	{
	360	bitset_stats_print (stderr, 1);
	361	}
	362
	363
	364	static void
	365	bitset_stats_set (dst, bitno)
	366	bitset dst;
	367	bitset_bindex bitno;
	368	{
	369	bitset bset = dst->s.bset;
c131cbff PE	370	bitset_windex wordno = bitno / BITSET_WORD_BITS;
c131cbff PE	371	bitset_windex offset = wordno - bset->b.cindex;
613f5e1a AD	372
	373	BITSET_STATS_SETS_INC (bset);
	374
	375	if (offset < bset->b.csize)
	376	{
c131cbff	377	bset->b.cdata[offset] \|= (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
613f5e1a AD	378	BITSET_STATS_CACHE_SETS_INC (bset);
	379	}
	380	else
	381	BITSET_SET_ (bset, bitno);
	382	}
	383
	384
	385	static void
	386	bitset_stats_reset (dst, bitno)
	387	bitset dst;
	388	bitset_bindex bitno;
	389	{
	390	bitset bset = dst->s.bset;
c131cbff PE	391	bitset_windex wordno = bitno / BITSET_WORD_BITS;
c131cbff PE	392	bitset_windex offset = wordno - bset->b.cindex;
613f5e1a AD	393
	394	BITSET_STATS_RESETS_INC (bset);
	395
	396	if (offset < bset->b.csize)
	397	{
c131cbff PE	398	bset->b.cdata[offset] &=
c131cbff PE	399	~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
613f5e1a AD	400	BITSET_STATS_CACHE_RESETS_INC (bset);
	401	}
	402	else
	403	BITSET_RESET_ (bset, bitno);
	404	}
	405
	406
	407	static int
	408	bitset_stats_test (src, bitno)
	409	bitset src;
	410	bitset_bindex bitno;
	411	{
	412	bitset bset = src->s.bset;
c131cbff PE	413	bitset_windex wordno = bitno / BITSET_WORD_BITS;
c131cbff PE	414	bitset_windex offset = wordno - bset->b.cindex;
613f5e1a AD	415
	416	BITSET_STATS_TESTS_INC (bset);
	417
	418	if (offset < bset->b.csize)
	419	{
	420	BITSET_STATS_CACHE_TESTS_INC (bset);
	421	return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
	422	}
	423	else
	424	return BITSET_TEST_ (bset, bitno);
	425	}
	426
	427
	428	static int
	429	bitset_stats_size (src)
	430	bitset src;
	431	{
	432	return BITSET_SIZE_ (src->s.bset);
	433	}
	434
	435
	436	static int
	437	bitset_stats_op1 (dst, op)
	438	bitset dst;
	439	enum bitset_ops op;
	440	{
	441	return BITSET_OP1_ (dst->s.bset, op);
	442	}
	443
	444
	445	static int
	446	bitset_stats_op2 (dst, src, op)
	447	bitset dst;
	448	bitset src;
	449	enum bitset_ops op;
	450	{
	451	BITSET_CHECK2_ (dst, src);
	452	return BITSET_OP2_ (dst->s.bset, src->s.bset, op);
	453	}
	454
	455
	456	static int
	457	bitset_stats_op3 (dst, src1, src2, op)
	458	bitset dst;
	459	bitset src1;
	460	bitset src2;
	461	enum bitset_ops op;
	462	{
	463	BITSET_CHECK3_ (dst, src1, src2);
	464	return BITSET_OP3_ (dst->s.bset, src1->s.bset, src2->s.bset, op);
	465	}
	466
	467
	468	static int
	469	bitset_stats_op4 (dst, src1, src2, src3, op)
	470	bitset dst;
	471	bitset src1;
	472	bitset src2;
	473	bitset src3;
	474	enum bitset_ops op;
	475	{
	476	BITSET_CHECK4_ (dst, src1, src2, src3);
	477
	478	/* This is a bit of a hack. If the implementation handles
479	a four operand operation then vector to it, passing
480	the enclosed bitsets. Otherwise use the fallback
481	bitset_op4 routine. */
482	if (dst->s.bset->b.ops->op4 != bitset_op4)
483	return BITSET_OP4_ (dst->s.bset, src1->s.bset, src2->s.bset,
484	src3->s.bset, op);
485
486	return bitset_op4 (dst, src1, src2, src3, op);
487	}
488
489
490	static int
491	bitset_stats_list (bset, list, num, next)
492	bitset bset;
493	bitset_bindex *list;
494	bitset_bindex num;
495	bitset_bindex *next;
496	{
497	bitset_bindex count;
498	bitset_bindex tmp;
499	bitset_bindex size;
500	bitset_bindex i;
501	enum bitset_type type;
502
503	count = BITSET_LIST_ (bset->s.bset, list, num, next);
504
505	type = BITSET_TYPE_ (bset->s.bset);
506	BITSET_STATS_LISTS_INC (bset->s.bset);
507
508	/* Log histogram of number of set bits. */
509	for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
510	continue;
511	if (i >= BITSET_LOG_COUNT_BINS)
512	i = BITSET_LOG_COUNT_BINS - 1;
513	BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i);
514
515	/* Log histogram of number of bits in set. */
516	size = BITSET_SIZE_ (bset->s.bset);
517	for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
518	continue;
519	if (i >= BITSET_LOG_SIZE_BINS)
520	i = BITSET_LOG_SIZE_BINS - 1;
521	BITSET_STATS_LIST_SIZES_INC (bset->s.bset, i);
522
523	/* Histogram of fraction of bits set. */
524	i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
525	if (i >= BITSET_DENSITY_BINS)
526	i = BITSET_DENSITY_BINS - 1;
527	BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i);
528	return count;
529	}
530
531
532	static int
533	bitset_stats_reverse_list (bset, list, num, next)
534	bitset bset;
535	bitset_bindex *list;
536	bitset_bindex num;
537	bitset_bindex *next;
538	{
539	return BITSET_REVERSE_LIST_ (bset->s.bset, list, num, next);
540	}
541
542
543	static void
544	bitset_stats_free (bset)
545	bitset bset;
546	{
547	BITSET_STATS_FREES_INC (bset->s.bset);
548	BITSET_FREE_ (bset->s.bset);
549	}
550
551
552	struct bitset_ops_struct bitset_stats_ops = {
553	bitset_stats_set,
554	bitset_stats_reset,
555	bitset_stats_test,
556	bitset_stats_size,
557	bitset_stats_op1,
558	bitset_stats_op2,
559	bitset_stats_op3,
560	bitset_stats_op4,
561	bitset_stats_list,
562	bitset_stats_reverse_list,
563	bitset_stats_free,
564	BITSET_STATS
565	};
566
567
568	/* Return enclosed bitset type. */
569	enum bitset_type
570	bitset_stats_type_get (bset)
571	bitset bset;
572	{
573	return BITSET_TYPE_ (bset->s.bset);
574	}
575
576
577	int bitset_stats_bytes (void)
578	{
579	return sizeof (struct bitset_struct);
580	}
581
582
583	bitset
584	bitset_stats_init (bset, n_bits, type)
585	bitset bset;
586	bitset_bindex n_bits;
587	enum bitset_type type;
588	{
589	unsigned int bytes;
590	bitset sbset;
591
592	bset->b.ops = &bitset_stats_ops;
593
594	/* Disable cache. */
595	bset->b.cindex = 0;
596	bset->b.csize = 0;
597	bset->b.cdata = 0;
598
599	/* Set up the actual bitset implementation that
600	we are a wrapper over. */
601	switch (type)
602	{
603	case BITSET_ARRAY:
604	bytes = abitset_bytes (n_bits);
605	sbset = (bitset) xcalloc (1, bytes);
606	abitset_init (sbset, n_bits);
607	break;
608
609	case BITSET_LIST:
610	bytes = lbitset_bytes (n_bits);
611	sbset = (bitset) xcalloc (1, bytes);
612	lbitset_init (sbset, n_bits);
613	break;
614
615	case BITSET_TABLE:
616	bytes = ebitset_bytes (n_bits);
617	sbset = (bitset) xcalloc (1, bytes);
618	ebitset_init (sbset, n_bits);
619	break;
620
621	default:
622	abort ();
623	}
624
625	bset->s.bset = sbset;
626
627	BITSET_STATS_ALLOCS_INC (type);
628
629	return bset;
630	}