2 Copyright (C) 2002 Free Software Foundation, Inc.
3 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
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.
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.
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. */
27 static void bitset_print
PARAMS ((FILE *, bitset
, int));
30 #define BITSET__CHECK2(DST, SRC) \
31 if ((DST)->OPS != (SRC)->OPS) abort ();
33 #define BITSET__CHECK3(DST, SRC1, SRC2) \
34 if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS) abort ();
36 #define BITSET__CHECK4(DST, SRC1, SRC2) \
37 if ((DST)->OPS != (SRC1)->OPS || (DST)->OPS != (SRC2)->OPS \
38 || (DST)->OPS != (SRC3)->OPS) abort ();
40 #define BITSET__CHECK2(DST, SRC)
42 #define BITSET__CHECK3(DST, SRC1, SRC2)
44 #define BITSET__CHECK4(DST, SRC1, SRC2, SRC3)
48 #define BITSET_STATS_FILE "bitset.dat"
50 #define BITSET_LOG_COUNT_BINS 10
51 #define BITSET_LOG_SIZE_BINS 16
52 #define BITSET_DENSITY_BINS 20
54 struct bitset_type_stats_struct
56 unsigned int xmallocs
;
58 unsigned int oballocs
;
61 unsigned int list_counts
[BITSET_LOG_COUNT_BINS
];
62 unsigned int list_sizes
[BITSET_LOG_SIZE_BINS
];
63 unsigned int list_density
[BITSET_DENSITY_BINS
];
66 struct bitset_stats_struct
69 struct bitset_type_stats_struct types
[BITSET_TYPE_NUM
];
72 struct bitset_stats_struct bitset_stats_data
;
73 struct bitset_stats_struct
*bitset_stats
;
75 static void bitset_percent_histogram_print
PARAMS ((FILE *, const char *,
79 static void bitset_log_histogram_print
PARAMS ((FILE *, const char *,
81 unsigned int, unsigned int *));
82 static void bitset_stats_print_1
PARAMS ((FILE *, const char *,
83 struct bitset_type_stats_struct
*));
84 static void bitset_stats_print
PARAMS ((FILE *, int));
85 static void bitset_stats_read
PARAMS ((void));
86 static void bitset_stats_write
PARAMS ((void));
88 #define BITSET_STATS_XMALLOCS_INC(TYPE) \
90 bitset_stats->types[(TYPE)].xmallocs++
92 #define BITSET_STATS_XFREES_INC(BSET) \
94 bitset_stats->types[(BSET)->ops->type].xfrees++
96 #define BITSET_STATS_OBALLOCS_INC(TYPE) \
98 bitset_stats->types[(TYPE)].oballocs++
100 #define BITSET_STATS_OBFREES_INC(BSET) \
102 bitset_stats->types[(BSET)->ops->type].obfrees++
104 #define BITSET_STATS_LISTS_INC(BSET) \
106 bitset_stats->types[(BSET)->ops->type].lists++
108 #define BITSET_STATS_LIST_COUNTS_INC(BSET, I) \
110 bitset_stats->types[(BSET)->ops->type].list_counts[(I)]++
112 #define BITSET_STATS_LIST_SIZES_INC(BSET, I) \
114 bitset_stats->types[(BSET)->ops->type].list_sizes[(I)]++
116 #define BITSET_STATS_LIST_DENSITY_INC(BSET, I) \
118 bitset_stats->types[(BSET)->ops->type].list_density[(I)]++
121 #define BITSET_STATS_XMALLOCS_INC(TYPE)
123 #define BITSET_STATS_XFREES_INC(BSET)
125 #define BITSET_STATS_OBALLOCS_INC(TYPE)
127 #define BITSET_STATS_OBFREES_INC(BSET)
129 #define BITSET_STATS_LISTS_INC(BSET)
131 #define BITSET_STATS_LIST_COUNTS_INC(BSET, I)
133 #define BITSET_STATS_LIST_SIZES_INC(BSET, I)
135 #define BITSET_STATS_LIST_DENSITY_INC(BSET, I)
136 #endif /* BITSET_STATS */
140 /* Return number of bytes required to create a N_BIT bitset
141 of TYPE. The bitset may grow to require more bytes than this. */
143 bitset_bytes (type
, n_bits
)
144 enum bitset_type type
;
145 bitset_bindex n_bits
;
152 bytes
= sbitset_bytes (n_bits
);
156 bytes
= lbitset_bytes (n_bits
);
160 bytes
= ebitset_bytes (n_bits
);
171 /* Initialise bitset BSET of TYPE for N_BITS. */
173 bitset_init (bset
, n_bits
, type
)
175 bitset_bindex n_bits
;
176 enum bitset_type type
;
181 return sbitset_init (bset
, n_bits
);
184 return lbitset_init (bset
, n_bits
);
187 return ebitset_init (bset
, n_bits
);
195 /* Select a bitset type for a set of N_BITS and with attribute hints
196 specified by ATTR. For variable size bitsets, N_BITS is only a
197 hint and may be zero. */
199 bitset_type_choose (n_bits
, attr
)
200 bitset_bindex n_bits ATTRIBUTE_UNUSED
;
203 enum bitset_type type
;
205 #ifdef ENABLE_CHECKING
206 /* Check attributes. */
207 if (attr
& BITSET_FIXED
&& attr
& BITSET_VARIABLE
)
209 if (attr
& BITSET_SPARSE
&& attr
& BITSET_DENSE
)
212 /* Note that sometimes we will be asked for a zero length
213 fixed size bitset. */
216 /* Choose the type of bitset. */
219 /* Currently, the simple bitsets do not support a variable size. */
220 if (attr
& BITSET_VARIABLE
|| attr
& BITSET_SPARSE
)
223 if (attr
& BITSET_DENSE
|| attr
& BITSET_GREEDY
)
231 /* Create a bitset of N_BITS of type TYPE. */
233 bitset_alloc (n_bits
, type
)
234 bitset_bindex n_bits
;
235 enum bitset_type type
;
240 BITSET_STATS_XMALLOCS_INC (type
);
242 bytes
= bitset_bytes (type
, n_bits
);
244 bset
= (bitset
) xmalloc (bytes
);
246 return bitset_init (bset
, n_bits
, type
);
250 /* Create a bitset of N_BITS of type TYPE. */
252 bitset_obstack_alloc (bobstack
, n_bits
, type
)
253 struct obstack
*bobstack
;
254 bitset_bindex n_bits
;
255 enum bitset_type type
;
259 BITSET_STATS_OBALLOCS_INC (type
);
261 bytes
= bitset_bytes (type
, n_bits
);
263 return bitset_init (obstack_alloc (bobstack
, bytes
), n_bits
, type
);
267 /* Create a bitset of N_BITS and with attribute hints specified by
270 bitset_create (n_bits
, attr
)
271 bitset_bindex n_bits
;
274 enum bitset_type type
;
276 type
= bitset_type_choose (n_bits
, attr
);
278 return bitset_alloc (n_bits
, type
);
282 /* Free bitset BSET. */
287 BITSET_STATS_XFREES_INC (bset
);
297 /* Free bitset BSET allocated on obstack. */
299 bitset_obstack_free (bset
)
302 BITSET_STATS_OBFREES_INC (bset
);
310 /* Find next bit set in SRC starting from and including BITNO.
311 Return -1 if SRC empty. */
313 bitset_next (src
, bitno
)
318 bitset_bindex next
= bitno
;
320 if (!bitset_list (src
, &val
, 1, &next
))
326 /* Find previous bit set in SRC starting from and including BITNO.
327 Return -1 if SRC empty. */
329 bitset_prev (src
, bitno
)
334 bitset_bindex next
= bitno
;
336 if (!bitset_reverse_list (src
, &val
, 1, &next
))
342 /* Find first set bit. */
347 return bitset_next (src
, 0);
351 /* Find last set bit. */
356 return bitset_prev (src
, 0);
361 bitset_print (file
, bset
, verbose
)
369 fprintf (file
, "n_bits = %d, set = {", bitset_size (bset
));
372 BITSET_EXECUTE (bset
, 0, i
,
376 fprintf (file
, "\n");
380 fprintf (file
, "%d ", i
);
381 pos
+= 1 + (i
>= 10) + (i
>= 100);
385 fprintf (file
, "}\n");
390 bitset_copy (dst
, src
)
396 if (dst
->ops
== src
->ops
)
397 return BITSET__COPY (dst
, src
);
399 /* Convert bitset types. We assume that the DST bitset
400 is large enough to hold the SRC bitset. */
402 BITSET_EXECUTE (src
, 0, i
,
411 /* Return size in bits of bitset SRC. */
416 return BITSET__SIZE (src
);
425 return BITSET__OP1 (dst
, BITSET_ZERO
);
434 return BITSET__OP1 (dst
, BITSET_ONES
);
438 /* Return non-zero if all bits in bitset SRC are reset. */
443 return BITSET__OP1 (src
, BITSET_EMPTY_P
);
447 /* Return DST == DST | SRC. */
449 bitset_subset_p (dst
, src
)
453 return BITSET__OP2 (dst
, src
, BITSET_SUBSET_P
);
457 /* Return DST == SRC. */
459 bitset_equal_p (dst
, src
)
463 BITSET__CHECK2 (dst
, src
);
464 return BITSET__OP2 (dst
, src
, BITSET_EQUAL_P
);
470 bitset_not (dst
, src
)
474 BITSET__CHECK2 (dst
, src
);
475 return BITSET__OP2 (dst
, src
, BITSET_NOT
);
479 /* DST = SRC1 | SRC2. Return non-zero if DST != SRC1 | SRC2. */
481 bitset_or (dst
, src1
, src2
)
486 BITSET__CHECK3 (dst
, src1
, src2
);
487 return BITSET__OP3 (dst
, src1
, src2
, BITSET_OR
);
491 /* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
493 bitset_and (dst
, src1
, src2
)
498 BITSET__CHECK3 (dst
, src1
, src2
);
499 return BITSET__OP3 (dst
, src1
, src2
, BITSET_AND
);
503 /* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
505 bitset_xor (dst
, src1
, src2
)
510 BITSET__CHECK3 (dst
, src1
, src2
);
511 return BITSET__OP3 (dst
, src1
, src2
, BITSET_XOR
);
515 /* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
517 bitset_andn (dst
, src1
, src2
)
522 BITSET__CHECK3 (dst
, src1
, src2
);
523 return BITSET__OP3 (dst
, src1
, src2
, BITSET_ANDN
);
527 /* DST = SRC1 | ~SRC2. Return non-zero if DST != SRC1 | ~SRC2. */
529 bitset_orn (dst
, src1
, src2
)
534 BITSET__CHECK3 (dst
, src1
, src2
);
535 return BITSET__OP3 (dst
, src1
, src2
, BITSET_ORN
);
539 /* DST = (SRC1 | SRC2) & SRC3. Return non-zero if
540 DST != (SRC1 | SRC2) & SRC3. */
542 bitset_or_and (dst
, src1
, src2
, src3
)
548 BITSET__CHECK4 (dst
, src1
, src2
, src3
);
549 return BITSET__OP4 (dst
, src1
, src2
, src3
, BITSET_OR_AND
);
553 /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if
554 DST != (SRC1 & SRC2) | SRC3. */
556 bitset_and_or (dst
, src1
, src2
, src3
)
562 BITSET__CHECK4 (dst
, src1
, src2
, src3
);
563 return BITSET__OP4 (dst
, src1
, src2
, src3
, BITSET_AND_OR
);
567 /* Dump bitset BSET to FILE. */
569 bitset_dump (file
, bset
)
573 bitset_print (file
, bset
, 0);
577 /* Function to be called from debugger to print bitset. */
582 bitset_print (stderr
, bset
, 1);
586 /* Release memory associated with bitsets. */
588 bitset_release_memory ()
590 lbitset_release_memory ();
591 ebitset_release_memory ();
597 bitset_list (bset
, list
, num
, next
)
605 count
= BITSET__LIST (bset
, list
, num
, next
);
612 enum bitset_type type
;
614 type
= bset
->ops
->type
;
615 BITSET_STATS_LISTS_INC (bset
);
617 /* Log histogram of number of set bits. */
618 for (i
= 0, tmp
= count
; tmp
; tmp
>>= 1, i
++)
620 if (i
>= BITSET_LOG_COUNT_BINS
)
621 i
= BITSET_LOG_COUNT_BINS
- 1;
622 BITSET_STATS_LIST_COUNTS_INC (bset
, i
);
624 /* Log histogram of number of bits in set. */
625 size
= bitset_size (bset
);
626 for (i
= 0, tmp
= size
; tmp
; tmp
>>= 1, i
++)
628 if (i
>= BITSET_LOG_SIZE_BINS
)
629 i
= BITSET_LOG_SIZE_BINS
- 1;
630 BITSET_STATS_LIST_SIZES_INC (bset
, i
);
632 /* Histogram of fraction of bits set. */
633 i
= size
? (count
* BITSET_DENSITY_BINS
) / size
: 0;
634 if (i
>= BITSET_DENSITY_BINS
)
635 i
= BITSET_DENSITY_BINS
- 1;
636 BITSET_STATS_LIST_DENSITY_INC (bset
, i
);
642 /* Print a percentage histogram with message MSG to FILE. */
644 bitset_percent_histogram_print (file
, name
, msg
, n_bins
, bins
)
655 for (i
= 0; i
< n_bins
; i
++)
661 fprintf (file
, "%s %s", name
, msg
);
662 for (i
= 0; i
< n_bins
; i
++)
663 fprintf (file
, "%.0f-%.0f%%\t%8d (%5.1f%%)\n",
665 (i
+ 1) * 100.0 / n_bins
,
666 bins
[i
], (100.0 * bins
[i
]) / total
);
670 /* Print a log histogram with message MSG to FILE. */
672 bitset_log_histogram_print (file
, name
, msg
, n_bins
, bins
)
681 unsigned int max_width
;
684 for (i
= 0; i
< n_bins
; i
++)
690 /* 2 * ceil (log10(2) * (N - 1)) + 1 */
691 max_width
= 2 * (unsigned int)(0.30103 * (n_bins
- 1) + 0.9999) + 1;
693 fprintf (file
, "%s %s", name
, msg
);
694 for (i
= 0; i
< 2; i
++)
695 fprintf (file
, "%*d\t%8d (%5.1f%%)\n",
696 max_width
, i
, bins
[i
], 100.0 * bins
[i
] / total
);
698 /* Perhaps we should bail out once the histogram goes to zero. */
699 for (; i
< n_bins
; i
++)
700 fprintf (file
, "%*d-%d\t%8d (%5.1f%%)\n",
701 max_width
- ((unsigned int) (0.30103 * (i
) + 0.9999) + 1),
702 1 << (i
- 1), (1 << i
) - 1, bins
[i
], (100.0 * bins
[i
]) / total
);
706 /* Print bitset statistics to FILE. */
708 bitset_stats_print_1 (file
, name
, stats
)
711 struct bitset_type_stats_struct
*stats
;
716 fprintf (file
, "%d %ss xmalloced, %d freed.\n",
717 stats
->xmallocs
, name
, stats
->xfrees
);
718 fprintf (file
, "%d %ss oballoced, %d freed.\n",
719 stats
->oballocs
, name
, stats
->obfrees
);
721 fprintf (file
, "%d bitset_lists\n", stats
->lists
);
723 bitset_log_histogram_print (file
, name
, "count log histogram\n",
724 BITSET_LOG_COUNT_BINS
, stats
->list_counts
);
726 bitset_log_histogram_print (file
, name
, "size log histogram\n",
727 BITSET_LOG_SIZE_BINS
, stats
->list_sizes
);
729 bitset_percent_histogram_print (file
, name
, "density histogram\n",
730 BITSET_DENSITY_BINS
, stats
->list_density
);
734 /* Print all bitset statistics to FILE. */
736 bitset_stats_print (file
, verbose
)
738 int verbose ATTRIBUTE_UNUSED
;
741 static const char *names
[] = BITSET__TYPE_NAMES
;
746 fprintf (file
, "Bitset statistics:\n\n");
748 if (bitset_stats
->runs
> 1)
749 fprintf (file
, "Accumulated runs = %d\n", bitset_stats
->runs
);
751 for (i
= 0; i
< BITSET_TYPE_NUM
; i
++)
752 bitset_stats_print_1 (file
, names
[i
], &bitset_stats
->types
[i
]);
754 #endif /* BITSET_STATS */
757 /* Initialise bitset statistics logging. */
762 bitset_stats
= &bitset_stats_data
;
763 bitset_stats_read ();
764 #endif /* BITSET_STATS */
768 /* Read bitset statistics file. */
777 file
= fopen (BITSET_STATS_FILE
, "r");
780 if (fread (&bitset_stats_data
, sizeof (bitset_stats_data
),
784 perror ("Could not read stats file");
786 fprintf (stderr
, "Bad stats file size\n");
790 bitset_stats_data
.runs
++;
794 /* Write bitset statistics file. */
796 bitset_stats_write ()
803 file
= fopen (BITSET_STATS_FILE
, "w");
806 if (fwrite (&bitset_stats_data
, sizeof (bitset_stats_data
),
808 perror ("Could not write stats file");
812 perror ("Could not open stats file for writing");
816 /* Dump bitset statistics to FILE. */
818 bitset_stats_dump (file
)
822 bitset_stats_print (file
, 0);
823 bitset_stats_write ();
824 #endif /* BITSET_STATS */
828 /* Function to be called from debugger to print bitset stats. */
830 debug_bitset_stats (void)
833 bitset_stats_print (stderr
, 1);
834 #endif /* BITSET_STATS */