[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Bitset statistics
From: |
Akim Demaille |
Subject: |
Re: Bitset statistics |
Date: |
03 Mar 2002 12:28:32 +0100 |
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) XEmacs/21.4 (Common Lisp) |
| Akim Demaille writes:
| > I have finished (at home), spreading bitset into Bison. I have a few
| > wishes:
| >
| > - int bitset_count: number of bits set.
| > - int bitset_disjoint_p (bitset, bitset): whether they have common
| > bits. (If different size, then die I guess).
|
| OK, these are trivial to implement and are included in my new patch.
Thanks!
| I've also changed the API for the bitset vectors so that the
| number of vectors do not have to passed to every call.
Yeah! I missed the existence of these! Excellent, that cleans up
Bison even further. Then I have another suggestion, which, I believe,
is general enough for submission to bitset:
----------------------------------------
/* Generate transitive closure of a matrix,
Copyright 1984, 1989, 2000, 2001, 2002 Free Software Foundation,
Inc.
This file is part of Bison, the GNU Compiler Compiler.
Bison 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, or (at your option)
any later version.
Bison 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 Bison; see the file COPYING. If not, write to
the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
Boston, MA 02111-1307, USA. */
#include "system.h"
#include "getargs.h"
#include "bitsetv.h"
#include "warshall.h"
/*--------------------------------------------------------.
| Display the MATRIX array of SIZE bitsets of size SIZE. |
`--------------------------------------------------------*/
static void
bitmatrix_print (const char *title, bitsetv matrix)
{
size_t i, j;
size_t size = bitset_size (matrix[0]);
/* Title. */
fprintf (stderr, "%s BEGIN\n", title);
/* Column numbers. */
fputs (" ", stderr);
for (i = 0; i < size; ++i)
putc (i / 10 ? '0' + i / 10 : ' ', stderr);
putc ('\n', stderr);
fputs (" ", stderr);
for (i = 0; i < size; ++i)
fprintf (stderr, "%d", i % 10);
putc ('\n', stderr);
/* Bar. */
fputs (" .", stderr);
for (i = 0; i < size; ++i)
putc ('-', stderr);
fputs (".\n", stderr);
/* Contents. */
for (i = 0; i < size; ++i)
{
fprintf (stderr, "%2d|", i);
for (j = 0; j < size; ++j)
fputs (bitset_test (matrix[i], j) ? "1" : " ", stderr);
fputs ("|\n", stderr);
}
/* Bar. */
fputs (" `", stderr);
for (i = 0; i < size; ++i)
putc ('-', stderr);
fputs ("'\n", stderr);
/* End title. */
fprintf (stderr, "%s END\n\n", title);
}
/*-------------------------------------------------------------------.
| Given the MATRIX array of N bitsets of size N, modify its contents |
| to be the transive closure of what was given. |
`-------------------------------------------------------------------*/
static void
TC (bitsetv matrix)
{
int i, j;
if (trace_flag)
bitmatrix_print ("TC: Input", matrix);
/* R (J, I) && R (I, K) => R (J, K).
I *must* be the outter loop. */
for (i = 0; matrix[i]; ++i)
for (j = 0; matrix[j]; ++j)
if (bitset_test (matrix[j], i))
bitset_or (matrix[j], matrix[j], matrix[i]);
if (trace_flag)
bitmatrix_print ("TC: Output", matrix);
}
/*---------------------------------------------------------------.
| Reflexive Transitive Closure. Same as TC and then set all the |
| bits on the diagonal of MATRIX. |
`---------------------------------------------------------------*/
void
RTC (bitsetv matrix)
{
int i;
TC (matrix);
for (i = 0; matrix[i]; ++i)
bitset_set (matrix[i], i);
}
----------------------------------------
| I suppose the next thing to do is to write up the docs. I've been
| waiting for a response on the gcc mailing list but the "cone of
| silence" seems to have descended...
:(
AFAIAC, I am still waiting for the FSF's approval :(
Also, as yet another wish from a painful user ;) I have many
warnings. If I was not aware GCC was also looking for 0 warnings, I
wouldn't report these, but you might want to fix them. Some are due
to missing protos, but most are related to id clashes.
----------------------------------------
source='bitset.c' object='bitset.o' libtool=no \
depfile='.deps/bitset.Po' tmpdepfile='.deps/bitset.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f bitset.c || echo './'`bitset.c
source='bitsetv.c' object='bitsetv.o' libtool=no \
depfile='.deps/bitsetv.Po' tmpdepfile='.deps/bitsetv.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f bitsetv.c || echo './'`bitsetv.c
bitsetv.c:137: warning: function declaration isn't a prototype
source='ebitset.c' object='ebitset.o' libtool=no \
depfile='.deps/ebitset.Po' tmpdepfile='.deps/ebitset.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f ebitset.c || echo './'`ebitset.c
ebitset.c: In function `ebitset_elt_find':
ebitset.c:316: warning: declaration of `index' shadows global declaration
ebitset.c:331: warning: declaration of `elt' shadows previous local
ebitset.c: In function `ebitset_set':
ebitset.c:584: warning: declaration of `index' shadows global declaration
ebitset.c: In function `ebitset_reset':
ebitset.c:598: warning: declaration of `index' shadows global declaration
ebitset.c: In function `ebitset_test':
ebitset.c:617: warning: declaration of `index' shadows global declaration
ebitset.c: In function `ebitset_reverse_list':
ebitset.c:651: warning: declaration of `index' shadows global declaration
ebitset.c: In function `ebitset_list':
ebitset.c:734: warning: declaration of `index' shadows global declaration
ebitset.c:796: warning: declaration of `elt' shadows previous local
ebitset.c: In function `ebitset_op2':
ebitset.c:956: warning: declaration of `selt' shadows previous local
ebitset.c:957: warning: declaration of `delt' shadows previous local
ebitset.c:995: warning: declaration of `selt' shadows previous local
ebitset.c:996: warning: declaration of `delt' shadows previous local
ebitset.c: At top level:
ebitset.c:1243: warning: function declaration isn't a prototype
ebitset.c:1253: warning: function declaration isn't a prototype
ebitset.c:1277: warning: function declaration isn't a prototype
source='lbitset.c' object='lbitset.o' libtool=no \
depfile='.deps/lbitset.Po' tmpdepfile='.deps/lbitset.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f lbitset.c || echo './'`lbitset.c
lbitset.c: In function `lbitset_elt_link':
lbitset.c:309: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_elt_find':
lbitset.c:371: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_set':
lbitset.c:588: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_reset':
lbitset.c:602: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_test':
lbitset.c:619: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_reverse_list':
lbitset.c:651: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_list':
lbitset.c:735: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_op1':
lbitset.c:936: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_op2':
lbitset.c:987: warning: declaration of `index' shadows global declaration
lbitset.c: In function `lbitset_op3':
lbitset.c:1096: warning: declaration of `index' shadows global declaration
lbitset.c: At top level:
lbitset.c:1310: warning: function declaration isn't a prototype
lbitset.c:1320: warning: function declaration isn't a prototype
lbitset.c:1330: warning: function declaration isn't a prototype
source='sbitset.c' object='sbitset.o' libtool=no \
depfile='.deps/sbitset.Po' tmpdepfile='.deps/sbitset.TPo' \
depmode=gcc /bin/sh ../config/depcomp \
gcc -DHAVE_CONFIG_H -I. -I. -I.. -I../intl -I.. -I../src -I../intl
-I../lib -g -O2 -Wall -W -Wbad-function-cast -Wcast-align
-Wcast-qual -Wformat -Wmissing-declarations -Wmissing-prototypes
-Wnested-externs -Wshadow -Wstrict-prototypes -Wwrite-strings -c `test
-f sbitset.c || echo './'`sbitset.c
sbitset.c: In function `sbitset_reverse_list':
sbitset.c:187: warning: declaration of `index' shadows global declaration
sbitset.c: In function `sbitset_list':
sbitset.c:246: warning: declaration of `index' shadows global declaration